Questions: The Church-Turing Thesis

Question 1

Why is the Church-Turing thesis called a 'thesis' rather than a 'theorem'?

• A. It has been proven for all known models of computation but not for future ones
• B. The concept 'effectively computable' cannot be formally defined without circularity, so the claim cannot be formally proved
• C. Mathematicians informally agreed not to attempt a proof
• D. It was proposed before the formal definition of a Turing machine existed

Answer: (B)

A theorem requires a precise formal statement. The thesis links Turing computability (formal) to 'effective computability' (informal — what a person can compute by following a definite procedure). Defining 'effective computability' precisely without essentially invoking Turing machines would be circular, making the thesis an empirical claim rather than a mathematical one.

Question 2

The Church-Turing thesis implies that quantum computers can solve problems that Turing machines can seldom solve at most.

• T. True
• F. False

Answer: False

Quantum computers can solve some problems *faster* (e.g., integer factorization), but they compute the same *class* of functions as Turing machines. Every function computable by a quantum computer is also computable by a Turing machine — just potentially much more slowly. The halting problem remains undecidable for quantum computers just as for classical ones. The thesis is about computability, not efficiency.

Question 3

What is the primary empirical evidence that supports the Church-Turing thesis, even though it cannot be formally proved?

Model answer: The convergence of independently invented models of computation — Turing machines, Church's lambda calculus, Kleene's general recursive functions, register machines, and others — all turned out to compute exactly the same class of functions, despite being motivated by completely different mathematical intuitions.

The robustness of this convergence across fully independent formalisms is strong evidence that the boundary of computability reflects something objective about mechanical procedure, not an artifact of any particular model. No model ever proposed that is intuitively 'mechanical' has been shown to compute strictly more than Turing machines.