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.