What is a Turing machine?

The Turing machine is a classic concept that originated before the computer era. It was a logical computational construct and not a real computer. The model describes how a computer solves a formalized task in order to arrive at the result, and what requirements are placed on the algorithm so that the machine understands and correctly executes the task.

The British mathematician Alan Turing proposed an abstract universal model in 1936 in order to illustrate the concept of an algorithm and to theoretically explore the possibilities of algorithms with the help of this model. It was a logical arithmetic construct and not a real physical calculating machine. Although computers did not exist back then, the model describes how a computer solves a formalized task in order to arrive at the result, and what requirements are placed on the algorithm so that the machine understands the task and executes it correctly.
 

 
The theoretical model of a computer invented by Turing was called the Turing machine. Turing wanted to use his model to prove either the existence or the impossibility of the existence of an algorithm for a particular task. The classic Turing machine is an extremely simplified model that can be expanded and “upgraded” as required in order to formalize, visualize, and describe more complex tasks. Operations that are carried out by modern real computers or implemented in network protocols can also be simulated in a Turing machine.

The Turing machine is a classic concept that originated before the computer era. The best way to imagine a Turing machine and to familiarize yourself with this concept is to convert the terms that Alan Turing originally used to describe his machine into common terms of modern information technology such as external data, read and write access, states, Commands, and actions translated. We will use such modern terms here because they are the basic concepts of computer science and make the operation of a Turing machine-understandable.
 

What is a Turing machine?

The classic Turing machine consists of an endless band divided into cells on both sides (as a data memory with read and write access for the current cell) and a machine that is controlled according to the predefined rules. According to the data (the character) of the currently read cell and the current status, the Turing machine carries out certain actions that are defined in the rules. The rules are specified in the form of a table and, like in a real computer, form the actual program according to which the Turing machine works when it solves a task. The table defines the corresponding actions for all permissible data that can be read from the band as letters of the external alphabet and for all possible states of the machine.
 

 
Possible actions include the transition to the new internal state of the machine, overwriting the data in the current cell, and moving the read/write head to the next (right or left) cell on the data strip. The rules defined in the table are the actual commands for the Turing machine when solving the specific task. The data on the band and the rules in the table are just as independent of each other as external data are from the algorithm. A rule defined in the table is determined on the basis of the data readout and the current status, and action results. The data on the band are, for example, external events that the Turing machine processes in accordance with the rules specified in the table in order to find and apply the appropriate actions in the table.

In order for you to be able to use a Turing machine to solve a specific task, you must describe the following components:

• External alphabet – a finite set, the elements of which are called letters (characters). One of the letters in this alphabet must be an empty character or a separator.
• Internal alphabet – a finite set of states of the automaton. One of the states (q1) must be initiated in order to start the program. Another state (q0) must be the state of the interruption in order to terminate the execution of the program.
• Transition table – it describes the behavior of the machine depending on its current state and the character currently being read.

A Turing machine can read out or overwrite the character of the current cell, position the read/write head to the nearest either left or right cell of the data band and change the internal status according to the data read out. All possible combinations of the internal states and the permitted external data are defined as rules in the table and determine which character should be written in the current cell, in which direction (to the left or right) the head should move and in which state the Automat passes over. Possible actions also include those that do not move the head to the next cell, do not overwrite the data of the current cell, or do not change the current state.
 

Example of a Turing machine

For example, suppose there is a word on the band that consists of the characters A, B, 1, and 0, for example, 1A0B10. The task is to replace all characters A and B with zeros. At the time of start, the head is on the left above the first letter of the word. The program ends when the head is above the blank character (a separator) after the last letter of the word.
 

 
The rules in the table are defined as follows:

• If the current character is 0, then move your head to the right (0 / ->).
• If the current character is 1, then move your head to the right (1 / ->).
• If the current character is A, then change the character to 0 and move your head to the right (A / 0, ->).
• If the current character is B then change the character to 0 and move your head to the right (B / 0, ->).

Step-by-step execution of the program while editing the letters one after the other, from left to right:

• Character (1): 1A0B10 -> 1A0B10
• Character (A): 1A0B10 -> 100B10
• Character (0): 100B10 -> 100B10
• Character (B): 100B10 -> 100010
• Character (1): 100010 -> 100010
• Character (0): 100010 -> 100010
• Character (separator): end

The resulting word at the end of program execution is 100010.
 

Conclusion

The Turing machine is one of the most fascinating and exciting intellectual discoveries of the 20th century. This is a simple and useful abstract computer model that is often enough to formalize any computer task and implement the algorithm found in a programming language. Thanks to a simple but universal and expandable concept, the Turing machine forms the basis of theoretical computer science. The concept leads to a deeper understanding of both digital computers and network protocols and digital communication.

With the help of the Turing machine, complex scientific computing problems were identified that cannot be solved with common computers and traditional sequential algorithms. However, it is to be expected that a quantum Turing machine for describing quantum algorithms for quantum computers will be invented, which will revolutionize computing of the future and lead to groundbreaking developments and technologies.
 

MCQPractice competitive and technical Multiple Choice Questions and Answers (MCQs) with simple and logical explanations to prepare for tests and interviews.Read More