Turing machine: Difference between revisions

Revision as of 00:38, 10 February 2025

Mathematical model of computation

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine. The Turing machine manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

File:Turing Machine Model Davey 2012.jpg

A model of a Turing machine

History

The concept of the Turing machine was introduced by Alan Turing in 1936, in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem." Turing's machine was designed to be a simple yet powerful model of computation that could be used to explore the limits of what can be computed.

Description

A Turing machine consists of:

A tape divided into cells, one next to the other. Each cell contains a symbol from a finite alphabet.
A head that can read and write symbols on the tape and move the tape left and right one cell at a time.
A state register that stores the state of the Turing machine, one of a finite number of states.
A finite table of instructions that, given the current state and the symbol the head is reading, tells the machine what symbol to write, how to move the tape (left or right), and what the next state of the machine is.

File:Turing machine 2a.svg

Diagram of a Turing machine

Functionality

The Turing machine operates by reading the symbol on the tape at the current head position, consulting the table of instructions, and then performing the specified action. This action may involve writing a new symbol on the tape, moving the head left or right, and changing the state of the machine. The process continues until the machine reaches a halting state, if such a state exists.

Variants

There are many variants of the Turing machine, including the universal Turing machine, which can simulate any other Turing machine. Other variants include the multi-tape Turing machine, which has multiple tapes and heads, and the non-deterministic Turing machine, which can make multiple moves at once.

Applications

Turing machines are used in theoretical computer science to understand the limits of what can be computed. They are also used in the study of computational complexity to classify problems based on the resources required to solve them.

Busy Beaver

The Busy Beaver is a Turing machine that is designed to produce the maximum number of 1s on its tape before halting, given a specific number of states. The Busy Beaver function is non-computable, meaning there is no algorithm that can determine the maximum number of 1s for any given number of states.

File:Busy Beaver 3 State.png

Example of a 3-state Busy Beaver

Related pages

References

Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, 2(42), 230-265.
Davis, M. (2000). "The Universal Computer: The Road from Leibniz to Turing." W. W. Norton & Company.

@@ Line 1: / Line 1: @@
-A Turing machine is a theoretical device that was proposed by the mathematician and computer scientist Alan Turing in 1936. It is a simple yet powerful model of computation that can simulate any algorithm or computer program. The concept of a Turing machine has had a profound impact on the field of computer science and has played a crucial role in the development of modern computers.
+{{short description|Mathematical model of computation}}
+{{Use dmy dates|date=October 2023}}
-== Overview ==
+== Turing machine ==
-A Turing machine consists of a tape divided into cells, each of which can hold a symbol from a finite alphabet. The machine has a read/write head that can move along the tape and read or write symbols on the cells. It also has a control unit that determines the machine's behavior based on its current state and the symbol it reads from the tape.
+A '''Turing machine''' is a mathematical model of computation that defines an abstract machine. The Turing machine manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a [[CPU]] inside a computer.
-The behavior of a Turing machine is defined by a set of rules, known as the transition function. This function specifies how the machine should change its state and move its head based on the current state and the symbol it reads. The machine starts in an initial state and continues executing the transition function until it reaches a halting state, at which point it stops.
+[[File:Turing_Machine_Model_Davey_2012.jpg|thumb|A model of a Turing machine]]
-== Functioning ==
+== History ==
-To perform a computation, a Turing machine starts with an input on the tape and follows the transition function to manipulate the symbols on the tape. The machine can perform various operations, such as reading a symbol, writing a symbol, moving the head left or right, and changing its state. By repeatedly applying the transition function, the machine can perform complex computations.
+The concept of the Turing machine was introduced by [[Alan Turing]] in 1936, in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem." Turing's machine was designed to be a simple yet powerful model of computation that could be used to explore the limits of what can be computed.
-The power of a Turing machine lies in its ability to simulate any algorithm or computer program. It can solve problems that are computationally solvable, meaning that there exists an algorithm that can solve them. This property is known as Turing completeness, and it forms the basis for the theory of computation.
+== Description ==
+A Turing machine consists of:
+* A tape divided into cells, one next to the other. Each cell contains a symbol from a finite alphabet.
+* A head that can read and write symbols on the tape and move the tape left and right one cell at a time.
+* A state register that stores the state of the Turing machine, one of a finite number of states.
+* A finite table of instructions that, given the current state and the symbol the head is reading, tells the machine what symbol to write, how to move the tape (left or right), and what the next state of the machine is.
+[[File:Turing_machine_2a.svg|thumb|Diagram of a Turing machine]]
+== Functionality ==
+The Turing machine operates by reading the symbol on the tape at the current head position, consulting the table of instructions, and then performing the specified action. This action may involve writing a new symbol on the tape, moving the head left or right, and changing the state of the machine. The process continues until the machine reaches a halting state, if such a state exists.
+== Variants ==
+There are many variants of the Turing machine, including the [[universal Turing machine]], which can simulate any other Turing machine. Other variants include the [[multi-tape Turing machine]], which has multiple tapes and heads, and the [[non-deterministic Turing machine]], which can make multiple moves at once.
 == Applications ==
-Although Turing machines are primarily a theoretical concept, they have had a significant impact on the development of computers and computer science. They provide a formal framework for understanding the limits of computation and have helped researchers analyze the complexity of algorithms and problems.
+Turing machines are used in theoretical computer science to understand the limits of what can be computed. They are also used in the study of [[computational complexity]] to classify problems based on the resources required to solve them.
-Turing machines have also influenced the design of real-world computers. The von Neumann architecture, which is the basis for most modern computers, is inspired by the structure of a Turing machine. It consists of a central processing unit (CPU) that executes instructions stored in memory, similar to how a Turing machine reads and executes symbols on its tape.
+== Busy Beaver ==
+The Busy Beaver is a Turing machine that is designed to produce the maximum number of 1s on its tape before halting, given a specific number of states. The Busy Beaver function is non-computable, meaning there is no algorithm that can determine the maximum number of 1s for any given number of states.
-== See also ==
+[[File:Busy_Beaver_3_State.png|thumb|Example of a 3-state Busy Beaver]]
+== Related pages ==
 * [[Alan Turing]]
 * [[Computability theory]]
-* [[Turing completeness]]
+* [[Church-Turing thesis]]
-* [[Von Neumann architecture]]
+* [[Halting problem]]
+* [[Universal Turing machine]]
 == References ==
-{{Reflist}}
+* Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, 2(42), 230-265.
+* Davis, M. (2000). "The Universal Computer: The Road from Leibniz to Turing." W. W. Norton & Company.
-== External links ==
-* [https://plato.stanford.edu/entries/turing-machine/ Turing Machines - Stanford Encyclopedia of Philosophy]
-* [https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf On Computable Numbers, with an Application to the Entscheidungsproblem - Alan Turing]
-[[Category:Computability theory]]
+[[Category:Models of computation]]
-[[Category:Theory of computation]]
-[[Category:Computer science]]
 [[Category:Alan Turing]]
+[[Category:Theoretical computer science]]