On relative randomness (Q688792): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Q688791 / rank | |||
Property / reviewed by | |||
Property / reviewed by: Vladik Ya. Kreinovich / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2709403 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ∏ 0 1 Classes and Degrees of Theories / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms and Randomness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3758821 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4723720 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4732457 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3484822 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Von Mises' definition of random sequences reconsidered / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The axiomatization of randomness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4385509 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The definition of random sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Classical recursion theory. The theory of functions and sets of natural numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4040892 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:28, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On relative randomness |
scientific article |
Statements
On relative randomness (English)
0 references
2 June 1994
0 references
In algorithmic complexity theory, an element is declared random iff it does not belong to any constructive set of measure 0. In particular, ``relative'' randomness is defined as follows. Assume that an infinite binary sequence \(\alpha\) is given. By an \(\alpha\)-algorithm, we mean an algorithm that uses \(\alpha\) as an oracle. An interval \(I\) on a set of all binary sequences is a set of all sequences \(\beta\) that start with a given finite sequence \(\beta_ 1 \dots \beta_ p\). The measure \(\mu\) is defined as follows: for each interval \(I\) determined by a sequence \(\beta_ 1 \dots \beta_ p\), the measure \(\mu(I)\) of this intervals is \(2^{-p}\). We say that a set \(S\) of infinite binary sequences has \(\alpha\)-constructive measure 0, if there exists an \(\alpha\)-algorithm that for every \(n\), generates a sequence \(I_{mn}\) of intervals such that \(S \subseteq I_ n=\cup_ mI_{mn}\), and \(\mu(I_ n) \leq 2^{- n}\). A sequence \(\beta\) is called \(\alpha\)-random (or, to be more precise, \(\alpha-1\)-random) if it does not belong to any set of \(\alpha\)- constructive measure 0 (or, equivalently, for which the one-element set \(\{\beta\}\) is not of \(\alpha\)-constructive measure 0). Crudely speaking, if \(\beta\) is \(\alpha\)-random, this means in particular, that knowing \(\alpha\) will not help in computing \(\beta\). A natural question is: does this also mean that knowing \(\beta\) does not help in computing \(\alpha\)? This question was raised by M. van Lambalgen and D. Zambella. The author provides the following answer: there exist \(\alpha\) and \(\beta\) such that \(\beta\) is \(\alpha\)-random while \(\alpha\) is recursive in \(\beta\). Other results on relative randomness are also proved.
0 references
random set
0 references
constructive measure 0
0 references
relative randomness
0 references
algorithmic complexity theory
0 references
0 references