Universal Turing machine

In computer science, a universal Turing machine (UTM) is a special machine. It can do any calculation that any other computer can do. This idea was first described by Alan Turing in his paper called "On Computable Numbers, with an Application to the Entscheidungsproblem". Turing showed that such a machine is possible.

Turing compared solving math problems to a machine that can only be in a few states. He called these states "m-configurations". He explained how this machine would work and why it could do any computing task.

Turing introduced the idea of the universal Turing machine in 1936–1937. This idea helps us understand what machines can do and how different computers are related.

Introduction

Further information: Register machine § Historical development of the register machine model

Alan Turing first described the idea of a machine that can copy any other machine. This idea helped shape early computers and computer science.

Martin Davis says Turing's ideas about storing instructions and data in memory helped John von Neumann design early computers like the EDVAC. Davis also says Turing's work on the ACE computer had early ideas about how computers can do tasks better. Donald Knuth says Turing's work helped computers manage programs and tasks more easily.

Mathematical theory

A universal Turing machine can solve any problem that can be solved by an algorithm. This helps us understand what computers can do.

Because of this, scientists use the universal Turing machine to see how powerful different computers are. If a computer can act like a universal Turing machine, it is called Turing complete.

Efficiency

Every Turing machine can be written as a special string of 0s and 1s. This helps us study how these machines work.

In 1966, two scientists showed that a special kind of Turing machine can copy the work of any other Turing machine. If a machine finishes its task in N steps, this special machine can do the same task in about N times the logarithm of N steps.

Smallest machines

Alan Turing imagined a very simple machine that could do any calculation. Later, scientists tried to find the smallest such machine. They found that just two symbols or a few states could be enough. For example, one scientist made a machine with 7 states and 4 symbols that could do everything a bigger machine could.

Researchers have since found even smaller machines. Some use only 2 states and 18 symbols, while others need more states but fewer symbols. These tiny machines follow strict rules to work like bigger universal machines. Scientists also found ways to make machines even smaller by changing some rules slightly.

Machines with no internal states

Some special kinds of machines don’t need extra memory spots to work. They can use the tape itself to remember what to do next.

For example, imagine a tape with six different colors of squares. By moving several reading heads at once across these colored squares, the machine can act like one with extra memory spots, even though it doesn’t have any built-in ones.

With just two reading heads and six colors, such a machine can act like a very powerful computer. We still don’t know the smallest number of colors needed for this kind of machine or if it’s possible to do this with only two colors. These ideas also show that certain rule-based systems can act like powerful computers too. If the space between the two reading heads can change, the machine can mimic other types of universal systems as well.

Example of coding

Alan Turing showed how to design a special machine that can follow any set of rules. He used simple symbols to show these rules and put them in order on a tape.

The rules were written using symbols like “;” and letters such as A, D, and C. These symbols were placed on the tape with special marks at the start and end. This lets the machine read and follow the rules step by step.