Turing machine: at the origins of computer science and cryptography

The Turing machine became a grandiose invention, which initiated the era of information technology and anticipated the architecture of modern computer systems. The outstanding British mathematician and analyst Alan Turing, in an incomplete twenty-four years, managed to mentally construct an abstract mechanism for solving one of the fundamental problems of mathematics formulated by the famous German professor David Hilbert at the International Mathematical Congress held in 1900 in Paris.

The Turing machine not only became a clear answer to a specific computing problem, but it was also the theoretical basis of algorithms and the scientific basis of programming. In addition, the very principle of solving complex mathematical problems by the method of constructing various abstract mechanisms and constructing algorithms executed by electronic devices formed the basis for the emergence of a new sphere of intellectual activity - information technologies.

The Turing machine is equipped with an infinite tape, divided into cells, each of which contains a certain symbol from a fixed finite set. The totality of all symbols is called the alphabet of the machine. One of the signs of this peculiar alphabet stands out and is called the "gap". The Turing machine changes the contents of the cells by means of a special reading and writing head moving along the tape. Receiving information from the head about the contents of each cell, the device itself decides, depending on its internal state, which character to write in this cell and where to move the head after this operation. In this case, the internal state (memory) of the machine, characterized by a certain value from zero to a certain maximum value, also undergoes a change.

The Turing machine is extremely simple, but it allows you to execute almost any program built on clear algorithms. For execution of various computational operations there is a special table in which certain rules are written, representing a set of universal instructions for the machine. Guided by this table, which fixes the order of actions for a particular combination of different states and symbols, the device determines which computational operation should be performed in each particular situation. In fact, the universal Turing machine is the first prototype of modern computers.

The ingenious invention of Alan Turing was successfully applied by the British cryptanalytical bureau during the Second World War for hacking German secret codes. Often, the deciphering of secret messages of underwater vultures Denitsa lay on the Churchill table before she got into the Reich Chancellery. Unlike German cryptographers who practiced a purely intuitive approach and applied to cryptography as an art, Alan Turing's technique provided algorithmic ways of solving the most complicated tasks for deciphering secret codes, which turned out to be incomparably more effective.

The non-deterministic Turing machine made it possible to crack the ciphers of the enemy not only to brilliant cryptographers, but also to ordinary employees of the bureau, turning intuitive actions into systematic, purposeful movement toward the goal. The data obtained with the help of the Turing machine in no small measure affected the outcome of the battle for England.