1
$\begingroup$

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)?

$\endgroup$
  • 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