One of the limitations of the Turing machine is that it behaves like a computer that always runs the same program and can therefore only perform a single task. From a purely historical perspective, one of the first examples of a Turing machine was the AGC (Apollo Guidance Computer) system. This machine was the main computer aboard NASA's Apollo missions, which enabled the feat of sending man to the Moon on July 20, 1969.

Long before this, and aware of this limitation, Alan Turing introduced a generalization of his machine that came to be called the universal Turing machine or u-machine. This is a Turing machine that can simulate any other Turing machine, and therefore can process distinct programs. Therefore, a computer is an example of a universal Turing machine.

Another example is smartphones, cell phones with the performance of a minicomputer.

The fact that the Turing machine could be universal represents a decisive step in the history of computing. If we also consider another extremely important fact, the famous Church-Turing thesis, we conclude that the invention of the computer was already imminent.

American mathematician Alonzo Church, a key figure in mathematical logic, formulated with Alan Turing what became known as the Church-Turing thesis. Their thesis states that the class of problems that can be solved by a universal Turing machine is one whose solution can be expressed using an algorithm.

However, we must keep in mind that at that time the term "algorithm" was not yet used, and the expression "effective method of calculation" was used to refer to the same concept.

An algorithm can be defined as the set of steps or rules that lead to a result or solution to a problem. Therefore, for a computer, an algorithm is synonymous with a solution. The entire algorithm must satisfy certain properties:

-First, the number of steps leading to the solution must be finite, that is, the protocol that is executed until the solution is reached must always terminate, no matter how long it is.

-Second, the steps or rules must be well defined, without ambiguity.

-Third, although this is an optional requirement, the ideal will be for an algorithm to be able to solve not a concrete problem, but problems of the same class.

-And fourth, and this is also an optional requirement, the path to the solution must consist of as few steps as possible.

Mathematics studied over the centuries is full of simple algorithms. For example, solving systems of equations using the substitution method consists of the following algorithm:

-Step 1. Solve the same unknown in both expressions.

-Step 2. Match the expressions.

-Step 3. Solve the equation.

-Step 4. Substitute the obtained value into any of the expressions where the other variable was isolated.

-Step 5. Solve the equation resulting from the previous step.

-Phase 6. End.

Based on these considerations, we conclude that a computer is a universal Turing machine that processes algorithms. When the solution to a problem can be expressed through an algorithm, then the problem is said to be computable.

Swiss engineer Niklaus Wirth, author of programming languages ​​such as Algol, Modula-2, and Pascal, among others, introduced the definition of a program in 1975. According to the latter, the program is the meeting of the algorithm with the way of organizing the data in the program, which is known as data structure, thus proposing one of the most famous expressions inherited from Turing's work: algorithm + data structure = program.

References

Geni della matematica n. 3 - Turing. La mente che ha inaugurato l'era dei computer, published on January 1, 2022 by RBA.

Written by Emanuele Pace