Which Turing machine extensions broaden the power of the machine?

Question

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?

Answer 1

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)

Answer 2

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 ℵ₀, 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…