1
$\begingroup$

I read a previous question, Is a secondary TM sufficient to detect all loops?, which asks if there is a TM1 that takes the description and input of any other TM2 to detect if TM2 will loop for the input.

One answer was to run two copies of TM2, the second at 1/2 the speed.If the second machine ever reaches the same configuration as the first, a loop was detected. Seems to me that the process requires a third entity to do the comparison at every step. Since neither copy output their complete configuration, it is not obvious this third entity and the complete system of all three entity can be a TM. Another easy way is for a second TM2 to keep a list of all configuration of TM1 and check to if there any repeats. This can surely work. But again, what is not obvious is if this complete system of the checking process on TM2, the running of TM1 and outputting TM1's complete state configurations to TM2 can be realized as a TM. TM1 can't output its own states to TM2, so TM2 somehow has to grab these from TM1, not just its output but TM1's complete state information or there has to be a third entity that does the communication.

My question: Can this process be implemented as a Turing machine?

$\endgroup$
1
$\begingroup$

I think you're wondering how one Turing machine can keep track of what another Turing machine is doing, including checking that machine's state and knowing what's on its tape. After all, Turing machines don't have a method for "outputting" a description of what they're doing—they merely run.

But a Turing machine that takes in a description of another Turing machine can simulate that second machine on its tape, the same way that you can simulate running a TM using pencil and paper. The TM writes down the current configuration of the simulation, including what the simulated current state is, what the second machine's tape says, and where the machine's tape head is. It follows rules for moving the tape head, writing to the simulated tape, and changing the simulated current state.

That's how one machine can simulate another. Another helpful trick is that a TM can have any finite number of tapes without affecting its capabilities—a three-tape TM is no more powerful than a one-tape TM. So if it's conceptually helpful, you can give the TM a separate tape for each concurrent simulation.

$\endgroup$
  • $\begingroup$ Thanks. Your answer highlighted my question. In your statement "But a Turing machine that takes in a description of another Turing machine can simulate that second machine on its tape", there are three TMs involved, the original TM, the one "taking" the description and the one that the description was put on as input to simulate the original one. My question is how do you know that the "taking" can be done by a TM? It is assumed to be there and it is a TM. As a matter of fact, it is humans that are assumed to "take" the description of one TM and put as input to the second TM. $\endgroup$ – Jerry Mar 23 '18 at 12:37
  • $\begingroup$ Actually, there are only two machines. The first machine is a universal TM. When it runs with the description of a second TM on its tape, it steps through a simulation of that second TM. Exercise: how would you completely describe a TM in symbols? Exercise: Define the transition function for a TM that simulates another TM's description. $\endgroup$ – user326210 Mar 23 '18 at 16:26

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.