patternMinor
Oblivious Universal Turing Machine in O(T log(T)) time
Viewed 0 times
loguniversaloblivioustimemachineturing
Problem
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 e
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 e
Solution
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.
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.
Context
StackExchange Computer Science Q#60005, answer score: 2
Revisions (0)
No revisions yet.