Turing Machine: what is it and how does it work?

A machine that set the precedents of today's computing.

We cannot conceive of the historical moment in which we live without considering the importance of computing. In just a few years it has gone from being used in specific areas to being an omnipresent entity, and not only in computers, but also in cell phones and in almost all commonly used technologies (such as wearables).

In fact, the computer or cell phone you are using to read this article has such technology that a few decades ago it would have needed a huge space to work (or it would have been totally unfeasible). The fact is that today we are moving towards an extraordinary miniaturization of computer components, which will expand their use and facilitate their expansion to all areas of life.

The progress to which technology is subjecting us is unstoppable, to the point that without it we would no longer be able to live optimally. Our species depends on information technology, because today's society is so complex that the bare cognitive functions no longer allow us to manage it successfully, requiring external help to compensate for our shortcomings.

In this text we will see what is the concept of the Turing machineIts contribution to computing as we know it today is evident, and it is considered the model on which the logic and architecture of today's computers are based. That is: the mother of a technology that has not only changed the world, but also the horizon of humanity.

What is the Turing machine?

The Turing machine is a device created in 1936, which represents an idealized model of computation capable of storing/processing virtually infinite information.. The system is a mathematical abstraction that is constructed in an extraordinarily simple way, but which facilitates the empirical verification of a wide range of questions on the theories of computability and/or complexity. Its ideation marked a major milestone in the history of computing, to the point of being considered as the origin of today's computers (and related technologies, such as tablets or cell phones).

The architect of this was Alan M. Turing, English logician and mathematician who, throughout his life, sought the conception of a theoretical model with which to provide answers to the unknowns of his discipline, automatically and accessible to all.

This British genius, whose historical importance cannot be questioned, also contributed (along with several Polish scientists) to unraveling the cryptographic codes that the Nazi military used to communicate secretly among themselves during the sad Second World War (through what became known as the enigma machine). To this end, he devised an electromagnetic cutting device (bombe), the use of which shortened the duration of the conflict and saved countless human lives by allowing the regime's plans to be revealed during the prolonged hostilities.

Turing's machine is the historical precursor of the modern "stored-program computers", which allow both the storage ofwhich allow both the storage of data and of the algorithms on which they are built. Its advantage, and one of the factors that fascinates computer theorists, is its simplicity and its enormous configuration possibilities at a technical level; it allows experimentation through the way its physical elements are arranged and the "question" with which its use is programmed (through algorithms, which are translated into a "succession" of codes inspired by the logical language). This versatile capacity is due to the very nature of the data with which it operates, which are subject to an enormous level of abstraction.

Thus, the Turing machine machine can be programmed to execute instructions of a concrete nature, answering more or less complex questions.. All this implies that its particular language must be known, with the aim of adapting the algorithm for its operation to it, aware that there is no universal code to clarify all the mathematical unknowns that slumber in nature itself (as indicated by the Church-Turing law). Therefore, the system requires a human mind behind it, which asks itself the doubt to be formulated and knows how to "address" the device to solve it.

The raw material of the Turing machine are the computable numbers, i.e. those that can be computed.that is, those that can be calculated objectively by means of a mathematical formula, and within a reasonable time. In this context, it is essential that it be adapted to two specific "problems": that of the decision (each answer is preceded by a series of previous calculation elements that can be answered dichotomously as yes/no) and that of the stop (to recognize if the final answers are really possible, or if the system will be "condemned" to process the order in an infinite/irresolvable cycle). That is, that there is a concrete algorithm for what you want to know and that your technology can answer it with the necessary precision to "stop" and offer a solution.

Up to this point, the theoretical logics of a Turing machine have been discussed in detail. In the following lines we will delve into the core of its physical and/or functional particularities, with which the algorithm or operating rule that the user has set (and that can range from simple equations to the very entrails of the law of mathematical abstraction) can be executed.

Description of the Turing machine

Along with the logical/mathematical foundation described above, the Turing machine requires a series of physical elements, which have the function of executing the commands introduced previously. The arrangement of these can be diverse, as there would be almost infinite designs of this system, but the following are necessarily required: a tape of paper or similar material, a moving head whose end is capable of making traces (symbols or numbers) and a central processor in which to encode the algorithms that are required or that facilitate the analysis.

The tape is the most essential element of them all. It is nothing more than a longitudinal strip, which is divided into a succession of squares of equal size (or boxes), and whose length will depend largely on the "effort" to be carried out to solve the question posed by the user (it can be as short or as long as deemed appropriate). The boxes are reserved for the head to plot different symbols (such as 0-1 in binary code) in each box, and are the computational product that the user will use for the calculation.The boxes are reserved for the head to plot different symbols (such as 0-1 in binary code) in each one, and constitute the calculation product to be checked after it has stopped. In computer terms, these tapes could be the memory of a modern computer. The first cells usually have an already established content (input), leaving the rest empty and ready to be occupied after the computation process.

Likewise, the Turing machine consists of a head, a mechanical appendix (mobile) that moves to the left or to the right following the order that the system provides for it.. At its end it has an elongation capable of engraving a trace on the tape, giving its shape to the numbers or figures that correspond according to the code that determines the movement. The original model had a head of rudimentary technology, but progress in the fields of robotics has allowed the emergence of new, more advanced and precise designs. The head "reads" the contents of the cells and moves a single cell to either side (depending on its specific state) to continue executing the instruction.

Thirdly, there is a central a central processor that is intended to store code and algorithms containing instructions for the activity of the device, expressed as instructions for the activity of the device, expressed in mathematical and logical terms. This language has a universal nuance, although it allows a certain degree of maneuverability to introduce operational expressions formulated by the user (provided that he has operationalized the meaning). In this way, its head would facilitate the execution of instructions stored in the processor, which would be equivalent to what is known today as programs or applications (apps). This system would make it possible to reproduce any possible calculation and would stand as the predecessor of any of today's computers.

How this device works

A Turing machine is designed for the recording of a specific sample of symbols or numbers, whose possible universe is usually called "alphabet". When it works with binary code, its total alphabet is two (0 or 1), but it can be as wide as it is deemed appropriate for the function to be performed. The head will only be able to reproduce in the cells of the tape what has been previously indicated in such a system, so that a calculation (number "pi", for example) will require the full spectrum of numbers (from 0 to 9).

In addition to this, it is usually also contemplated what in practice are known as states (Q), which are also programmed by the user during the description of the code (and are labeled as q). (and which are labeled q1, q2, q3, q4... qn). The total range depends on abstract mathematical hypotheses, and outlines the conditional nuances of the logical formula of the code, in order to make the head move in the corresponding direction and perform the relevant action ("if you are in position q2, write "0" and do not move", e.g.).

Finally, there would be a "transition" function (delta), which summarizes the whole sequence (step by step) of mathematical processing, and expresses the complete instruction: reading of cell, writing of new symbol, changes of state (or not) and movement of the head; in a recurring cycle that stops when the answer to the initial question is found, or also at the moment when the user has foreseen it in his code (often by an exclamation, read as "stop"). At the moment the machine stops moving, the tape is retrieved and the answer provided is analyzed in detail.

As can be seen, there is a clear similarity between Turing's machine and the computers we use today.. His contribution has been key to exponential progress in all subsequent computer design, to the point that his spirit lies at the very Heart of a technology that allows us to stay interconnected.

Bibliographical references:

• Khan, S. and Khiyal, M. (2006). Turing Model for Distributed Computing. Information Technology Journal. 5, 305-313.
• Qu, P., Yan, J., Zhang, Y. and Gao, G. (2017). Parallel Turing Machine, a Proposal. Journal of Computer Science and Technology, 32, 269-285.