Through many successful simulations of different models of computation on a Turing machine over many decades, mathematicians and computer scientists have become convinced that the Turing machine model is a sufficiently powerful model to serve as the formal definition of the concept of an algorithm.

Said a different way, the Church-Turing thesis holds:

If there is an algorithm to do a symbol manipulation task, then there is a Turing machine to do that task.

CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000