The Turing machine is thought to be a very general model of computation. In 1936, logician Alonzo Church
advanced the thesis that any algorithmic procedure to manipulate symbols, conducted by humans or any
machine, can be conducted by some TM.
It is not possible to prove this proposition rigorously, for the notion of an algorithm is not specified mathematically.
However, the Church–Turing thesis has been widely tested, and is now accepted as true. One would
not want to write a TM for a complex task like designing a set of stairs for a staircase, but it could be done.
The significance of having such a model of computation is that the model has been used to show that some
tasks cannot be accomplished with a TM. If the Church–Turing thesis is true, then tasks for which a TM cannot
be successful are tasks which simply have no algorithmic solution.
No comments:
Post a Comment