Showing that carbon is not a complexity measure per Blum
Papadimitriou is being extremely sloppy here. Let us consider part (b) first. What does Papadimitriou mean by &quot;ink&quot;? 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.