# Formal definition of one Turing machine simulating another

Here on Wikipedia is says "In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input". I would like to know what the formal definition of 'simulate' is in reference to the formal definition of Turing machine given here. I have been unable to find such a formal definition on either Wikipedia page, or in the textbook Introduction to Automata Theory, Languages, and Computation 3rd Edition by John Hopcroft.

I would expect that such a formal definition would be something like the following:

Consider TMs (Turing machines) $$M_i=\langle Q_i,\Gamma_i ,b_i,\Sigma_i ,\delta_i ,q^0_i,F_i\rangle$$ for $$i=1,2$$
We say $$M_1$$ can simulate $$M_2$$ on arbitrary input if there exist computable functions $$f:\Sigma_2^*\to\Sigma_1^*$$ and $$g:\Sigma_1^*\to\Sigma_2^*$$ such that if $$M_2$$ halts on an input string $$\omega\in\Sigma_2^*$$ then $$M_1$$ halts on $$f(\omega)$$. Mover over, if $$\gamma$$ is the state of the tape of $$M_1$$ after having started at state $$f(\omega)$$, then $$M_2$$ when started on input state $$\omega$$ should halt with state $$g(f(\omega))$$.

This definition above may in fact not be quite right for one reason or another, so ideally I'd like to know what the generally accepted definition is. In the definition I give above, I hope to capture the idea that one Turing machine simulates another when one can encode the inputs of the simulated machine as inputs to the simulator and vice versa.

If any of this question is unclear, please point out where I can clarify so that I might improve the understandably of the question.

Also, I'd like to point out that my question is quite similar to this unanswered stack exchange question, however I personally think my question is sufficiently different that it does not qualify as a duplicate. If you disagree, please let me know how I can proceed to contribute to this old question so that it might get answered. Thanks for the help.

To further clarify my question, what I would like to do is express the concept of 'simulate' as a homomorphism in the category of Turing machines. Also I would like the definition of 'simulate' (homomorphism) to be as rigorous as possible so, for example, simply stating as wikipedia does that:

"U is supplied with the tape on the beginning of which is written the string of quintuples separated by semicolons of some computing machine M"

Is not as rigorous as I would like. This requires a particular mapping that takes sets such as $$Q_i,\Gamma_i,b_i$$ etc into the set of strings.

More broadly, what I would like is a mathematical treatment of Turing machines, and automata in general, that defines concepts such as 'simulates' and 'reduction' and so on as homomorphisms, between objects in the category of Turing machines. Ideally I'd like to find a textbook that provides such a treatment, or if no such book exists, some published literature.

• I think you mean $M_2$ halts with state $g(\gamma)$? A $U$ which can simulate any arbitrary TM will need some mapping which depends on $Q_i, \Gamma_i, \ldots$; the Wikipedia statement implicitly claims that such injective mappings exist. But a problem with this attempt at definition: if $M_2$ halts on an input, then its final state is computable, so an $M_1$ which does nothing qualifies as long as $g \circ f$ maps every halting input to the corresponding final state. That should hardly count as a "simulation". Nov 1, 2022 at 2:30