A Big Leap!

it is capable of solving any problem that can be solved on that computer


Church-Turing Thesis


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