0
$\begingroup$

Related to my answer on this question, I'm not sure of a detail.

Assume you have a Turing Machine which simulates all possible Turing Machines all at once (meaning it does not "page" its data, i.e. it can't erase data from one "process" to write data from another "process"; it must keep all "processes" "in memory" at the same time). Then, this Turing Machine must simulate itself, because it is a Turing Machine and the definition of this machine is that it simulates all possible Turing Machines. It must also simulate the simulation of itself, and the simulation of that, and so on, infinitely recursive. Therefore, this Turing Machine must have infinite data on its tape.

My question is, can this Turing Machine exist, and why or why not?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

Your conclusion "this Turing Machine must have infinite data on its tape" is not accurate. Everything up to that point is basically fine, but that one statement is not correct.

Turing machines never have an infinite amount of data on the tape at any one time. At any point in time, they have a finite amount of data on the tape. However, this amount might increase over time without limit. That's not the same as saying that at any point the amount is infinite.

An analogy: imagine I start counting out loud 1, 2, 3, 4, 5, 6, etc., without ever stopping. At any point in time, the number I said aloud is finite. However, there is no fixed upper bound on these numbers; they increase without limit.

It's the same with such a Turing machine. Call this machine $M$. It simulates all Turing machines in parallel, but crucially, each simulation proceeds at a reduced speed. $M$ itself will be one of the machines being simulated, but at a reduced speed: say, 1000x slower (just to make up a number). So, $M$ is simulating $M$ running 1000x slower. That means it is also recursively simulating $M$ running 1000000x slower, and so on. (And because the simulated $M$ is running slower, it writes to the tape more slowly, so the size of the tape grows slower.)

Improve this answer
$\endgroup$
11
  • $\begingroup$ Right, and the point that "Turing machines never have an infinite amount of data on the tape" is the point. Unless I'm missing something (in which case please enlighten me), in order to simulate every possible Turing machine, then either the tape must contain a description of every possible Turing machine at the same time (thus using infinite data on the tape as there are an infinite number of possible Turing machines), or it must rewrite some amount of the description of one machine with the description of another. $\endgroup$
    – Ertai87
    Apr 17, 2020 at 19:53
  • $\begingroup$ The former situation is impossible, as it would use infinite data, and the latter is also impossible, as it breaks the rules on "paging" as laid out in my original question. Therefore my question: Is the setup as suggested possible? $\endgroup$
    – Ertai87
    Apr 17, 2020 at 19:53
  • 3
    $\begingroup$ @Ertai87, I suggest reading about dovetailing and how it works. For your specific examples, dovetailing has the following property: every machine is eventually simulated. That's good enough. There's a perfectly reasonable sense in which it is true that there exists a Turing machine that simulates every other Turing machine in parallel. (There may also be a sense in which that is false, but I'm not taking a position on that.) Dovetailing is an example of why. $\endgroup$
    – D.W. ♦
    Apr 17, 2020 at 20:47
  • 3
    $\begingroup$ In my analogy, the equivalent is saying: every number is eventually written. For every $n$, there exists a time $t$ at which $n$ is on the tape. If you switch the order of the quantifiers -- there exists a time $t$ at which for every $n$, $n$ is on the tape -- then you get something false, but that's ok. It doesn't take away from what is true. $\endgroup$
    – D.W. ♦
    Apr 17, 2020 at 20:47
  • 2
    $\begingroup$ Personally, I'm not eager to get into a debate over what counts as "simulate every other Turing machine". Dovetailing is what it is, and it has whatever properties it has. How you define that phrase doesn't change what is and isn't true. $\endgroup$
    – D.W. ♦
    Apr 17, 2020 at 20:50
4
$\begingroup$

What you describe is a standard technique in computability theory called dovetailing. At each step of execution, dovetailing only requires a finite amount of data to be stored on the tape.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.