If you are in the air and your problems are complex, try to stop them.

From the model of the mechanical machines  to the automatic computation machines: the step between the two approaches was required, because the tools were needed for assessing the complexity of the algorithms and the calculation of the physical resources.  Alan Mathison Turing, a british mathematician, logician and cryptographer , was one of the founders of the theory of computability of the algorithms through the invention of the “Turing machine” in the 1936 by publishing an article which was entitled: “On computable numbers, with an application to the Entscheidungs problem”. In wider terms a “Turing machine” is a model of abstract machine, not physical, it’s equipped with a head and a tape and it is able to perform operations of reading and writing. The head of the machine evolves along a belt where a string is placed  that represents the input data of a problem P. An evolution of this machine consists of a sequence of its possible configurations of a string of finite length. But if you are using a Turing machine with an open-ended evolution for calculating the prime numbers, Mersenne numbers (we consider as infinite the resources of space and time on the machine), you want to know if the machine will stop or not following the computation. This problem is known as the halting problem. There is an universal Turing machine which is capable to simulate every possible configuration of the Turing machine, but is not able to decide in each case the halting problem. No Turing machine can do it. This negative result, which is called the Church-Turing conjecture, is expressed by saying that the halting problem is Turing-undecidable. This negative result constitutes a limit for all computational mechanisms; it constitutes a limiting result of great general importance and for the study of the algorithms.



Turing machine


Comments are closed.