Proof of proposition between Precise Turing Machine and Proper Complexity function

Question

In "Computational Complexity" textbook by C. H. Papadimitriou, p. 141, he proved the following claim.

Proposition 7.1: Let there be a DTM/NDTM M that decides a language L within time/space $f(n)$, where $f$ is a proper function. Then there is a precise TM $M'$ that decides L in time/space $O(f(n))$.

Proof. We start simulating $M'$ on input $x$ by $M_f$ ($M_f$ is same as M, it is TM with proper function $f$ on input $x$). After $M_f$'s computation has halted, $M$ uses the output string of $M_f$ as a "yardstick" of length $f(|x|)$, to guide its further computation. Now, we have two cases depending on the resources: $f(n)$ is time bound or space bound.

For if $f(n)$ is time bound, then $M'$ simulates $M$ on a different set of strings ($x_1, x_2, ...$ where for such i, $x_i$ is an arbitrary string), using the yardstick as an "alarm clock". i.e., it moves its cursor forward on the yardstick after the simulation of each step of M, and halts iff a true blank is encountered in $O(f(n))$ steps. For if $f(n)$ is space bound, then $M'$ simulates M on the quasiblanks of $M_f$'s output string. In either case, the machine is precise.

If M is NDTM, then precisely the same amount of time/space is used over all possible computations of $M'$ (the simulation of $M_f$). In both cases, the time/space is the time/space consumed by $M_f$ plus that consumed by M, and it therefore $O(f(n))$.

What is "yardstick" or 'alarm clock'? Are they the same? It is not clear what is it. Is it indicator to such i, where i is cell in tape in the Turing machine. It seems for me 'alarm clock' looks like a step in $M_f$ of simulation with $M$. So, every step is counted and stop when we simulate $M_f$ by $M$ in $O(f(|x|))$ steps.

It is not clear why do we need exactly to define $M_f$? I mean, we could simulate $M'$ by M directly without $M_f$, don't agree.

---

NOTE: for definition of precise TM and proper complexity function, please refer to the book pp. 140-141, or look at some slides [4-6] [here 1].

Answer 1

For interested readers, here are some of related definitions.

A function $f : \Bbb N \to\Bbb N$ is a proper complexity function if $f$ is nondecreasing and there is a $k$-string TM Mf with input and output such that on any input $x$,

1. $M_f(x) = \sqcap^{f(|x|)}$ where $u$ is a tally (“quasi-blank”) symbol,
2. $M_f$ halts within $O(|x|+f(|x|))$ steps, and
3. $M_f$ uses $O(f(|x|))$ space besides its input.

Let $M$ be a deterministic/nondeterministic multi-string Turing machine (with or without input and output). Machine $M$ is precise if there are functions $f$ and $g$ such that for every $n\ge 0$, for every input $x$ of length $n$, and for every computation of $M$,

1. $M$ halts in precisely $f(|x|)$ steps and
2. all of its strings (except those reserved for input and output whenever present) are at halting of length precisely $g(|x|)$.

---

Proposition 7.1 is intuitively simple and clear. If there is such a $M$, we can just extend the computation steps or space used by $M$ to the same limit $g(n)$ for all inputs of the same length $n$, where $g(n)$ is some function large enough but still bounded by $O(f(n))$.

It is not clear why do we need exactly to define $M_f$? I mean, we could simulate $M'$ by M directly without $M_f$.

The issue is how you can make $M'$ precise? For different inputs of the same size, $M$ can halt at different number of steps using different amount of spaces. You must have some reference or standard that can display or communicate the expected number of computation steps or spaces, which $M'$ can look up to and adjust itself to.

What is "yardstick" or 'alarm clock'? Are they the same?

A yardstick is "a fact or standard by which you can judge the success or value of something", according to Cambridge dictionary. That is the "reference or standard" I just said in my last paragraph.

For the sake of simpler explanation, let us assume $M$ is a deterministic $t$-string Turing machine with time bound. Here is how we construct $M'$ in slightly more detail.

Suppose $M_f$ is defined on a $k$-string Turing machine. We will define $M'$ on a $(k$+$t)$-string Turing machine.

Let $x$ be a given input of size $n$, which is given at the start of the first string (tape).

First, $M'$ will copy the input to the start of the $k$+$1$-th string (tape).

Second, $M'$ simulate $M_f$ with input $x$ using the first $k$ strings. Then reset $M'$ state to initial state, without touching the quasi-blanks on the first $k$ strings.

Third, $M'$ simulate $M$ using the remaining $t$ strings, the $k$+$1$-th, $k$+2-th, $\cdots$ and $k$+$t$-th strings. At the same time, whenever $M'$ make one computation step, it will advance its heads on the first $k$ strings once.

Lastly and most importantly, if the simulation of $M$ by $M'$ halts before $f(n)+1$ time, just continue to move the heads on the first $k$ strings until a true blank is encountered, which is an alarm and why this part is referred as "an alarm clock". Then $M$ will halt. This step homogenizes the running time of $M$.

It is possible I miss a detail in a place or two. Besides, there is a problem of choosing which head to move when we stipulate $M'$ to advance its head. I will let you figure out how to fill this obvious loophole. In any case, the idea and concept here are pretty easy to grasp, although the details are long, tedious and error-prone. Just make sure you have convinced yourself and you are confident to convince anybody.

---

More information can be found in Turing Machines as Clocks, Rulers and Randomizers written by José Félix Costa.