Recursive Universal Turing Machines

Let $U$ be a universal Turing machine that on input $$ simulates a Turing machine $M$ on input $w$. I have a question about what would happen if $U$ "operated" on itself.

That is, what happens when we consider the input $>$?

Or what about the input $>>$?

If we give the input $>$ to the Turing machine U, it will simulate the Turing machine U on input $$. The behavior of the simulated machine U on input $$ is to simulate the Turing machine $M$ on input $w$. So it seems like the behavior would still be a Turing machine that simulates $M$ on input $w$. At least two questions need further clarification:

• How is the input $w$ encoded? If we have a requirement that only input where "$$" are "perfectly matched" is allowed, then we can just copy the input "w" unmodified between $$. This is the strategy used by Tcl, which can be surprising if you are not used to it. Otherwise, you have to encode the input "$w$" suitably, which can mean that you have to escape "$$", as well as the escape character itself. In this case, the "$w$" in $>>$ is quite different from "$w$" itself, because it has been encoded multiple times. For example the escape character "\" might have turned into "\\\\\\\\".

• What exactly do we mean by "simulate"? The most important aspects of a simulation of a Turing machine is whether it halts or not. If the Turing machine M halts, it is (or can be) also important which output it leaves on its tape. If the machine M doesn't halt, we need to be careful how to define the output of the machine. For simplicity, let's assume that either the machine has a dedicated output tape, or that we don't care for the output in case the machine never halts. The output should never be encoded like the input, but directly match the original output.

What about the efficiency of the simulation? A good simulation would have only a constant offset in memory consumption and a logarithmic factor (logarithmic in the input to $U$) in runtime (->multi-tape Turing machine is assumed here). Both properties seem to be conserved by applying $U$ to itself, so you still have an efficient simulation of $M$ on input $w$ if you apply $U$ (repeatedly) to itself.

StackExchange Computer Science Q#18305, answer score: 3