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

Question

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

Answer 1

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.

Answer 2

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.