Probabilistic poly-time machine always halts on all inputs?

In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.

Is the intention really to say that the machine halts for all inputs, or that if it halts it must be in polynomial time?

We say that a probabilistic Turing machine M runs in time T(n) if for any input x M halts in less than T(|x|) steps independently of the random choices it makes during the computation (worst case over all possible computation paths).

For example, the most general definition of Probabilistic Polynomial-time, namely PP, is:


A language L is in PP if and only if there exists a probabilistic Turing machine M, such that

• M runs for polynomial time on all inputs

• For all x in L, M outputs 1 with probability strictly greater than 1/2

• For all x not in L, M outputs 1 with probability less than or equal to 1/2.

It always halts in polynomial time on all inputs.

Because the two probabilities can be made very close ($\frac{1}{2}+\frac{1}{2^n},\frac{1}{2}-\frac{1}{2^n}$), it would take potentially an exponential number of runs to distinguish accepting from rejecting with good confidence; so a more representative and efficient probabilistic class is BPP (Bounded-error Probabilistic Polynomial-time):


A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that

• M runs for polynomial time on all inputs

• For all x in L, M outputs 1 with probability greater than or equal to 2/3

• For all x not in L, M outputs 1 with probability less than or equal to 1/3.

Again, M always halts in polynomial time on all inputs.

See also the complexity class RP (Randomized Polynomial time).

We have: $RP \subseteq BPP \subseteq PP$

StackExchange Computer Science Q#2047, answer score: 6