# Showing that carbon is not a complexity measure per Blum

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.

• I think this would be a better question if you: (a) provided a complete, self-contained specification of the language that you want the Turing machine to recognize, (b) stated Blum's axioms, (c) showed your work. For which of Blum's axioms do you think it does satisfy? For which do you think it doesn't? Why? What have you tried, to either prove or disprove that it satisfies each axiom? What progress have you made on your own? I'm not sure we're looking to be just a solutions manual for exercises printed in books.
– D.W.
Oct 8, 2020 at 23:16
• Please make an effort to spell people's names correctly. Oct 9, 2020 at 9:17
• @Yuval Filmus You mean Papademetriou? His surname can be written with either i or e. Oct 9, 2020 at 9:21

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.