2

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.

Ricky Tensor
  • 1,221
  • 7
  • 10
  • 1
    If A halts immediately, what does it output? If 1 then would B always output 1, thus not recognize only primes. – coffeemath Sep 30 '18 at 21:53
  • 1
    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. – Ricky Tensor Sep 30 '18 at 21:55
  • I was thinking that the Turing machines would each have a single tape. In the input phase the tape is initialized to the value of the input. The the Turing machine runs. Then, after the machine halts (if it halts), the output of the machine is just the final state of its tape. In retrospect, this was kind of a confusing thing for me to do. Since it doesn't really matter, I'll edit the post so that the machines just input and output natural numbers, and $A$ just outputs its input. – Ricky Tensor Sep 30 '18 at 22:08
  • 1
    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'? – Fernando Chu Sep 30 '18 at 22:53
  • @Ryunaq The intuitive idea is that there ought to be some kind of isomorphism between the steps of the two computations. (Maybe not a literal isomorphism.) Ideally, a Turing machine using bubblesort does not count as a simulation of one using mergesort, since the algorithms involved are different. (The definition I have given above fails to distinguish them, which is another problem with it.) That being said, if there's any standard definition for what "simulates" means in the field of theoretical comp-sci, I'd be happy to know what it is. – Ricky Tensor Sep 30 '18 at 23:30
  • 1
    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? – Fernando Chu Sep 30 '18 at 23:42
  • I echo @Ryunaq s query, and am still confused about what you mean by equivalent Turing machines. – coffeemath Oct 01 '18 at 01:38
  • I'd say that the idea of "simulation" is fairly close to "being coded with the same algorithm". There are, however, many different Turing machines that we would recognize as performing Bubblesort, hence the need for some kind of formal definition. (I don't think that "simulates" is an equivalence relation, though. One Turing machine could be doing extra computational work, as well as simulating another, so the relation would only go one way.) – Ricky Tensor Oct 01 '18 at 02:57
  • I'm not sure such a general notion of simulating can be done. The distinction between two different algorithms for solving a problem (e.g. bubble sort and merge sort) is not mathematically clear. Take for example an algorithm that does one step of bubble sort and then another one of merge sort, or genarally, n steps of bubble sort and then m steps of merge sort until it halts (let's call it $A(n,m)$). Sure, $A(a,b)$ can be distinguished from $A(c,d)$ but only because I defined $A(x,y)$ beforehand........ – Fernando Chu Oct 01 '18 at 03:34
  • .....A really general notion of simulation that can distinguish between our intuitive ideas of what an algorithm does must then classify every single algorithm at the same time. This, in theory, should be possible, but the main constraint on this classification is not a mathematical one, but an intuitive one. Hence, it seems it couldn't be done, unless there is some innate algorithm-classifier algorithm that we unconsciously use. – Fernando Chu Oct 01 '18 at 03:35
  • 2
    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. – Rob Arthan Oct 01 '18 at 21:31

0 Answers0