4
$\begingroup$

I am reading the book [Arora2009] and working on Exercise 1.3, which asks:

EXERCISE 1.3. Complete the proof of Claim 1.6.

Claim 1.6 states:

Claim 1.6 Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used as input, work, and output tape. For every $f: \{0, 1\}^* \to \{0, 1\}$ and time-constructible $T: \mathbb{N} \to \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5 k T(n)^2$ by a single-tape TM $\tilde{M}$. $\diamond$

The proof sketch says:

Again the idea is simple: The TM $\tilde{M}$ encodes $k$ tapes of $M$ on a single tape by using locations $1, k + 1, 2 k + 1, ...$ to encode the first tape, locations $2, k + 2, 2 k + 2, ...$ to encode the second tape etc. (see Figure 1.4). For every symbol $a$ in $M$’s alphabet, $\tilde{M}$ will contain both the symbol $a$ and the symbol $\hat{a}$. In the encoding of each tape, exactly one symbol will be of the “ˆ type,” indicating that the corresponding head of $M$ is positioned in that location (see Figure 1.4). $\tilde{M}$ will not touch the first $n + 1$ locations of its tape (where the input is located) but rather start by taking $O(n^2)$ steps to copy the input bit by bit into the rest of the tape, while encoding it in the above way.

enter image description here

To simulate one step of $M$, the machine $\tilde{M}$ makes two sweeps of its work tape: First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by “ˆ”. Then $\tilde{M}$ uses $M$’s transition function to determine the new state, symbols, and head movements and sweeps the tape back in the right-to-left direction to update the encoding accordingly. Clearly, $\tilde{M}$ will have the same output as $M$. Also, since on $n$-length inputs $M$ never reaches more than location $T(n)$ of any of its tapes, $\tilde{M}$ will never need to reach more than location $2 n + k T(n) \leq (k + 2) T(n)$ of its work tape, meaning that for each of the at most $T(n)$ steps of $M$, $\tilde{M}$ performs at most $5 \cdot k \cdot T(n)$ work (sweeping back and forth requires about $4 \cdot k \cdot T(n)$ steps, and some additional steps may be needed for updating headmovement andbook keeping). $\blacksquare$

I am confused by the sentence:

"for each of the at most $T(n)$ steps of $M$, $\tilde{M}$ performs at most $5 \cdot k \cdot T(n)$ work (sweeping back and forth requires about $4 \cdot k \cdot T(n)$ steps, and some additional steps may be needed for updating head movement and bookkeeping)."

Could someone explain why simulating one step of $M$ requires about $5kT(n)$ steps in $\tilde{M}$? I especially want to understand the breakdown of the $4kT(n)$ sweeping cost and the additional overhead. Thank you!

Reference

[Arora2009] S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ It does not require that much time. That is an upper bound of the time used. It says that $M$ never reaches location $T(n)$, so $M'$ will never need to traverse longer than to $2n +kT(n)$, where $2n$ is the input work area and $kT(n)$ is the cost of using a single tape for encoding $k$ tapes, each of length $T(n)$. $\endgroup$ Commented Oct 4 at 12:35
  • $\begingroup$ To @AinsleyH.: Thank you for your comment. $\endgroup$ Commented Oct 4 at 12:50
  • 1
    $\begingroup$ I love this book, but it keeps saying things like ‘The proof is simple’ a bit too often. $\endgroup$ Commented Oct 8 at 17:49
  • $\begingroup$ To Auberon: Totally agree—Arora & Barak is brilliant, but their “The proof is simple” often assumes a high baseline of familiarity. I’ve had to unpack quite a few “simple” proofs myself. 😅 $\endgroup$ Commented Oct 9 at 2:13

1 Answer 1

Reset to default
3
+100
$\begingroup$

For each tape $i\in[k]$, the machine $\tilde M$ must look for the current position of the head at this tape and keep the symbol at this position in the state. This already costs $2kT(n)$ in the simplest implementation (go the the $i$th position and search in steps of size $k$), since the machine might need to go over the whole tape twice for every tape. After that the machine decides the transition and keeps it in the state and looks again for every head updating it, this costs again $2k$ to find the head positions, and updating costs around $k$ for each tape, which is bounded by $4kT(n) + k^2$ which is bounded by $5kT(n)$ for $k\leq 5T(n)$

Improve this answer
$\endgroup$
10
  • $\begingroup$ Excuse me, what is $[k]$? $\endgroup$ Commented Oct 8 at 6:59
  • 1
    $\begingroup$ k is a constant, and T(n) is usually at least n, since you need at least n to go over the input. $\endgroup$ Commented Oct 9 at 7:06
  • 1
    $\begingroup$ More formally, you can handle cases of n<k separately since you only have constant many such inputs, by having a built in table of inputs/outputs. $\endgroup$ Commented Oct 9 at 7:07
  • 1
    $\begingroup$ The reason for twice: for each head we go to the beginning and then look for the head. If all heads are at the ends of their tapes, you would pay n to go to the beginning and n again to find the head at the end. You can optimize this, but we only need it as an upper bound. $\endgroup$ Commented Oct 9 at 7:14
  • 1
    $\begingroup$ To Narek Bojikian: Thank you for your comments. $\endgroup$ Commented Oct 10 at 11:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.