<p>First, let's clearly settle what it means for a Turing Machine to compute a function.</p>
<p>Any specification of a deterministic TM <span class="math-container">$M$</span> implicitly defines, for each word <span class="math-container">$w \in \Sigma^*$</span>, a (possibly infinite) sequence of configurations of <span class="math-container">$M$</span> when run on <span class="math-container">$w$</span> (the machine is said to <em>halt</em> if this sequence is finite). A configuration consists of the state of the TM, the position of its head, and the contents of its tape. This, in turn, defines a function
<span class="math-container">$$f_M: \Sigma^* \to \Sigma^* \uplus \{\bot\}$$</span>
that the machine computes: for a word <span class="math-container">$w \in \Sigma^*$</span>, if the sequence of configurations of <span class="math-container">$M$</span> when run on <span class="math-container">$w$</span> is finite, the function value <span class="math-container">$f_M(w)$</span> is the word <span class="math-container">$v$</span> that is on the tape in the last configuration of that sequence, and if the sequence is infinite, we set <span class="math-container">$f_M(w) = \bot$</span> (indicating that <span class="math-container">$M$</span> does not halt on input <span class="math-container">$w$</span>).</p>
<p>Next, we need to recognize that TMs themselves can be encoded as words over <span class="math-container">$\Sigma^*$</span>. Let's assume for simplicity that every word <span class="math-container">$w$</span> describes a TM <span class="math-container">$M_w$</span>. Also, define for each TM <span class="math-container">$M$</span> the set of words that encode <span class="math-container">$M$</span>, i.e.
<span class="math-container">$$ \operatorname{enc}(M) = \{w \in \Sigma^* \mid M_w = M\}.$$</span>
Further, pairs of words <span class="math-container">$(w, v) \in \Sigma^* \times \Sigma^*$</span> can be canonically encoded as a single word <span class="math-container">$u \in \Sigma^*$</span> - denote this word by <span class="math-container">$\langle w, v \rangle$</span>.</p>
<p>And now we're ready to rigorously define what we mean when we say that TMs simulate other TMs. We say that a TM <span class="math-container">$M$</span> simulates another TM <span class="math-container">$M'$</span>, if for all <span class="math-container">$w \in \operatorname{enc}(M')$</span> and all words <span class="math-container">$v \in \Sigma^*$</span>,
<span class="math-container">$$f_M(\langle w, v\rangle) = f_{M'}(v).$$</span>
That is, given any description of <span class="math-container">$M'$</span>, and an input <span class="math-container">$v$</span>, <span class="math-container">$M$</span> outputs exactly what <span class="math-container">$M'$</span> would output, and if <span class="math-container">$M'$</span> doesn't halt, then <span class="math-container">$M$</span> also doesn't halt.</p>
<p>A universal TM is a machine that simulates all other machines, in the following sense: A TM <span class="math-container">$M$</span> is called <em>universal</em>, if for every pair <span class="math-container">$(w, v) \in \Sigma^* \times \Sigma^*$</span>,
<span class="math-container">$$f_M(\langle w, v \rangle) = f_{M_w}(v).$$</span>
That is, given any description <span class="math-container">$w$</span> of a Turing machine <span class="math-container">$M_w$</span>, and an input <span class="math-container">$v$</span> for that machine, <span class="math-container">$M$</span> outputs exactly what <span class="math-container">$M_w$</span> would output when run on <span class="math-container">$v$</span>, and if <span class="math-container">$M_w$</span> doesn't halt, then <span class="math-container">$M$</span> also doesn't halt.</p>
<p><strong>Edit:</strong> Restructured answer to make it more readable.</p>

CC BY-SA 4.0
2021-01-11T14:21:55.320Z
Note that this notion of simulation treats Turing machines are devices defining a *function*, i.e. a deterministic input/output relation (with non-termination being a special form of output). This is fine, but there are other cases, where this is not fine-enough a notion of simulation, e.g. for optimising compilers, or in computer security (think: side-channel attacks which is not a concept that makes sense when computation is seen as an input/output relation). In such cases, different notions of simulation need to be used.
Martin Berger
CC BY-SA 4.0
2021-01-10T22:31:17.767Z
2021-01-10T23:11:27.860Z
2021-01-10T23:11:27.860Z
Silence of the Lemma
<p>Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They introduce one particular Universal Turing Machine and explain how it simulates other Turing Machines. But does there exist a rigorous theory/formalization behind simulations of Turing machines? Particular questions that I care about:</p>
<ul>
<li>Given two Turing machines T and T', when can it be said that T simulates T'?</li>
<li>Is there a theory of &quot;shortcuts&quot; in simulations of Turing machines?</li>
<li>A random google search revealed the notion of <em>Simulation preorder</em>, see e.g.:
<a href="https://en.wikipedia.org/wiki/Simulation_preorder" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Simulation_preorder</a>
Does something similar exist for Turing machines?</li>
</ul>

CC BY-SA 4.0
2021-01-08T17:48:29.280Z
There is not just one concept of how two computations can be
equal. Turing machines are not a good formalism to study for this question, since
the formalism itself doesn't not suggest any obvious notions of
equality. I recommend looking at a more algebraic model of
computation, such as $\lambda$-calculi or $\pi$-calculi;. Most
conventional programming languages take some variant of equality of
traces of memory reads and memory writes as notion of equality
(details are subtle). By the Church-Turing thesis all those equalities can be recovered for Turing machines, but details are messy.
Martin Berger
CC BY-SA 4.0
2021-01-10T22:01:01.127Z
Thanks for your answer! I agree that Turing machines can get quite involved for a rigorous and general formalization of simulation. However, Turing machines are a rather natural or practical model of computation, that is why I try to focus on them.
QuantumAI
CC BY-SA 4.0
2021-01-10T23:14:44.753Z
TMs are not more natural and practical than other models. Unlike most other notions of computation, there is no natural algebra of programs, you construct TMs as on 'blob', rather than from smaller parts.  This becomes a problem when you want to reason about more complicated forms of computation such as parallelism. In more algebraic formulations of programming, you can define equality and simulation using contexts, e.g. $P \cong Q$ iff for all one-holed contexts $C[.]$ we have $C[P] \cong C[Q]$ (there are natural ways of removing the circularity).
Martin Berger
CC BY-SA 4.0
2021-01-10T23:16:05.593Z
I think the [RAM model of computation](https://en.wikipedia.org/wiki/Random-access_machine) is much more natural, if you are interested in modelling normal (sequential) programming languages. But 'natural' depends on your background knowledge and also what you are trying to model.
Martin Berger
<turing-machines><universal-turing-machines>
Formalization of simulation for Turing machines
QuantumAI
# Formalization of simulation for Turing machines

(Asked by: username_0 on 2021-01-07)

Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They introduce one particular Universal Turing Machine and explain how it simulates other Turing Machines. But does there exist a rigorous theory/formalization behind simulations of Turing machines? Particular questions that I care about:

* Given two Turing machines T and T', when can it be said that T simulates T'?
* Is there a theory of "shortcuts" in simulations of Turing machines?
* A random google search revealed the notion of *Simulation preorder*, see e.g.:
  <https://en.wikipedia.org/wiki/Simulation_preorder>
  Does something similar exist for Turing machines?

**Tags:** turing-machines, universal-turing-machines

> **Comments:**
> **username_1**: There is not just one concept of how two computations can be equal. Turing machines are not a good formalism to study for this question, since the formalism itself doesn't not suggest any obvious notions of equality. I recommend looking at a more algebraic model of computation, such as $\lambda$-calculi or $\pi$-calculi;. Most conventional programming languages take some variant of equality of traces of memory reads and memory writes as notion of equality (details are subtle). By the Church-Turing thesis all those equalities can be recovered for Turing machines, but details are messy.  
> **username_0**: Thanks for your answer! I agree that Turing machines can get quite involved for a rigorous and general formalization of simulation. However, Turing machines are a rather natural or practical model of computation, that is why I try to focus on them.  
> **username_1**: TMs are not more natural and practical than other models. Unlike most other notions of computation, there is no natural algebra of programs, you construct TMs as on 'blob', rather than from smaller parts.  This becomes a problem when you want to reason about more complicated forms of computation such as parallelism. In more algebraic formulations of programming, you can define equality and simulation using contexts, e.g. $P \cong Q$ iff for all one-holed contexts $C[.]$ we have $C[P] \cong C[Q]$ (there are natural ways of removing the circularity).  
> **username_1**: I think the [RAM model of computation](https://en.wikipedia.org/wiki/Random-access_machine) is much more natural, if you are interested in modelling normal (sequential) programming languages. But 'natural' depends on your background knowledge and also what you are trying to model.  

---

## 1 answers

### Answer by username_2 on 2021-01-10. Score: 2

First, let's clearly settle what it means for a Turing Machine to compute a function.

Any specification of a deterministic TM $M$ implicitly defines, for each word $w \in \Sigma^\*$, a (possibly infinite) sequence of configurations of $M$ when run on $w$ (the machine is said to *halt* if this sequence is finite). A configuration consists of the state of the TM, the position of its head, and the contents of its tape. This, in turn, defines a function
$$f\_M: \Sigma^\* \to \Sigma^\* \uplus \{\bot\}$$
that the machine computes: for a word $w \in \Sigma^\*$, if the sequence of configurations of $M$ when run on $w$ is finite, the function value $f\_M(w)$ is the word $v$ that is on the tape in the last configuration of that sequence, and if the sequence is infinite, we set $f\_M(w) = \bot$ (indicating that $M$ does not halt on input $w$).

Next, we need to recognize that TMs themselves can be encoded as words over $\Sigma^\*$. Let's assume for simplicity that every word $w$ describes a TM $M\_w$. Also, define for each TM $M$ the set of words that encode $M$, i.e.
$$ \operatorname{enc}(M) = \{w \in \Sigma^\* \mid M\_w = M\}.$$
Further, pairs of words $(w, v) \in \Sigma^\* \times \Sigma^\*$ can be canonically encoded as a single word $u \in \Sigma^\*$ - denote this word by $\langle w, v \rangle$.

And now we're ready to rigorously define what we mean when we say that TMs simulate other TMs. We say that a TM $M$ simulates another TM $M'$, if for all $w \in \operatorname{enc}(M')$ and all words $v \in \Sigma^\*$,
$$f\_M(\langle w, v\rangle) = f\_{M'}(v).$$
That is, given any description of $M'$, and an input $v$, $M$ outputs exactly what $M'$ would output, and if $M'$ doesn't halt, then $M$ also doesn't halt.

A universal TM is a machine that simulates all other machines, in the following sense: A TM $M$ is called *universal*, if for every pair $(w, v) \in \Sigma^\* \times \Sigma^\*$,
$$f\_M(\langle w, v \rangle) = f\_{M\_w}(v).$$
That is, given any description $w$ of a Turing machine $M\_w$, and an input $v$ for that machine, $M$ outputs exactly what $M\_w$ would output when run on $v$, and if $M\_w$ doesn't halt, then $M$ also doesn't halt.

**Edit:** Restructured answer to make it more readable.

> **Comments:**
> **username_1**: Note that this notion of simulation treats Turing machines are devices defining a *function*, i.e. a deterministic input/output relation (with non-termination being a special form of output). This is fine, but there are other cases, where this is not fine-enough a notion of simulation, e.g. for optimising compilers, or in computer security (think: side-channel attacks which is not a concept that makes sense when computation is seen as an input/output relation). In such cases, different notions of simulation need to be used.  

---

