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


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".

  • $\begingroup$ Why would $m$ be computable? There may be infinitely many executions of $M$ on $x$ and an unbounded number of tosses. $\endgroup$
    – Raphael
    Commented Mar 28, 2012 at 6:33
  • $\begingroup$ @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). $\endgroup$
    – Kaveh
    Commented Mar 28, 2012 at 8:03

2 Answers 2


Probabilistic "functions" are not even functions in the classical sense of the term "function", that is, they do not assign to each member of the domain a specific member of the range. They are not even partial functions. So the requirement of the Blum axioms that the complexity functions be computable cannot be satisfied.

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.

We could, however, define a complexity measure differently on probabilistic models, allowing a random variable, which is after all, a kind of function. Then various properties of the r.v. -- mean, median, standard deviation, etc -- could well qualify as complexity measures, and you could develop the theory from there, in the probabilistic/statistical realm.

So, although Blum measures are somewhat out of favor, except for the classic space and time measures, there's no inherent reason the basic idea can't be extended in ways like this.


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?

Probabilistic functions do not fit the classical paradigm of computable functions well; even non-deterministic machines are required to loop if they do not output the correct result.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.