In 1936, to define what method should be used to prove the axioms Hilbert’s Program, two mathematicians Alan Turing and Alonzo Church both defined the decidability of a problem and computability. The thesis is so called because Alan Turing and Alonzo Church both, independently, developed formalisms for defining what constitutes an algorithm. The two formalisms are equivalent.
Definition
Effectively Calculable
Effectively Calculable ^def-effectively-calculable
A function/method is effectively calculable if, and only if, it satisfies the following conditions as set out in the original thesis:
- There are exact instructions that are finite in length. It is possible to compute the function without any guessing or intuition, just following the steps.
- Given infinite time and resources, it must complete in finite time
- The instructions must be encoded in a finite set. For example, a binary function is encoded in
- The instructions can be computed by a human with unlimited time and an unlimited supply of pen and paper.
Thesis
Church-Turing Thesis ^def
Any effectively calculable method of computation is computable and equivalent to a Turing Machine
Examples of effectively computable methods include:
Alan Turing’s Turing Machine
Turing stated that any function can be run on a Turing machine is considered computable.
Alonzo Church’s Lambda Calculus
Alonzo Church created Lambda calculus as a way to define functions. In it, a function is first defined, and it’s arguments are put after it. Don’t need to cover on it too much (I think).