In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows:

"On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to simulate the execution of $M_x$ on $x$." Here $M_x$ is the machine encoded by string $x$.

Since we are simulating another TM on $D$, this would implicitly make $D$ a universal TM, right? If this is the case, then why is it necessary to state that $D$ will simulate $\mathcal{U}$ in order to simulate $M_x$ when $D$ is already capable of simulating $M_x$ directly?

On the other hand, if it is not the case that $D$ is a UTM, then why can't we "run" (whatever that means) $M_x$ directly on $x$ instead of running $M_x$ through $\mathcal{U}$ (in the same way that we "run" $\mathcal{U}$)? Why do we need to simulate a machine capable of simulating an arbitrary TM if we only need to simulate exactly one TM?


The difference between $\mathcal{U}$ and $M_x$ is that $\mathcal{U}$ can be hardcoded while $x$ is an input to the machine.

In other words, when Arora and Barak write "run $\mathcal{U}$ to simulate $M_x$", what they mean is to switch to a part of the Turing machine which behaves like $\mathcal{U}$ (you can think of it as a function), and afterwards switch to some other part of the machine. The states of $\mathcal{U}$ do the work of simulating $M_x$.

You are not simulating $\mathcal{U}$. You incorporate its code as part of your Turing machine. (In programming languages, this is sometimes known as inlining.)

| cite | improve this answer | |
  • $\begingroup$ Makes much more sense, thank you. It's strange that they don't mention this explicitly anywhere in the sections on Universal simulation. $\endgroup$ – kotu Jun 10 '19 at 20:21

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.