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

CC BY-SA 3.0
2017-07-18T15:42:02.237Z
What you are looking for is average-case complexity.
Sasho Nikolov
CC BY-SA 3.0
2017-07-18T16:39:40.570Z
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).
user1767774
CC BY-SA 3.0
2017-07-18T19:40:22.617Z
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?
Sasho Nikolov
CC BY-SA 3.0
2017-07-18T20:34:57.227Z
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.
user1767774
CC BY-SA 3.0
2017-07-18T20:46:35.187Z
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.
András Salamon
<computability><turing-machines><randomness>
An alternative model of a probabilistic Turing machine
user1767774
# An alternative model of a probabilistic Turing machine

(Asked by: username_0 on 2017-07-18)

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

**Tags:** computability, turing-machines, randomness
> **Comments:**
> **username_1**: What you are looking for is average-case complexity.  
> **username_0**: 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).  
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: 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.  

---

## 0 answers

