Turing Machine: What It Is And How It Works

A machine that set the precedents for today’s computing.

Turing machine

We cannot conceive of the historical moment in which we live without paying attention to the importance of computing. In just a few years it has gone from being used in specific fields to being omnipresent, and not only in computers, but also in mobile phones and in almost all commonly used technologies (such as so-called “wearables”).

In fact, the computer or mobile you use to read this article has such technology that a few decades ago it would have needed a huge space to function (or it would have been totally unfeasible). And it 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 advance to which technology subjects us is unstoppable, to the point that without it we could no longer live optimally. Our species depends on computing, because today’s society is of such complexity that bare cognitive functions no longer allow us to manage it successfully, requiring external help to compensate for our deficiencies.

In this text we will see what the concept of the Turing machine, created in the middle of the 30th century, consists of. Its contribution to computing as it is known today is evident, considering the model on which the logic and architecture of current computers. This 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 computing capable of storing / processing virtually infinite information. The system is a mathematical abstraction that is constructed in an extraordinarily simple way, but that facilitates the empiricist verification of a wide range of questions about the theories of computability and / or complexity. His ideation marked a great milestone in the history of computing, to the point of being considered the origin of today’s computers (and related technologies, such as tablets or mobile phones).

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

This British genius, whose historical importance cannot be questioned, also contributed (together with several Polish scientists) to unravel the encrypted codes that the Nazi military used to secretly communicate with each other during the sad Second World War (through what became known as an enigma machine). To do this, he devised an electromagnetic cut-off 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 unveiled during the time the hostilities raged on.

The Turing machine is the historical precursor of modern “stored-program computers”, which allow both the saving of data and the algorithms on which it is built. Its advantage, and one of the factors by which it generates fascination among computer theorists, is its simplicity and its enormous configuration possibilities at a technical level; and it is that it enables experimentation through how its physical elements are arranged and the “question” with which its use is programmed is posed (by means of algorithms, which are translated into a “succession” of codes that are inspired by logical language ). This versatile capacity is due to the very nature of the data with which it operates, subject to an enormous level of abstraction.

In this way, the Turing machine can be programmed to execute specific instructions that answer 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 doze in nature itself (as indicated Church-Turing law). Therefore, the system requires a human mind behind it, asking itself the question to be formulated and knowing how to “address” the device to solve it.

The raw material of the Turing machine are computable numbers, that is, those that can be calculated objectively by means of a mathematical formula, and within the threshold of 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 (recognize if the final answers are really possible, or if the system will be “condemned” to process the order in an infinite / unsolvable cycle). That is, that there is a specific algorithm for what it is intended to know and that its technology can respond to 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. The following lines will delve into the core of its physical and / or functional characteristics, with which the algorithm or operating standard that the user has set can be executed (and which can range from simple equations to the very heart of the law of mathematical abstraction).

Description of the Turing machine

Along with the logical / mathematical foundation that has been described, the Turing machine requires a series of physical elements, which have the function of executing the previously entered commands. Their arrangement can be diverse, as there would be almost infinite designs of this system, but the following are necessarily required: a tape of paper or a similar material, a moving head whose end is capable of making lines (symbols or numbers) and a central processor in which to code 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 squares), and whose length will depend largely on the “effort” that must be carried out to solve the question posed by the user (being able be as short or as long as deemed appropriate). The boxes are reserved for the head to draw different symbols (such as 0-1 in the binary code) in each one, and they constitute the calculation product that will have to be checked after stopping. In computer terms, these tapes could be the memory of a modern computer. The first cells usually have a content already established (input), leaving the rest empty and ready to be used after the computation process.

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

Third, there is a central processor to which the function of storing code and algorithms that contain instructions for the activity of the apparatus is assigned, expressed following mathematical and logical terms. This language has a universal nuance, although it allows a certain degree of maneuver to introduce operational expressions formulated by the user (provided that the meaning has been made operational). 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 (app). This system would allow any possible calculation to be reproduced and would stand as the predecessor of any of the current computers.

Operation of this device

A Turing machine is designed to engrave a specific sample of symbols or numbers, the possible universe of which is often called the “alphabet.” When it works with binary code, its total alphabet is two (0 or 1), but it can be as wide as 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 a calculation (number “pi”, for example) will require the full spectrum of numbers (from 0 to 9).

In addition to this, what is known in practice as states (Q) are also usually considered , which are also programmed by the user during the description of the code (and which are labeled as q1, q2, q3, q4 … qn). The total range depends on abstract mathematical hypotheses, and reviews the conditional nuances of the logical formula of the code, in order for the head to move in the corresponding direction and perform the pertinent action (“if you are in position q2, write “0” and don’t move “, eg).

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

As can be seen, there is a clear similarity between the Turing machine and the computers we use today. His contribution has been key to exponentially advancing all subsequent computer design, to the point that his spirit resides at the very heart of a technology that allows us to remain interconnected.

Bibliographic 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.

Add a Comment

Your email address will not be published. Required fields are marked *