Infinite computations with random oracles

Merlin Carl and Philipp Schlicht have posted an article to the arXiv entitled infinite computations with random oracles. A basic result of classical computability theory states that if a real x is Turing-computable relative to all oracles in a set of positive measure, then this real number is Turing-computable in the empty oracle. In different words,  the use of random generators does not enrich the set of computable functions. The authors examine whether this is true for models of infinite computation. In particular, for Infinite Time Turing Machine, Infinite Time Register machines, α-Turing machines, and ordinal Turing/register machines, the authors ask whether there are noncomputable reals (in the sense of the machine type) that are reducible to all oracles in a set of positive measure. The authors show that the answer is negative for most models of infinite computation.


Δημοφιλείς αναρτήσεις από αυτό το ιστολόγιο

New milestone in quantum supremacy