It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?
1
-
1$\begingroup$ Cpt Wobbles, I suggest you should go through the logarithmic overhead simulation in Arora and Barak's book. It is very understandable the way they have presented. $\endgroup$– SarvottamanandaFeb 29, 2016 at 8:36
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
9
No. The logarithmic overhead comes from the fact that the machine you're simulating could have an arbitrarily large state set $Q$ and arbitrarily large tape alphabet $\Gamma$. To simulate any such machine using a fixed, constant number of states and a fixed, constant tape alphabet, you need to code $Q$ and $\Gamma$ as multiple symbols in the universal machine's tape alphabet: specifically, you need $\log |Q|$ symbols to write down the current state of the simulated machine, and each character of the simulated tape will take $\log |\Gamma|$ symbols on the universal machine's tape. (The base of the logarithm will depend on how many symbols you use: for example, simulating in binary will give logs to base 2.)
Because of this, the logarithmic slowdown is unavoidable, even if you use multiple tapes. Indeed, if you only use a single tape, it'll be even worse than logarithmic.
However, see Shreesh's answer for a more significant source of logarithmic overhead, which is logarithmic in the running time of the simulated machine, not just the length of its description.
answered Feb 29, 2016 at 3:36
-
$\begingroup$ Hmmm I see what you are saying. So even if I use a multi-dimensional tape with a constant number of heads, this slowdown is unavoidable. Is that a correct statement? $\endgroup$ Feb 29, 2016 at 3:40
-
$\begingroup$ I believe it's correct, yes. I can't see any way to avoid it. $\endgroup$ Feb 29, 2016 at 3:43
-
$\begingroup$ One more followup. Since the volume of computation is unavoidable, is it possible to reduce the time by performing operations in parallel? I think the answer is no as well as we can only have as many active heads as the program we are simulating plus a constant number. $\endgroup$ Feb 29, 2016 at 4:04
-
1$\begingroup$ The linear speedup theorem says you can make the constants as small as you want without changing the model of computation. And note that you can't make your machine have as many tapes as the machine you're simulating, since the number of tapes the universal machine has must be a fixed constant, independent of the input. $\endgroup$ Feb 29, 2016 at 4:23
-
$\begingroup$ @David Richerby, you might have hurriedly answer the question, logarithmic factor is $\log T(n)$, which is the length of the tape that is used. So your answer is incorrect. I have posted the correct answer. $\endgroup$ Feb 29, 2016 at 8:19
$\begingroup$
$\endgroup$
2
The logarithmic factor in efficiency of universal turing machine $O(C T(n)\log T(n))$ is to simulate $k$ working tapes in fixed number of working tapes of universal turing machine. It is not because of alphabet size, number of tapes, or number of states.
$C$ depends on $M$'s alphabet size, number of tapes, and number of states, but it is independent of $n$ (or $T(n)$), so it can be taken as $O(1)$. Also, we can not just take a very large number of tapes in universal turing machine and say that we will simulate on those tapes; for simple reason than the number of tapes in the simulated turing machine can be higher than whatever number we fix for universal turing machine.
We can simulate $k$ working tapes on a single working tape using $k$ tracks. Or may be $2k$ tracks if we want to keep heads and other markers on a separate track. We can keep the markers just using $k$ tracks also, if we spread out the input and use the in between spaces for markers, similar to what Alan Turing did in his celebrated paper.
In every step of simulation, for moving heads in multi track, we will have to go to and fro the whole tape, leading to a $O(T(n))$ overhead. This will give us $O(CT(n)^2)$ simulation time. There is a clever trick involved that lets us write on multitrack machine with $O(\log T(n))$ overhead. Instead of moving the $k$ heads on the multi-track machine we move the track contents under the head. Furthermore we keep a lot of intermediate special blank spaces on both sides of head in each track to allow us shifting the tape contents more efficiently. This allows us to simulate each step of the turing machine in amortized $O(\log T(n))$ time. Thus turing machine will be simulated in amortized $O(C T(n)\log T(n))$ time.
See the complexity theory book of Arora and Barak for details.
Arora and Barak uses 3+ tapes, one for input, one for output and a few as working tapes. But in fact we can use a single tape for all of these and still can simulate any turing machine on any input in $O(CT(n)\log T(n))$ time.
Furthermore, we still don't know if the extra $\log T(n)$ factor is unavoidable for sure, though most probably it is unavoidable. But we might be able to prove that we need $\omega(1)$ overhead. That is, we might be able to prove that we can not simulate every turing machine without any overhead.
answered Feb 29, 2016 at 8:16
-
$\begingroup$ I do not think you can simulate any multi-tape Turing machine with a single tape in $O(T \log T)$ time. First of all, PALINDROME needs $\Omega(n^2)$ time on a single-tape TM but can be solved in linear time on 2-tape TM. On the other hand, I think the simulation given by Arora-Barak requires at least two tapes too to at least keep track of the indices. $\endgroup$– MygodNov 17, 2020 at 2:26
-
$\begingroup$ So $T = \Omega(n^2)$, actually $O(n^2)$, and thus we can simulate in $O(n^2\log n^2)$ time ($T$ is not $O(n)$ in this case, if I am not wrong you have presumed this). And, really speaking, the $O(T\log T)$ simulation is really ingenious, not at all a naive solution. $\endgroup$ Jan 30, 2021 at 16:49