The probability of a computable output from a random oracle

DOI10.1145/3091527MaRDI QIDQ5369244zbMATH OpenOpenAlexWikidataFDO

Authors George Barmpalias, Douglas Cenzer, Christopher P. Porter

Publication date 16 October 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.08537

zbMATH Keywords

algorithmic information theoryprobabilistic machinesrandom oraclesTuring machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation. We study the probability that the machine will produce a computable function when it is given a random stream of bits as the answers to its queries. Surprisingly, we find that these probabilities are the entire class of real numbers in (0, 1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines which produce a computable output with probability exactly 1/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin's halting probability) which witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.

Recommendations

• Random numbers as probabilities of machine behavior
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Randomness and halting probabilities
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• scientific article; zbMATH DE number 1886067

Cited in

(6)

• Chaitin's halting probability and the compression of strings using oracles
• Randomness and halting probabilities
• From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II
• scientific article; zbMATH DE number 1886067 (Why is no real title available?)
• Chaitin's as a continuous function
• The probability of ``undefined (non-converging) output in generating the universal probability distribution

This page was built for publication: The probability of a computable output from a random oracle

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