In 1936, to calculate any computable function, the machine invented by “Alan Turing” was named “Turing Machine (TM)”. In computer science, TM is the abstract mathematical model of computation and primary theoretical construct. Turing machines work through a pre-programmed uncountable number of instructions. It plays an important role and helps the users find the computation by delimiting the “Computable Functions”.

This write-up will briefly explain Turing machines, their working, and computability theory.

What is Turing Machine?

The Turing machine was invented by Alan Turing. Initially, it was named an “a-machine (automatic machine)”. Later, this term was changed to “Turing Machine” by “Alonzo Church”, who was Turing’s doctoral advisor.

A Turing machine is a mathematical model of computation based on infinite instruction sets used to implement any computer algorithm. The manipulation of symbols is done according to a table of rules on a strip of tape.

How Does Turing Machine Work?

The Turing machine works with an infinite memory tape divided into individual cells. Each cell can keep one symbol drawn from an infinite set of symbols. These symbols are known as the machine alphabet. The machine has a “HEAD” that points to the starting state of implementing the computing algorithm.

Additionally, it can be moved over one of these cells to be positioned. The selection of “state” can be done from a finite set of states. HEAD reads the symbol (machine alphabets) from the cell in each step. After reading the cell symbol, the new symbol can be added to the same cell by the Turing machine. In the base of the new symbol, it can move the HEAD pointer one step right or left. It might be possible that the computation process halts.

What is Compatibility and Church’s thesis?

Compatibility is not just a-machine (Turing machine), a recursive function, Pascal programming language, or calculus, but the combination of all. Alonzo Church, Turing’s doctoral advisor, introduced this concept known as “Church’s Thesis”. It is also called the “Church-Turing Thesis”.

Moreover, it is not a theorem but is used to compare the computable function with the functions that can be computed by a-machine. Those functions that are not computable by a-machines, cannot be computed by another method. When the concept of the Church’s thesis was formulated, at that time, people did not know about the capability of modern computers, and it was such a significant achievement.

Turing Machines and Computability Theory

A natural number set is a decidable or Turing computable set. For instance, we have a Turing machine with the number “m”, which becomes halts when the output is 1 if “m” is in the computable set. On the other hand, it halts when the output is 0 if “m” is not in the natural number set. A function “r” from a natural number to a natural number is a “Turing computable”. It can be observed that not every natural number set is computable.

We have explained the concept of the Turing machine and the computability theory.

Conclusion

The Turing machine was invented by “Alan Turing” in 1938 to calculate any computable function. It is the abstract mathematical model of computation and a central theoretical construct in computer science. A Turing machine is a mathematical model of computation based on infinite instruction sets used to implement any computer algorithm. The manipulation of symbols is done according to a table of rules on a strip of tape. This write-up demonstrated the concepts of Turing machines and computability theory.