4
$\begingroup$

I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)$ runs in $CT \log T$ steps where $C$ depends only on $M$'s alphabet size, number of tapes, and number of states. I'll describe $U$ loosely here:

It has an input tape, output tape, tape for $M$'s states and transition functions, tape for $M$'s current state, and one work tape. We say $M$ has $k$ work tapes and an alphabet of $\Gamma$.

$U$ uses an alphabet of $\Gamma^k$ to put the letters of all $k$ tapes on one cell and has a clever way of imitating the left and right shifts of different heads.

Since we only have $T$ steps, we only need to go from $-T$ to $T$. We'll say $L_i$ goes from $2^i$ to $2^{i+1}-1$ and $R_i$ goes from $-2^{i+1}+1$ to $-2^i$. This goes from $i=0$ to $i=\log T+1$. For any $i$, $L_i$ and $R_i$ is full of blank symbols, half-blank half-filled, or completely filled. Furthermore, the total number of blank symbols in both $L_i$ and $R_i$ at one time is $2^i$, meaning half of all of the cells are blank while the other half is information.

To left shift, find the smallest $i$ so $R_i$ is not empty and thus $L_i$ is not full. Put the leftmost non-blank symbol in position $0$ (i.e. under the head in $M$) and move the other $2^{i-1}-1$ non-blank symbols into the empty $R_0,R_1,...R_{i-1}$. This leaves all of those zones half-empty.

Push the $2^{i-1}$ leftmost non-blank symbols in $L_{i-1},...,L_1$ into $L_i$ and then reorganize the other non-blank symbols to make $L_{i-1},...,L_1$ all half-full.

Right shifts look similarly, except switch the roles of the left and right zones.

I want to solve the following exercise:

Define a TM $M$ to be oblivious if its head movement does not depend on the input but only on the input length. That is, M is oblivious if for every input $x \in \{0, 1\}^∗$ and $i \in N$, the location of each of $M$’s heads at step $i$ of execution on input $x$ is only a function of $\lvert x \rvert$ and $i$. Show that for any time-constructible $T : \Bbb{N} \rightarrow \Bbb{N}$, if $L \in \mathbf{DTIME}(T(n))$, then there is an oblivious TM that decides $L$ in $O(T(n)\log T(n))$ time.

Hint: Show that $U$ can be tweaked to be oblivious.

Now, my question is, under such a machine, while maintaining $CT\log T$ time, how do we make $U$ oblivious? I see how putting the input down initially and the left/right shifts are simply functions of $\lvert x \rvert$, but when we decide to left/right shift each tape has to decide on $x$ since we're not given that $T$ is oblivious, so how do we time the left and right shifts of $U$ so that they only depend on $\lvert x \rvert$ and not on the actual content of $x$?

$\endgroup$
3
1
$\begingroup$

A concrete construction of such a UTM, from which one can construct oblivious and efficient TMs, is given in this lecture note https://courses.cs.washington.edu/courses/cse531/16wi/lectures/lect01.pdf.

A crucial idea in the construction is rearranging $L_{i+2}$ and $R_{i+2}$ EVERY $2^i$ steps. The invariant ($L_i$ and $R_i$ are empty, half-full or full) does not hold every steps in this construction. However, we can see that it holds when the rearrangement occurs.

$\endgroup$
2
  • 1
    $\begingroup$ While the link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. It is common for the links to lecture notes for university become broken. Please read What is StackExchange's take on link only answers?. $\endgroup$
    – John L.
    Oct 21 '21 at 7:11
  • $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$
    – xskxzr
    Oct 22 '21 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.