2
$\begingroup$

I've been trying to figure out what it means for one thing to "simulate" another. For example, a universal Turing machine can "simulate" any other Turing machine. We might also say that two different cellular automata both "simulate" the sieve of Eratosthenes, despite having different rules.

To formalize my question, let's say that we have two Turing machines, $A$, $B$. What I'm looking for is some kind of formal proposition that checks whether or not $A$ simulates $B$. (I'm not specifying the input/output protocols of these machines. Choose whatever is most convenient.)

A failed first attempt (this is based off of a Quora article which explains how to define the notion of Turing completeness in a formal way):

To check whether or not $A$ simulates $B$, we would like to convert inputs for $B$ into inputs for $A$, and outputs from $A$ into outputs from $B$. For simplicity, assume that the input and output are both natural numbers. For $A$ to simulate $B$, we require that there exist computable functions $i:\mathbb{N}\to \mathbb{N}$ and $o:\mathbb{N}\to \mathbb{N}$ such that for all $n\in \mathbb{N}$:

  • $A$ halts when given $i(n)$ iff $B$ halts when given $n$.

  • If $B$ halts when given $n$, then $B(n) = o(A(i(n)))$

Why does this definition fail? Let $B$ to be a Turing machine that computes whether or not its input is a prime number. $B$ returns 1 for true, and 0 for false. Let $A$ be a Turing machine that returns its input, unaltered. Then according to my definition, A simulates B.

Proof: Let $i(n)=n$.

Let $o(n)=1$ if $n$ is a prime number and 0 otherwise.

Clearly, both $i$ and $o$ are computable. Also, both $A$ and $B$ always halt. So the first of our conditions is satisfied. Also, it is easy to check that $B(n)=o(A(i(n)))$. So the second condition holds, and $A$ simulates $B$. Q.E.D.

So, according to this definition of simulation, a Turing machine that literally does nothing other than return its input simulates a Turing machine that checks if its input is prime. Does anyone have a better definition?

EDIT: I edited this post to make the description of the Turing machines simpler. Originally I had unnecessarily complicated things by describing their inputs and outputs in terms of tape states.

$\endgroup$
11
  • 1
    $\begingroup$ If A halts immediately, what does it output? If 1 then would B always output 1, thus not recognize only primes. $\endgroup$
    – coffeemath
    Sep 30, 2018 at 21:53
  • 1
    $\begingroup$ I defined the output of my Turing machines to be the state of the tape when they halt. So $A$ is just a Turing machine that outputs its input. $\endgroup$ Sep 30, 2018 at 21:55
  • 1
    $\begingroup$ I'm confused, isn't it simply: Turing machine $A$ simulates $B$ iff $A(n)=B(n)$ whenever any of the sides is defined, and if one doesn't halt then the other doesn't halt? So a turing machine coded with bubble sort simulates merge sort? What is the intuitive definition of 'simulates'? $\endgroup$ Sep 30, 2018 at 22:53
  • 1
    $\begingroup$ As I understand it so far simulation is just 'being coded with the same algorithm'. Could you please give another simulation example using turing machines? $\endgroup$ Sep 30, 2018 at 23:42
  • 2
    $\begingroup$ This question is not answerable without more context. Some possibly relevant notions in computer science are "refinement" and "bisimulation". The term "simulation" is quite often used to describe a situation where one Turing machine mimics all the state changes of another Turing machine (this is a form of refinement and is the sense in which a universal Turing machine simulates every other Turing machine). The term "simulation" is not usually used to describe relations that only depend on the initial and final states of a computation. $\endgroup$
    – Rob Arthan
    Oct 1, 2018 at 21:31

0

You must log in to answer this question.

Browse other questions tagged .