Non Turing Model Of Computation

From NonTuringComputing:


Ideas:


Could a computational scheme be different from and not comparable in its capabilities with respect to complexity with a TuringMachine? Is it known that there are no ModelsOfComputation that can not be compared in expressive power with the TuringMachine / LambdaCalculus / whatever? In more concrete terms, could aliens arrive here using, for the tasks to which we apply devices that are comparable in power to Turing machines, devices that we wouldn't even be capable of recognising as a computer, if we were handed one and not told what it was for? -- KeithBraithwaite

Previous answer: Logically, there could be no such thing. If you could state that "scheme X" is not comparable to a TuringMachine, you immediately have a point of comparison to a TuringMachine (that is comparability to a TuringMachine--clearly Turing machiens are comparable to themselves). The only way, I suppose, would be to compare a TuringMachine to something outside of its class, like an "umbrella," say. Since a TuringMachine is a "computational scheme," any "computational scheme" is comparable to it. -- SunirShah

Not so fast, young man. My loose use of language is at fault here. I've re-written the question to hopefully be clearer.

There are plenty of NonTuringModelOfComputations. A flower is one. InfiniteStateMachines, C-Machines no less. The only reason we don't think of a flower as a computer is we're interested in computing things flowers don't usually compute ...


EditText of this page (last edited June 30, 2004) or FindPage with title or text search