Non Turing Computing
Non Turing ComputingWhat on earth is NonTuringComputing? Is it intended to mean
If I may suggest a direction: there are some fundamentals to TuringMachines that are not true of all SignalProcessor?s. For example, the representation of state by the machine, rather than by the signal. -- PeterMerel
The discussion is better understood (and perhaps refactored) from the standard truism that a turing machine can simulate (slowly) absolutely any digital computer. (There's a small possibility that certain problems may even be better suited to the turing machine...)
As I've been reading recently, the above is not true... A turing machine is defined to only take input at the start of its run, and then it runs to completion (or non-completion, as the case may be). A growing number of people have been publishing about the limits of that sort of "single-computation" computer compared to one that accepts input along the way. Peter Wegner of Brown Univ argued in a refereed journal (CACM) that the latter can compute things that the Turing machine can't. I've seen additional authors of this view since then. The point being, that a Turing machine has a particular sort of limitation that distinguishes it from, say, biological cells, which interact with their surroundings. This point of view may affect the correctness of the paragraphs that follow. -- AlistairCockburn
That's absurd; if you want incremental output from a Turing Machine, just have it reach completion periodically with an output value which encodes enough information to 'restart' the computation immediately thereafter. Keep feeding the machine's output back in to itself, gleaning bits of the answer each time. -- AdamMegacz
(Hi, Adam, you seem to have misread... the previous para said "input", not "output")
Anyway, a large enough digital computer can also simulate any actual turing machine with a fairly trivial program.
One could give the Turing Machine three tapes (equivalent to one tape): one is the conventional working tape, the other is a "write-only" tape on which the head is constrained to move right one square every time it writes a symbol, and the third is a "read-only" tape on which the head is constrained to move right one square every time it reads a symbol. Incremental output and input: every now and then the machine's instructions might see it reading something from the read-only tape, or writing something to the write-only tape. The two tapes could be referred to, respectively, as stdout and stdin). The contents of the third tape (or interleaved squares in the equivalent one-tape model) could be anything until such time as the machine reads it - just because we know what it says is irrelevant: many many things about the physical world exist right now that we don't know about, but once we do we'll no doubt be going around saying that we learned them.
Therefore, what people are really talking about here is the question of computability in the digital paradigm. In a sense, the question is "Does there exist the (possibly unwritten) computer program to perform interesting task FOO?". This makes the whole thing easier to think about.
Then there are those comments concerned with the cost of computation. Obviously a real turing machine is outrageously impractical for virtually any task. However, some tasks are better done not by computer, and some tasks just can't be done by digital computer. Assembling chickens from atoms is currently one of them. I anticipate that task to be the sole domain of chickens for quite some time.
There's an article about NonTuringComputing at http://www.techreview.com/currnt.htm (better reference?)
There are many kinds of computation that differ from those modeled by a Turing machine. Consider analog computers, neural nets, protein regulation, quantum computing to name a few. Tempers only flair when one is argued to be faster than another.
This is an incorrect use of terminology. These are "non-von-Neumann" models of computation, not "non-Turing" (with the probable exception of quantum computing). In the real world, analog computers do not have infinite accuracy, so they can be simulated on Turing machines. It is however true that a theoretical infinitely accurate analog computer could be non-Turing, but even then it would have to use Lukasiewicz logic to be so. Ordinary analog computers, of the sort that once were widely used commercially, are not even as powerful as Turing machines.
And as for neural nets and protein/DNA/RNA computing, they are simulated exactly on ordinary computers all the time. They are interesting in a number of ways, e.g. DNA computing can, in theory, be considerably faster than von Neumann architectures. But they are no more powerful, in the theoretical sense, than Turing machines: Turing machines can simulate them in a finite number of steps. That's the defining issue. It doesn't matter how many finite steps the simulation takes.
Even quantum computing is a big question mark. It is widely agreed that they might be more powerful than Turing machines, but not that they definitely will be, because there are foundational issues in quantum physics at stake that we are not 100% sure of. -- DougMerritt
OK, perhaps these need to be moved to a page where we discuss things that are Turing machines, and yet are NonVonNeumann? architectures. Perhaps combine with the list at VonNeumannArchitecture. -- DavidCary
EditText of this page
(last edited November 29, 2005)
or FindPage with title or text search