Turing Machine: Difference between revisions
Jump to navigation
Jump to search
imported>Eric M Gearhart (added blurb about Alan Turing) |
imported>Warren Schudy (See talk page) |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
The device does not necessarily have to be intentionally designed to compute or be a computer; if a device, piece of software or even an abstract concept meets the criteria it is | == Turing Completeness == | ||
A device that can simulate any Turing Machine is called '''Turing complete'''. The device does not necessarily have to be intentionally designed to compute or be a computer; if a device, piece of software or even an abstract concept meets the criteria it is Turing complete. | |||
Even software that is only used as a teaching tool or exist only as a concept, not as an implementation (such as [[Donald Knuth|Donald Knuth's]] MMIX<ref name=MMIX> {{cite web | url=http://www-cs-faculty.stanford.edu/~knuth/mmix.html | Even software that is only used as a teaching tool or exist only as a concept, not as an implementation (such as [[Donald Knuth|Donald Knuth's]] MMIX<ref name=MMIX> {{cite web | url=http://www-cs-faculty.stanford.edu/~knuth/mmix.html | ||
| Line 10: | Line 11: | ||
==References== | ==References== | ||
Revision as of 18:55, 1 January 2008
Turing Completeness
A device that can simulate any Turing Machine is called Turing complete. The device does not necessarily have to be intentionally designed to compute or be a computer; if a device, piece of software or even an abstract concept meets the criteria it is Turing complete.
Even software that is only used as a teaching tool or exist only as a concept, not as an implementation (such as Donald Knuth's MMIX[1] can be considered "Turing complete," in a completely abstract sense.
The name "Turing machine" and the concept known as "Turing completeness" are both derived from noted mathematician and computer scientist Alan Turing.
References
- ↑ Donald Knuth. Knuth: MMIX. Retrieved on 2007-11-10.