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.
Best Answer
For a formal construction of a Universal Turing Machine, you might look to this paper of Hennie and Stearns (https://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf). They formally construct a one-tape Turing machine that can efficiently simulate multi-tape machines. This machine is very useful for the study of Computation Complexity Theory. If the paper is rough, you may look at sections 1.4 and 1.7 of Arora and Barack’s book “Computational Complexity”
As for the Turing Machines as homomorphisms question, you might be interested in the following book. I can’t promise it will answer all of your questions exactly, but it definitely gets at a similar categorical perspective. https://www.cambridge.org/core/elements/abs/theoretical-computer-science-for-the-working-category-theorist/5F3499D1F326D2D77567AA1041627699