Science Fair Project Encyclopedia
Turing equivalence
Turing equivalence, in the theory of computation, describes a computing device capable of performing the same computations as a Turing machine. Such a device is termed Turing equivalent. Here the same computations has a technical meaning, but in essence it means that both machines are equally useful, looking only at the results they produce.
A Turing machine is a reference for what is deterministically computable, and what is not. If a problem is computable with a (modern high-performance) computer, which is Turing equivalent, then it is also computable with a Turing machine. This is slightly misleading, though, since a Turing machine, while primitive, is assumed to have unlimited memory, which is true of no machine in the real world.
Last updated: 05-27-2005 01:54:46
12-03-2008 10:22:39
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details