Church-Turing Thesis

Turing machines and counter programs are not the only mathematical models of algorithms; there are several others.

Surprisingly enough, all known models can be shown to be equivalent in terms of the problems they are capable of solving.

  
      Turing machines == counter programs
  		    == lambda calculus
  		    == Macintosh computers
  		    == Cray computers
  
  

The Church/Turing Thesis states that not only are these models all alike, but each captures the essence of computing or algorithmic problem solving (ie, effective computability)) which is by nature an intuitive notion.

• The Church/Turing thesis is a thesis, and not a theorem.

• All the evidence points to it being true.

In other words, if a problem can be solved by computer, it can be solved by a Turing machine; if it can't be solved by a Turing machine, it can't be solved by any computer.