Turing Machine Simulation

Turing machines are capable of simulation, that is, they can run other models of computation (including other Turing Machines). This method is used often when finding proofs of decidability for certain abstract computational problems, like the equivalence problem for finite state automata.

By the Church-Turing thesis, it is guaranteed that any effectively calculable (finite, specific, step-by-step procedure) can be simulated on a Turing Machine. Now to actually do the simulation requires more work:

1. Assume the algorithm/model to be simulated is called $O$. Also assume that we have the TM Encoding of $O$, given by $\langle O \rangl
2. Construct a multi-tape TM, $T$, that takes in $⟨O⟩$
3. First, ‘pre-process’ the input to ensure it is of the correct form.
   1. If $O$ is a computational model, this would ‘extract’ the transition function from other things, like the state register.
4. Then, use a work tape to store that initial configuration of $O$ (which is the start state)
5. Iteratively run $O$’s transition function on the work tape
6. Assuming $O$ halts, this simulating Turing Machine will always halt.

Examples §