The Church-Turing Thesis
The text below consists of excerpts from an article on The Church-Turing Thesis 1. The article is an elaborate review of the thesis and related terminology. It relies on historical retrospectives and corrects common misconceptions in the field. Being comprehensive yet intelligible, it can be a good starting point for those who have ever wondered what that "church-turing thing" is really about. And the following excerpts are like an aperitif to stimulate the appetite of such a person.
1. The Thesis and its History
The Church-Turing thesis concerns the concept of an effective or systematic or mechanical method in logic, mathematics and computer science.
1.1 Making the informal concept of an effective method precise
One of Alan Turing’s achievements, in his famous paper of 1936, was to present a formally exact predicate with which the informal predicate “can be done by means of an effective method” may be replaced (Turing 1936). Alonzo Church, working independently, did the same (Church 1936a).
1.4 The Entscheidungsproblem
Church stated the Entscheidungsproblem more generally:
By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system. (Church 1936b: 41)A few months before Turing, Church arrived at the same negative result concerning the decidability of the functional calculus. They discovered this result quite independently of one another.
Thus, in Church’s proposal, the words “λ-definable function of positive integers” (and equally the words “recursive function of positive integers”) can be replaced by “function of positive integers that is computable by Turing machine”.
Notice, though, that while the two theses are equivalent in this sense, they nevertheless have distinct meanings and so are two different theses. One important difference between the two is that Turing’s thesis concerns computing machines, whereas Church’s does not.
1.7 Turing’s arguments for the thesis
Turing argued that, given his various assumptions about human computers, the work of any human computer can be taken over by a Turing machine.
Turing’s provability theorem:
Every formula provable in Hilbert’s first-order predicate calculus can be proved by the universal Turing machine. (See Turing 1936: 77)
2. Misunderstandings of the Thesis
Unfortunately a myth has arisen concerning Turing’s paper of 1936, namely that he there gave a treatment of the limits of mechanism, and established a fundamental result to the effect that the universal Turing machine can simulate the behaviour of any machine. This myth has passed into the philosophy of mind, theoretical psychology, cognitive science, computer science, Artificial Intelligence, Artificial Life, and elsewhere—generally to pernicious effect.
In reality Turing proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis that effective methods are to be identified with methods that the universal Turing machine is able to carry out.
2.1 Distant cousins of the Church-Turing thesis
… the thesis concerns what a human being can achieve when working by rote, with paper and pencil (ignoring contingencies such as boredom, death, or insufficiency of paper). The thesis carries no implication concerning the extent of what machines are capable of achieving …
2.2.1 Avoiding confusion: the term ‘computable’
A common formulation of the Church-Turing thesis in the technical literature is the following, where ‘computable’ is being used synonymously with ‘effectively computable’:
All computable functions are computable by Turing machine.
Turing himself uses ‘computable’ in this way, …
The terminological decision to tie the term ‘computable’ (and its cognates) to the concept of effectiveness does lead to the truth of:
No possible computing machine can generate a function that the universal Turing machine cannot.
2.3 Some consequences of misunderstanding the Church-Turing thesis
The error of confusing the Church-Turing thesis properly so called with one or another form of the maximality thesis has led to some remarkable claims in the foundations of psychology. For example, one frequently encounters the view that psychology must be capable of being expressed ultimately in terms of the Turing machine.
Footnotes:
Copeland, B. Jack, "The Church-Turing Thesis", The Stanford Encyclopedia of Philosophy (Summer 2020 Edition), Edward N. Zalta (ed.)
