3
$\begingroup$

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?
Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Martin Berger
    Jan 8, 2021 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – QuantumAI
    Jan 10, 2021 at 22:01
  • $\begingroup$ 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). $\endgroup$
    – Martin Berger
    Jan 10, 2021 at 23:14
  • $\begingroup$ I think the RAM model of computation 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. $\endgroup$
    – Martin Berger
    Jan 10, 2021 at 23:16

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Martin Berger
    Jan 11, 2021 at 14:21

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.