Showing that carbon is not a complexity measure per Blum

Question

In Computational Complexity by Papadimitriou, there is an exercise about Blum's axioms where it asks to prove that several measures for the complexity of a Turing machine satisfy them.

7.4.12 Blum complexity. Time and space are only two examples of "complexity measures" for computations. In general, suppose that we have a function $\Phi$, possibly undefined on many arguments, mapping Turing machine-input pairs to the nonnegative integers. Suppose $\Phi$ is such that the following two axioms hold:

Axiom 1: $\Phi(M, x)$ is defined if and only if $M (x)$ is defined.

Axiom 2: It is decidable, given $M$, $x$, and $k$, whether $\Phi(M, x) = k$.

Then $\Phi$ is called a complexity measure. This elegant formulation of complexity was developed in

• M. Blum "A machine-independent theory of the complexity of recursive functions," J.ACM 14, 2, pp. 322–336, 1967.

(a) Show that space and time are complexity measures. (Notice that in this context we do not maximize space and time over all strings of the same length, but leave the dependence on individual strings.) Repeat for nondeterministic space and time.

(b) Show that ink (the number of times during a computation that a symbol has to be overwritten by a different symbol) is a complexity measure.

(c) Show that reversals (the number of times during a computation that the cursor must change direction of motion) is a complexity measure.

(d) Show that carbon (the number of times during a computation that a symbol has to be overwritten with the same symbol) is not a complexity measure.

I am interested in the answer of (d) which I don't know how to approach.

Answer 1

Papadimitriou is being extremely sloppy here. Let us consider part (b) first. What does Papadimitriou mean by "ink"? Suppose that he really means what he wrote: the number of times during computation that a symbol is overwritten by a different symbol. Consider a Turing machine which repeatedly goes right one step, then left one step, in an infinite loop. Then ink is 0, but the machine never halts, and so Axiom 1 seems to be violated. We conclude therefore that ink (and carbon) should be undefined if the machine doesn't halt.

The more challenging bit is proving Axiom 2. Given $M$, $x$, and $k$, we need to decide whether (1) $M$ halts on $x$ and (2) during this halting computation, a symbol is overwritten with a new symbol exactly $k$ times. It might seem at first that this shouldn't be decidable, since we are in some sense trying to solve the halting problem. However, we are given the crucial advice $k$. Let us see how it helps us. We simulate $M$ on $x$ until it either halts (in which case we declare No) or we have reached ink $k$. In the latter case, it remains to check whether $M$ halts on $x$, given the additional promise that the tape doesn't change any more.

The additional promise allows us to continue the simulation until one of the following happens: (1) carbon increases, (2) computation halts, (3) a configuration repeats, (4) we have determined that the machine is off on a tangent on one of the infinite ends of the tape. I leave further details to you.

A similar trick doesn't work for part (d). Indeed, we can arrange for a Turing machine to never overwrite a tape symbol with itself. The idea is that for each original tape symbol we will have two new ones, treated in exactly the same way, that are alternated if needed to insure that carbon is zero. It follows that the halting problem can be reduced to the problem of deciding whether carbon is zero or not.