Turing Machine: Difference between revisions
imported>Sandy Harris No edit summary |
mNo edit summary |
||
| (8 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
A '''Turing machine''' <ref>{{citation | A '''Turing machine'''<ref>{{citation | ||
| author = [[Alan Turing]] | | author = [[Alan Turing]] | ||
| title = On Computable Numbers, With an Application to the Entscheidungsproblem | | title = On Computable Numbers, With an Application to the Entscheidungsproblem | ||
| Line 7: | Line 7: | ||
| date = 1936 | | date = 1936 | ||
}}</ref> | }}</ref> | ||
is a theoretical computing device, first posited by mathematician [[Alan Turing]], which has been used extensively in analyzing computing problems such as tractability and complexity theory | is a theoretical computing device, first posited by mathematician [[Alan Turing]], which has been used extensively in analyzing computing problems such as tractability and complexity theory. | ||
Its basic components are a length of tape and a head which operates on the tape. The tape is divided into segments, each of which can hold a single character which is an element of a predefined, finite set of characters called the 'tape alphabet'. The machine is always in one 'state' which is an element in a predefined, finite set of states. The head is also always in a single location on the tape (i.e. there is one character on the tape at which the head is located). The machine is fully deterministic: the current state and current tape character determine what it does next. In a single computing step the head reads the character from the tape and takes actions based on the character and its current state. In addition to changing its internal state, it may take one of four actions — step to an adjacent character to the left, step to the right, change the character at the current location, or halt. | |||
A device that can simulate | == Turing completeness == | ||
| title=Knuth: MMIX | author=Donald Knuth | accessdate=2007-11-10 }}</ref> | Turing invented the machine in order to solve the [[halting problem]] and it is widely used in theoretical computer science because its simplicity makes it relatively easy to prove theorems about its behavior. However, it is also quite a general description and many other types of computer are provably equivalent to a Turing machine. A device that can simulate the Turing machine is called '''Turing complete'''. | ||
One reduction which has been proven to place no limitations on the Turing machine is limiting the tape alphabet to two characters; a Turing machine with a binary alphabet can simulate any Turing machine with an alphabet of any size. Therefore, Turing machines are usually defined and studied using only the binary alphabet consisting of 1 and 0. | |||
Any machine using the [[Von Neumann architecture]]—basically any computer with a single processor and memory—can be simulated by a Turing machine. | |||
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 exists 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 | |||
| title=Knuth: MMIX | author=Donald Knuth | accessdate=2007-11-10 }}</ref> can be considered "Turing complete," in a completely abstract sense. Even a language such as [http://esolangs.org/wiki/Brainfuck brainfuck], with only eight operators, can be Turing complete. | |||
==References== | ==References== | ||
{{reflist}} | {{reflist}} | ||
[[Category:Suggestion Bot Tag]] | |||
Latest revision as of 06:00, 31 October 2024
A Turing machine[1] is a theoretical computing device, first posited by mathematician Alan Turing, which has been used extensively in analyzing computing problems such as tractability and complexity theory.
Its basic components are a length of tape and a head which operates on the tape. The tape is divided into segments, each of which can hold a single character which is an element of a predefined, finite set of characters called the 'tape alphabet'. The machine is always in one 'state' which is an element in a predefined, finite set of states. The head is also always in a single location on the tape (i.e. there is one character on the tape at which the head is located). The machine is fully deterministic: the current state and current tape character determine what it does next. In a single computing step the head reads the character from the tape and takes actions based on the character and its current state. In addition to changing its internal state, it may take one of four actions — step to an adjacent character to the left, step to the right, change the character at the current location, or halt.
Turing completeness
Turing invented the machine in order to solve the halting problem and it is widely used in theoretical computer science because its simplicity makes it relatively easy to prove theorems about its behavior. However, it is also quite a general description and many other types of computer are provably equivalent to a Turing machine. A device that can simulate the Turing machine is called Turing complete.
One reduction which has been proven to place no limitations on the Turing machine is limiting the tape alphabet to two characters; a Turing machine with a binary alphabet can simulate any Turing machine with an alphabet of any size. Therefore, Turing machines are usually defined and studied using only the binary alphabet consisting of 1 and 0.
Any machine using the Von Neumann architecture—basically any computer with a single processor and memory—can be simulated by a Turing machine.
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 exists only as a concept, not as an implementation (such as Donald Knuth's MMIX)[2] can be considered "Turing complete," in a completely abstract sense. Even a language such as brainfuck, with only eight operators, can be Turing complete.
References
- ↑ Alan Turing (1936), "On Computable Numbers, With an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society
- ↑ Donald Knuth. Knuth: MMIX. Retrieved on 2007-11-10.