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.(Quote is on page 501).
CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000