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:
- Each and every function must be computable.
- 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.
- If any functions that follow above two assumptions must be states as computable function.
The Church-Turing thesis says that every solvable decision problem can be transformed into an equivalent Turing machine problem.
It can be explained in two ways, as given below −
- The Church-Turing thesis for decision problems.
- The extended Church-Turing thesis for decision problems.
Let us understand these two ways.
The Church-Turing thesis for decision problems
There is some effective procedure to solve any decision problem if and only if there is a Turing machine which halts for all input strings and solves the problem.
The extended Church-Turing thesis for decision problems
A decision problem Q is said to be partially solvable if and only if there is a Turing machine which accepts precisely the elements of Q whose answer is yes.
Proof
A proof by the Church-Turing thesis is a shortcut often taken in establishing the existence of a decision algorithm.
For any decision problem, rather than constructing a Turing machine solution, let us describe an effective procedure which solves the problem.
The Church-Turing thesis explains that a decision problem Q has a solution if and only if there is a Turing machine that determines the answer for every q ϵ Q. If no such Turing machine exists, the problem is said to be undecidable.
