3

Of all the Turing machine extensions there are (such as two-way infinite tape, RAM, multiple read/write heads, and nondeterminism), do any of them allow the TM to decide problems that were previously undecidable?

2
  • 1
    Beware! There be (mathematical) dragons in this area! Apr 30, 2013 at 19:44
  • 1
    You should have a look at (Church's Turing Thesis)[en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis]. In analogy to this thesis there is a postulate that every reasonable machine model can be simulated on a Turing machine with a constant factor of memory overhead and polynomial time overhead. This postulate excludes the RAM machine model with pointer arithmetic as a reasonable machine model. May 1, 2013 at 11:50

2 Answers 2

6

Two-way infinite tape does not stretch the computing power. RAM changes the processing speed in some situations but not the computing power. Multiple read/write heads can be used to simulate a non-deterministic Turing machine (NDTM) but still do not improve on its computing power.

Thus, no, no new problems can be solved with those adjustments, but computational speed can be altered sometimes.

You can reduce any of those additional enhancements to a simpler Turing machine within a finite amount of steps and vice versa. However, two-way infinite tape is the standard model for a TM, I believe.

(While we're on the topic of extensions to basic TMs, have a look at Quantum TMs, which still don't solve new problems as far as I can tell: http://en.wikipedia.org/wiki/Quantum_Turing_machine)

3
  • 1
    Great answer. The gist of it is that all these "extensions" may make programming the Turing machine easier or the computation faster, but they do not allow the machine to solve any problem it couldn't previously solve. The proof is simple: any such extension would, by definition, be possible to implement as a TM itself. Therefore, you could chain a number of non-extended Turing machines to get the semantics of the extended machine. Apr 30, 2013 at 19:25
  • @Nikbougalis Exactly. There are some tools at jflap.org that can be used to play around with TMs and infinite tape, and NDTMs can both be simulated there. I highly recommend it for students of computational theory. Apr 30, 2013 at 19:28
  • In addition, there should be one of these Turing Machines at every University. Apr 30, 2013 at 19:31
1

The standard Turing Machine model — finite automaton with bidirectionally-unbounded tape — can simulate any finite storage model. Indeed, I think you'll find that it can simulate any countably-infinite storage model too; it might take a long time to process, but it can be done.

Thus, in order to find a true extension to the TM that goes genuinely beyond what is there, we need to get exotic and we need to look at the other half of the system: the finite automaton. The most obvious extension would be to make the automaton itself infinite, i.e., to give it an infinite number of states, an infinite program. The downside of that is that it makes your brain hurt! It's quite possible in that case that you might end up with a system where the number of overall states exceeds ℵ0, i.e., not only is there an infinite system but you no longer precisely know what state you're in at all.

A saner extension is to change the definition of termination, so that a machine is said to “terminate” if it visits a particular set of (overall) states infinitely often rather than entering a special stop state. Conceptually, that's rather like an ω-regular expression, which is defined even when matching over infinite strings, and it is quite clear that such a system would not necessarily be fazed by the simple versions of the halting problem that the classical TM can't handle (it would be able to spot the nasty looping behavior), though there would still be programs that it couldn't analyze (as we know from the application of the theorem of Gödel to computation). However, what this actually means in practice I don't know; an ω-extended TM is still quite a strange theoretical construct, and its very oddness should warn us that it is beyond computation as we know it.

Well, probably. I'm not sure that a TM couldn't simulate such a system…

3
  • It seems like you are describing a TM that is just like a TM in every way other than that it can solve the Entscheidungsproblem, which makes it utterly unlike a TM! +1 Apr 30, 2013 at 20:32
  • It solves a particular type of halting problem — the simple version that the classical TM can't handle — but there must still be a possible construction of further halting problems that are unsolvable (which is my point about Gödel-incompleteness). Maybe the infinite program TM could handle those, but it would still be possible to construct even further unsolvable problems. The whole point of Gödel's work is that there can't be a last word in solvability; there's always another problem beyond, another axiom to accept or deny. May 1, 2013 at 8:30
  • What would be a "simple version" of the halting problem? Can you point me (and any curious Google viewer) to a link? May 1, 2013 at 13:39

Your Answer

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

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