# Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?

I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?

Clarification:

Note that since the execution of the machine is not deterministic, one should be careful about defining the number of coin tosses for a PTM $M$ on input $x$ in a way similar to the time complexity for NTMs and PTMs. One way is to define it as the maximum number of coin tosses over possible executions of $M$ on $x$.

We need the definition to satisfy the axiom about decidability of $m(M,x)=k$. We can define it as follows:

$$m(M,x) = \begin{cases} k & \text{all executions of M on x halt, k=\max #coin tosses} \\ \infty & o.w. \ \end{cases}$$

The number of random bits that an algorithm uses is a complexity measure that appears in papers, e.g. "algorithm $A$ uses only $\lg n$ random bits, whereas algorithm $B$ uses $n$ random bits".

• Why would $m$ be computable? There may be infinitely many executions of $M$ on $x$ and an unbounded number of tosses.
– Raphael
Mar 28, 2012 at 6:33
• @Raphael, if the number of coin tosses are unbounded then $m$ cannot be a number and should be $\infty$ (undefined). Also note that if there are unbounded long executions then there is a non-halting execution (by Konig's lemma). Mar 28, 2012 at 8:03

Specifically, for a TM $M$ with input $x$, the Blum axioms require an algorithm that for input $(M,x,n)$ decides if $\Phi(M,x)=n$, where $\Phi$ is the complexity measure. But if $\Phi(M,x)$ is a probabilistic function, then it cannot be computed by an algorithm, and there also can be no algorithm as required by the axioms.
According to the definition on Wikipedia, $T = \{(i,x,t) \mid \varphi_i \text{ tosses } t \text{ coins on } x\}$ has to be recursive if the measure you propose is to be a Blum complexity measure. As the number of coin tosses needed for $\varphi_i(x)$ may very well be random as well, how can the set be decidable?