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