Back to Search
Start Over
The probability of a computable output from a random oracle
- Publication Year :
- 2016
- Publisher :
- arXiv, 2016.
-
Abstract
- Consider a universal oracle Turing machine that prints a finite or an infinite binary sequence, based on the answers to the binary queries that it makes during the computation. We study the probability that this output is infinite and computable when the machine is given a random (in the probabilistic sense) stream of bits as the answers to its queries during an infinitary computation. 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 that produce a computable infinite 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) that witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.
- Subjects :
- Discrete mathematics
FOS: Computer and information sciences
General Computer Science
Logic
Computable number
010102 general mathematics
Description number
Busy beaver
0102 computer and information sciences
Computational Complexity (cs.CC)
01 natural sciences
Theoretical Computer Science
Computational Mathematics
Computer Science - Computational Complexity
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computable function
010201 computation theory & mathematics
Chaitin's constant
Turing reduction
0101 mathematics
Algorithmically random sequence
Mathematics
Halting problem
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....1960cb2754139a5310b40d31903f2f8f
- Full Text :
- https://doi.org/10.48550/arxiv.1612.08537