• 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