A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the distribution over all inputs (rather than over all random bits)? For example, is it possible that there exists a probabilistic turing machine that accurately solves the halting problem with a probability of 99% (over the space of all possible valid computer programs received as input)?
closed as off-topic by Emil Jeřábek, Kaveh, Jeffε, Mohammad Al-Turkistany, Yuval Filmus Jul 31 '17 at 11:28
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Kaveh, Jeffε, Mohammad Al-Turkistany, Yuval Filmus