4.4. Church-Turing thesis

As we have discussed at the beginning of the chapter, an algorithm can be regarded as a function on words. The input word is called the task and the output word is called the solution.

By the definitions above, Turing machines represents similar functions.

The question arises naturally, which tasks can be solved by a Turing machine. The following statement approaches this question.

Church-Turing thesis 4.13.

Let  be an algorithm transforming words to words, 
i.e. .
Then there exists a Turing machine  such
that .

Remark 4.14.

1. If  does not terminate on a given input ,
   then  is undefined and hence we should 
   assume that  does not terminate, too.
2. The Church-Turing thesis can be applied both
   on the transformationa and decision tasks.
   In the latter case the output of the algorithm
   is not a word, but a decision. (e.g. yes or no.)

Observing the Church-Turing thesis one may find that the concept of algorithms has no mathematical definition. It implies that the statement has no mathematical proof, although it has a truth value. It is rather unusual, but only disproof may exist - if the thesis is wrong. To do this, it is enough to find a task, which can be solved by some method - regarded as an algorithm - and can be proven to be unsolvable by a Turing machine.

The first appearance of the thesis is around the years 1930. Since then, there are no disproof, although many people tried to find one. A standard method for this, is to define a new algorithm model and try to find a task which can be solved by it, but not with a Turing machine. However, until now, all model was proven to be not stronger than the model of the Turing machine. If the class of solvable tasks for the observed model is the same as in the case of Turing machines, it is called Turing equivalent.

Some of the most well known Turing equivalent algorithm models: