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
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What you are looking for is average-case complexity. $\endgroup$ – Sasho Nikolov Jul 18 '17 at 15:42
  • 1
    $\begingroup$ Can you please explain why what I have described is equivalent to average-case complexity? The similarity between the concepts is clear, but I didn't refer to the running time but to the decidability of certain problems (in the example of the halting problem, the machine can mistake but is accurate for x% of the inputs). $\endgroup$ – user1767774 Jul 18 '17 at 16:39
  • 1
    $\begingroup$ I had in mind computability as the extreme case of complexity. Besides that your particular example is ill-defined: there are infinitely many inputs, so what is x% of the inputs? I.e. what probability distribution on inputs are you considering? $\endgroup$ – Sasho Nikolov Jul 18 '17 at 19:40
  • 1
    $\begingroup$ Thanks for the clarification. I admit the example is ill-defined, I was just wondering if similar notions are at all useful or are used in practice. $\endgroup$ – user1767774 Jul 18 '17 at 20:34
  • 2
    $\begingroup$ One reason to be careful: a unary encoding of the halting problem can be "decided" by a machine that says NO, and it will be extremely accurate (tending to 1), if one uses a uniform distribution over the set of all Boolean strings for any input. $\endgroup$ – András Salamon Jul 18 '17 at 20:46