Turing machine

A Turing machine is a mathematical model of computation that helps us understand how computers work. It imagines a very simple machine that can read, write, and move along a long tape covered with symbols. Even though it seems basic, this machine can perform any calculation that a real computer can do.

A physical Turing machine model constructed by Mike Davey. A true Turing machine would need to be provided more memory (tape) if and when required; physical models can only have a finite amount.

The Turing machine was created in 1936 by Alan Turing, a brilliant mathematician. He used it to explore big questions about what computers can and cannot do. For example, he showed that no machine can always tell if another machine will keep running forever or stop at some point.

Even though Turing machines are not used in real computers because they are too slow, they are very important in computer science. The idea of being "Turing complete" means that a system can do everything a Turing machine can do. Most programming languages are Turing complete, which means they can handle any computing task, given enough time and memory.

Overview

A Turing machine is a simple idea that helps us understand how computers work. It is like a model of a central processing unit (CPU). The CPU is the part of a computer that controls all data manipulation.

Imagine a machine that uses a long tape to store and change data.

In theory, a Turing machine can work with any set of symbols to create and recognize different sequences, called languages. A special kind of Turing machine, called a universal Turing machine, can simulate any other Turing machine. However, it is generally impossible to know if a Turing machine will ever finish what it is doing, due to something called the halting problem.

Description

A Turing machine is a simple idea that helps us understand how computers work. It imagines a machine with a long tape split into little boxes. Each box can hold a symbol, like a letter or number.

The machine has a reader that can move along the tape. It can read the symbol in a box, change the symbol, and move one step left or right. It follows a set of rules to decide what to do next. This basic idea can copy what any computer can do, even though it looks very simple.

Formal definition

3-state Busy Beaver. Black icons represent location and state of head; square colors represent 1s (orange) and 0s (white); time progresses vertically from the top until the HALT state at the bottom.

A Turing machine is a simple idea that can do any calculation a computer can. It has a set of rules and a long tape divided into boxes. Each box holds a symbol, like a letter or number. The machine reads a symbol, follows a rule, and may change the symbol or move left or right on the tape.

One example has three main steps: it starts in state A, reads the symbol 1, and changes to state B. This shows how even a very basic machine can do complex tasks.

State table for 3-state, 2-symbol busy beaver
Tape symbol	Current state A			Current state B			Current state C
Tape symbol	Write symbol	Move tape	Next state	Write symbol	Move tape	Next state	Write symbol	Move tape	Next state
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	HALT

Additional details required to visualise or implement Turing machines

To make a Turing machine work, we need to decide how the symbols look and how to read and write them. It’s also useful to let the tape slide under the head instead of moving the head itself.

While the tape can be thought of as stretching infinitely, in real use it’s often extended with blank spaces as needed. The tape cannot be fixed in length, as this would limit what the machine can compute. Different authors sometimes change the rules slightly to make their work easier, but these changes don’t affect the machine’s ability to solve problems.

Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
Current state	Scanned symbol	Print symbol	Move tape	Final (i.e. next) state	5-tuples
A	0	1	R	B	(A, 0, 1, R, B)
A	1	1	L	C	(A, 1, 1, L, C)
B	0	1	L	A	(B, 0, 1, L, A)
B	1	1	R	B	(B, 1, 1, R, B)
C	0	1	L	B	(C, 0, 1, L, B)
C	1	1	N	H	(C, 1, 1, N, H)

	Current m-configuration (Turing state)	Tape symbol	Print-operation	Tape-motion	Final m-configuration (Turing state)	5-tuple	5-tuple comments	4-tuple
N1	q_i	S_j	Print(S_k)	Left L	q_m	(q_i, S_j, S_k, L, q_m)	"blank" = S₀, 1=S₁, etc.
N2	q_i	S_j	Print(S_k)	Right R	q_m	(q_i, S_j, S_k, R, q_m)	"blank" = S₀, 1=S₁, etc.
N3	q_i	S_j	Print(S_k)	None N	q_m	(q_i, S_j, S_k, N, q_m)	"blank" = S₀, 1=S₁, etc.	(q_i, S_j, S_k, q_m)
4	q_i	S_j	None N	Left L	q_m	(q_i, S_j, N, L, q_m)		(q_i, S_j, L, q_m)
5	q_i	S_j	None N	Right R	q_m	(q_i, S_j, N, R, q_m)		(q_i, S_j, R, q_m)
6	q_i	S_j	None N	None N	q_m	(q_i, S_j, N, N, q_m)	Direct "jump"	(q_i, S_j, N, q_m)
7	q_i	S_j	Erase	Left L	q_m	(q_i, S_j, E, L, q_m)
8	q_i	S_j	Erase	Right R	q_m	(q_i, S_j, E, R, q_m)
9	q_i	S_j	Erase	None N	q_m	(q_i, S_j, E, N, q_m)		(q_i, S_j, E, q_m)

The table for the 3-state busy beaver ("P" = print/write a "1")
Tape symbol	Current state A			Current state B			Current state C
	Write symbol	Move tape	Next state	Write symbol	Move tape	Next state	Write symbol	Move tape	Next state
0	P	R	B	P	L	A	P	L	B
1	P	L	C	P	R	B	P	R	HALT

Equivalent models

Many machines might look like they are more powerful than a basic Turing machine. But they can’t do more than a Turing machine can. They might work faster or use less memory. But they can’t solve problems that a Turing machine can’t solve.

Some very simple machines are just as powerful as Turing machines. For example, a Turing machine is the same as a special kind of machine called a pushdown automaton. Or even a machine with just a couple of stacks. Other simple models, like multi-tape Turing machines or non-deterministic Turing machines, are also equally powerful.

Choice c-machines, oracle o-machines

In his 1936 paper, Alan Turing described two types of machines. An "automatic machine" follows rules based on its current state. A "choice machine" needs help from someone outside when it isn’t sure what to do next.

Turing also talked about an oracle machine. This is like a regular machine but stops to ask an external "oracle" for help with certain problems. The oracle isn’t a machine; it just gives answers when needed.

Universal Turing machines

Main article: Universal Turing machine

An implementation of a Turing machine

Alan Turing discovered that one special machine could do the work of any other computing machine. This idea was very surprising when he first shared it in 1936. Today, this idea helps us understand how modern computers work.

Turing called this special machine a "universal machine." It can follow any set of rules if those rules are written on its tape before it starts. This idea helped create computers that can store and run many different programs.

Comparison with real machines

A Turing machine realization using Lego pieces

Turing machines are special models that help us understand how computers work. They can do anything a real computer can do, but they imagine having endless space to work with. This makes it easier to study and describe computer programs.

One key difference is that real computers have limits on their storage, while a Turing machine can imagine having as much space as needed. Even though real computers can add more storage, like extra disks, they still have limits at any moment. Turing machines help us think about programs without worrying about these limits, letting us focus on what the program does rather than how much space it uses.

Comparison with the arithmetic model of computation

The arithmetic model of computation works differently from the Turing machine model in two main ways. In the arithmetic model, each real number uses one memory cell. But the Turing machine needs space based on how many bits are required to write the number.

Also, basic math operations like adding or multiplying can be done instantly in the arithmetic model. But on a Turing machine, these operations take time depending on the size of the numbers involved.

Some tasks can be done quickly in one model but not the other. For example, the Euclidean algorithm works fast on a Turing machine but not in the arithmetic model. There are also special cases where, if the numbers involved don't get too big compared to the input, tasks that are quick in the arithmetic model will also be quick for a Turing machine. This is called running in strongly polynomial time.

History

The idea of machines that can do calculations goes back a long way. Charles Babbage, who lived a long time ago, dreamed of a machine called the analytical engine that could do many kinds of math tasks by itself. Later thinkers tried to describe how such machines might work.

One big question for mathematicians was the “Entscheidungsproblem.” This was about finding a way to know for sure whether a math problem could be solved. Many smart people worked on this puzzle.

Then came Alan Turing. In 1936, he described a simple idea called the “a-machine” — what we now call a Turing machine. This helped people understand what kinds of problems machines could and could not solve. Turing showed that some problems were so hard that no machine could ever solve them completely. His work helped people understand the limits of what computers can do.

Later, Turing’s ideas became very important for the science of computers. Even today, scientists use his model to study how fast or slow computers need to work to solve different tasks.