What is the Turing machine?

Turing machine

The Turing machine is a computer device that consists of read and write header. It is a simple abstract computational device intended to help investigate the limitations of what can be computed. Nowadays we know it as a scanner and a paper ribbon that passes through the machine.

Alan Turing was the inventor of the Turing machine. He was known as an extremely talented man, who had great influences on the development of computing and on the formalization of the concept of algorithm and computation through his Turing machine, which played a very important role in the creation of the modern computer. Alan Turing termed this device as an “automatic machine” in 1936, and this machine was specifically devised for computing real numbers. Later, in 1937, Alonzo Church named this machine as “Turing machines” in a review of Turing’s paper. Today, they are considered to be one of the foundational models of computability and computer science.

Alan Mathison Turing

A Turing machine, like an algorithm, executes on an input string of bits. In the beginning, the input string is written on the tape, the tape head points to the first cell of the string, and all other cells are blank. During operation, the tape head is in a certain state. Every step, it consults the table (the set of transition functions), based on only the state it’s in and the symbol underneath the head, to obtain its next choice: either halt (end the operation), or resume by writing a symbol to the current cell, changing its state, and moving to the left or the right. This way, A Turing machine can simulate the fact that a program is made of many lines and thus it depends on what line a program is executing, and it can also simulate the fact that a program can react differently with different data in memory.

Turing machine consists of a tape that is initialized with a string of symbols. The machine has a head that reads and writes symbols as it moves along the tape. When the tape reads any particular symbol, it decides what to do depending on the set of transition functions associated with the machine. A transition function is essentially a specific instruction line in a Turing machine’s program. You can think of the set of transition functions as the complete program that specifies what the Turing machine should do on any valid input it receives.

The Turing machine has been used as a language generator because this type of machine has several tapes including an output tape that is empty at first and then filled with words of the language. It is also used in compilers I and II, state machines, automaton machines, and code generators. In past, it was used in machines like the “Bombe” which was a device used by the British cryptologists to decipher signals encrypted by the German machine “Enigma” during the Second World War. Also in the “Colossus” machines deciphered the encrypted messages intercepted in the communications of the Nazis.