**A Big Leap!**

- These
puny little computers are sufficient to execute any algorithm that we can
devise.

- In
particular, with some effort, we can simulate random access memory on a Turing
machine.

- Then
with some additional effort at formalizing the von Neumann model, we can simulate
**any program for any von Neumann computer**with a Turing machine.

- The Turing machine will be, in general, a significant amount slower (computational complexity!) than the von Neumann computer, but

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

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