|
A wide variety of models of computation have been proposed. With the exception of some strange mathematical models that we don't know how to build, no model that can compute more languages or functions than the Turing machine model has been found.
Some models compute a lot faster than Turing machines, but for the moment we are not concerned with computation speed. We will take that up later.
Let's adopt a notion of computability based on and intuitive notion of an algorithm (with the meaning that, to be an algorithm, a procedure must always eventually stop and reach an answer).
A language or function is computable if there is an algorithm that solves it.
The result of a long study of models of computation is the following.
The Church/Turing Thesis. The intuitive notion of computability corresponds exactly with the definition of Turing computability.
It is not possible to prove the Church/Turing thesis since one of its concepts, intuitive computability, is not carefully defined.
But the thesis allows us to drop the word Turing from computability, and simply talk about computability.
The thesis also allows us to describe algorithms in any convenient way. As long as the algorithm is clearly explained, it is possible to convert it to an equivalent Turing machine.
|