Church’s Thesis

In 1936, A method named as lambda-calculus was created by Alonzo Church in which the Church numerals are well defined, i.e. the encoding of natural numbers. Also in 1936, Turing machines (earlier called theoretical model for machines) was created by Alan Turing, that is used for manipulating the symbols of string with the help of tape.

Church Turing Thesis :

Turing machine is defined as an abstract representation of a computing device such as hardware in computers. Alan Turing proposed Logical Computing Machines (LCMs), i.e. Turing’s expressions for Turing Machines. This was done to define algorithms properly. So, Church made a mechanical method named as ‘M’ for manipulation of strings by using logic and mathematics.

This method M must pass the following statements:

• Number of instructions in M must be finite.
• Output should be produced after performing finite number of steps.
• It should not be imaginary, i.e. can be made in real life.
• It should not require any complex understanding.

Using these statements Church proposed a hypothesis called Church’s Turing thesis that can be stated as: “The assumption that the intuitive notion of computable functions can be identified with partial recursive functions.”

In 1930, this statement was first formulated by Alonzo Church and is usually referred to as Church’s thesis, or the Church-Turing thesis. However, this hypothesis cannot be proved.

The recursive functions can be computable after taking following assumptions:

1. Each and every function must be computable.
2. Let ‘F’ be the computable function and after performing some elementary operations to ‘F’, it will transform a new function ‘G’ then this function ‘G’ automatically becomes the computable function.
3. If any functions that follow above two assumptions must be states as computable function.