On the construction of effectively random sets

From MaRDI portal





In the 1980s, P. Gács and A. Kučera proved an unexpected result that every binary sequence \(\alpha\) can be reduced to a Martin-Löf random one, i.e., that for every \(\alpha\), there exists a random sequence \(\omega\) from which \(\alpha\) can be effectively reconstructed. The original proof of this result was rather complex. The authors provide a new proof of this result, a proof based on Schnorr's theorem that a sequence is Martin-Löf random if and only if no lower semi-computable (= subcomputable) martingal succeeds on it. This theorem enables the authors to construct \(\omega\) by diagonalizing against the corresponding martingales. The authors show that similar diagonalization can lead to new results: e.g., they show that there exists a random number that is computably enumerable (c.e.) self-reducible -- i.e., for which the computation of \(\omega_n\) can be efficiently reduced to the computation of the values \(\omega_i\) for \(i<n\). This result nicely complements the known result that no random number is Turing-autoreducible (hence no random number is Turing self-reducible), where autoreducible means that we reduce computation of \(\omega_n\) to computation of \(\omega_i\) with \(i\neq n\). Similar diagonalization techniques also apply for a wider class of rec-random sequences, i.e., sequences on which no computable martingale succeeds. In particular, the authors show that there exists a rec-random sequence which is weak truth-table autoreducible. This is probably the best possible result, because it is known that no rec-random sequence is truth-table autoreducible.











This page was built for publication: On the construction of effectively random sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311758)