In this article, we have explain the meaning and importance of Church Turing Thesis in Theory of Computation along with its applications and limitations.

Table of contents:

1. Introduction to Turing Church Thesis
2. Applications of Church Turing Thesis
3. Limitations of Church Turing Thesis

Prerequisites: Algorithms, Turing Machine

Let us get started with Church Turing Thesis in Theory of Computation.

Definition of Church Turing Thesis

Church Turing Thesis states that:

A computation process that can be represented by an algorithm can be converted to a Turing Machine.

In simple words, any thing that can be done by an Algorithm can be done by a Turing Machine as well. So, all algorithms can be implemented in a Turing Machine.

Specific Computation Models are equivalent which means any one model can be coverted to another model. These Computation Models include:

• One tape Turing Machine
• K tape Turing Machine where K >= 1
• Non Deterministic Turing Machine
• Programs in Programming Languages such as Java, C++, Lisp and others.

So, a program in C++ can be converted to a K tape Turing Machine and vice versa.

Applications of Church Turing Thesis

The applications of Church Turing Thesis are as follows:

• Church Turing Thesis is used to define an Algorithm (traditionally)
• Used in solving 10th Problem by Hilbert.
• Used in defining modern computing devices including Molecular and Quantum Computers.

10th Problem by Hilbert

It has been used to solve the 10th Problem by Hilbert in 8th August 1900 at the Second International Congress of Mathematicians in Paris. These problems were listed as critical problems that should be solved for progress in Mathematics.

The 10th Problem by Hilbert was:

Does there exists a process with finite number of steps that can determine if a given polynomial with integer coefficients has integral roots?

Another way to look at the problem is to find if there is an Algorithm to find if there exists an integral root for a given polynomial or not.

For example:
This is a Polynomial:

35x¹⁰y²z⁹ + 11x⁶z⁷ + 103xyz + 17y³¹z³ = 0.

Is there an algorithm that can find if there exist a solution in integers?

Note the solution is not needed. Only we need to find if such a solution exists or not.

In 1970, it was proved that no such algorithm exists. This was done by Matiyasevich.

Algorithm = Church Turing Thesis

To solve the 10th Hilbert Problem, one needs to understand what is meant by an algorithm. In fact, there have been different definitions and all have proved to be equivalent. Some definitions were:

• 1936: Algorithm = Turing Machine
• 1936: Algorithm = Lambda Calculus
• 1970+: Algorithm = Implementation in Programming Languages like C and Lisp
• Final: Algorithm = process converted to Turing Machine.

Finally, it was agreed that an Algorithm is based on Church Turing Thesis which said:

"Any computational process can be considered as an Algorithm if it can be converted to a Turing Machine." Note: This does not hold true as of now.

Modern Computing Devices

Traditional Computers which are in use today, are limited by Church Turing Thesis. This is because Church Turing Thesis defines an Algorithm which can be implemented in a real system.

Therefore, the Computing Device you are using is basically a Turing Machine.

The only difference is that Computing Devices are efficient while Turing Machine is inefficient. Theoretically, from a point of view of algorithms, there is no difference.

There are 3 different approaches future computers may take:

• Quantum Computer: Solve Computing Problems using atoms by quantum rules. This is an active area of research.
• Molecular Computer: Solve Computing Problems using Molecules by taking advantage of Physical laws of Moleculars. This includes replicating the idea of DNA.
• Super Recursive Algorithm: This domain has not been realized yet and exists in theory but this is the part where Church Turing Thesis fail. We have covered this in the next section on "Limitations of Church Turing Thesis".

Two different futuristic models of Computer which follows Church Turing Thesis:

• Quantum Computers can be represented as Non Deterministic Turing Machine
• Molecular Computers can be represented by Turing Machine with many tapes and heads

Therefore, Quantum and Molecular Computers are same fundamentally and they are only more efficient than Mechnical Computers.

Limitations of Church Turing Thesis

Super Recursive Algorithms proved Church Turing Thesis wrong. The first Super Recursive algorithm was introduced in 1965 by Mark Gold and Hillary Putnam by using ideas of limit recursive and limit partial recursive functions. It was based on ideas from non standard analysis by Abraham Robinson in 1966 and Inductive Definition of sets by Spector in 1959. This resulted in Inductive Inference by Gasarch and Smith in 1997 and is used in Machine Learning.

Super Recursive Algorithms can solve problems that are unsolvable by Turing Machines. To account for this, a new idea was introduced: Inductive Turing Macine. These were not accepted as Algorithm for a long time as it was refuting Church Turing Thesis and Godel Incompleteness Theorem (as proved in 1987 by Burgin).

The idea of Inductive Turing Machine is as follows:

• Turing Machine has a property that it stops after giving a result.
• Most programs stop after giving a result and this seems to be reasonable as what a program should do once it has found the answer.
• Operating Systems are also programs but it does not give a standard output. It gives some strings to the users during its use but it cannot be considered as a output. The functionality of an Operating System is considered to be the output. It does not stop like standard program. If it stops, it cannot give any output.
• There can be programs which give a result at the moment which is good enough but
• This idea of not stopping after giving a result is the basis.

Inductive Turing Machine is more powerful than Conventional Turing Machine. Inductive Turing Machine can solve the Halting Problem which is known to be unsolvable by Conventional Turing Maching.

There are different types of Inductive Turing Machine:

• Inductive Turing Machine + Structured Memory
• Inductive Turing Machine + Structured Rules (control device)
• Inductive Turing Machine + Structured Head (Operating Device)

Today, Church Turing Thesis is not considered as an Universal Principle. Inductive Turing Machine is the most powerful super recursive algorithm.

This lead to the formulation of "Extended Church Turing Thesis".

There are three open questions:

• How to realize Super Recursive algorithms in technological devices?
• How modern computing devices are related to Super Recursive Algorithm?
• What are the new possibilities with Super Recursive Algorithm?

Think about these research open ended problems in Theory of Computation.

With this article at OpenGenus, you must have the complete idea of Church Turing Thesis in Theory of Computation.