THE CHURCH-TURING THESIS: EVERY FUNCTION THAT IS "EFFECTIVELY CALCULABLE" — computable by any mechanical procedure whatsoever — IS COMPUTABLE BY A TURING MACHINE. ── WHY IT IS NOT A THEOREM ───────────────────────────────── IT CANNOT BE PROVED, and the reason is precise: it relates a FORMAL notion (Turing computability, defined exactly) to an INFORMAL one (effective procedure, an intuitive idea about what counts as a mechanical method). YOU CANNOT PROVE A THEOREM ABOUT AN UNDEFINED TERM. To prove it, one would first have to define "effective procedure" formally — and then the thesis would become the claim that THAT definition is the right one, which is the same problem again. WHAT AN "EFFECTIVE PROCEDURE" INFORMALLY MEANS: · a FINITE set of precise instructions · each step is elementary and mechanical · it requires no insight, creativity or luck · it produces its result in FINITELY many steps when it succeeds · it can be carried out by a person with paper and pencil, given unlimited time and paper TURING'S 1936 PAPER ARGUES DIRECTLY FROM THIS LAST IMAGE — he analyses what a human "computer" following rules can do, and shows the machine captures it. THAT ANALYSIS, RATHER THAN ANY THEOREM, IS THE ORIGINAL EVIDENCE. ── THE EVIDENCE: CONVERGENCE ─────────────────────────────── Several formalisations were proposed independently, from different starting points, and ALL PROVED EQUIVALENT: 1936 TURING MACHINES Turing — from machines 1936 λ-CALCULUS Church — from functions 1930s μ-RECURSIVE FUNCTIONS Gödel, Kleene — from logic 1936 POST SYSTEMS Post — from symbol manipulation 1961 REGISTER MACHINES Minsky 1936 COMBINATORY LOGIC Curry, Schönfinkel CELLULAR AUTOMATA von Neumann, Conway every programming language ever designed THREE OF THESE APPEARED IN THE SAME YEAR, BY PEOPLE WHO WERE NOT COLLABORATING, APPROACHING COMPUTATION FROM MACHINES, FROM FUNCTIONS AND FROM LOGIC — AND THEY LANDED ON EXACTLY THE SAME CLASS. THE SECOND STRAND OF EVIDENCE: EVERY ATTEMPT TO STRENGTHEN THE MODEL HAS FAILED. multiple tapes, multiple tracks, two-way tapes, non-determinism, multiple heads, two-dimensional tapes, random access, parallelism — NONE ADDS COMPUTATIONAL POWER. THE THIRD: NINETY YEARS AND NO COUNTEREXAMPLE. Nobody has exhibited a procedure that is intuitively effective and not Turing computable. ── THE TWO VERSIONS ──────────────────────────────────────── THE CLASSICAL THESIS — about COMPUTABILITY: anything effectively calculable is Turing computable UNIVERSALLY ACCEPTED. THE EXTENDED (COMPLEXITY-THEORETIC) THESIS — about EFFICIENCY: any reasonable model simulates a Turing machine with at most POLYNOMIAL overhead ALSO WIDELY ACCEPTED BUT MORE CONTENTIOUS, since QUANTUM COMPUTERS may violate it. Shor's algorithm factors integers in polynomial time on a quantum computer, and no polynomial classical algorithm is known. NOTE CAREFULLY WHAT THAT DOES AND DOES NOT THREATEN: A QUANTUM COMPUTER COMPUTES EXACTLY THE SAME FUNCTIONS AS A TURING MACHINE. It challenges the EXTENDED thesis about speed, and leaves the classical thesis about computability entirely untouched. ── WHAT THE THESIS BUYS ──────────────────────────────────── 1. IT LICENSES HIGH-LEVEL DESCRIPTIONS. Having argued informally that an algorithm exists, one may assert that a Turing machine exists without constructing it. EVERY PROOF IN THIS SECTION RELIES ON THIS, and so does every exam answer that says "the machine simulates M on w". 2. IT MAKES IMPOSSIBILITY RESULTS MEANINGFUL. "The halting problem is undecidable" becomes "NO PROCEDURE OF ANY KIND CAN DECIDE HALTING", rather than a limitation of one model. 3. IT UNIFIES THE FIELD. Computability is a property of PROBLEMS, not of machines or languages, so results transfer between them freely. 4. IT SETS THE AGENDA. Once the boundary of the computable is fixed, the interesting questions move to COMPLEXITY — not what can be computed but what can be computed AFFORDABLY.

── CANDIDATE COUNTEREXAMPLES, AND WHY THEY FAIL ──────────── QUANTUM COMPUTERS Compute exactly the Turing-computable functions. Believed faster on some problems; NOT more powerful. THE CLASSICAL THESIS IS UNAFFECTED. ANALOGUE COMPUTERS A physical quantity varying continuously appears to hold infinite information. IN PRACTICE, NOISE AND FINITE PRECISION DESTROY THIS — no measurement extracts unbounded information from a physical quantity. Idealised infinite-precision analogue machines can exceed Turing machines on paper, but they are not physically realisable. ORACLE MACHINES A Turing machine with a black box answering some undecidable question CAN decide more. But THE ORACLE IS NOT AN EFFECTIVE PROCEDURE — it is assumed, not implemented. So the thesis is untouched; oracles are a proof technique, not a machine. HYPERCOMPUTATION Proposals such as machines performing infinitely many steps in finite time ("Zeno machines"), or exploiting exotic spacetimes. NONE IS PHYSICALLY REALISABLE ON ANY EVIDENCE, and each assumes some infinity that physics does not obviously supply. THE HUMAN MIND The one genuinely open question, and it is philosophical rather than mathematical. IF THE BRAIN IS A PHYSICAL SYSTEM OBEYING COMPUTABLE PHYSICAL LAWS, IT IS TURING EQUIVALENT. Roger Penrose has argued from Gödel's theorem that mathematical insight exceeds any algorithm; most logicians reject the argument, and the matter is unresolved because nobody knows how to formalise "understanding". ── WHAT THE THESIS DOES **NOT** CLAIM ────────────────────── Three misreadings worth naming, because each appears in weak exam answers: IT DOES NOT SAY EVERY PROBLEM IS SOLVABLE. Quite the reverse — it makes it possible to prove that some are not. IT DOES NOT SAY COMPUTATION IS EFFICIENT. It concerns what is computable AT ALL, with no reference to time or space. IT DOES NOT SAY BRAINS ARE COMPUTERS. It says anything computable by an effective procedure is Turing computable, which is silent on whether thought is such a procedure. ── THE PHYSICAL CHURCH-TURING THESIS ─────────────────────── A stronger and genuinely empirical claim: EVERY PHYSICALLY REALISABLE PROCESS CAN BE SIMULATED BY A TURING MACHINE. THIS IS A STATEMENT ABOUT THE UNIVERSE, NOT ABOUT MATHEMATICS, and could in principle be REFUTED BY EXPERIMENT — by building a device that computes something uncomputable. NO SUCH DEVICE HAS EVER BEEN BUILT OR CREDIBLY PROPOSED. ── THE PRACTICAL UPSHOT ──────────────────────────────────── FOR AN ENGINEER, THE THESIS HAS ONE OPERATIONAL CONSEQUENCE: IF A PROBLEM IS PROVED UNDECIDABLE, NO PROGRAMMING LANGUAGE, NO HARDWARE, NO CLEVERNESS AND NO FUTURE TECHNOLOGY WILL SOLVE IT IN GENERAL. The correct engineering response is never to search harder for the general algorithm. IT IS TO CHANGE THE PROBLEM: · solve a RESTRICTED case that is decidable · accept an APPROXIMATE answer · accept a CONSERVATIVE answer that is sometimes wrong in a safe direction · require the user to supply a HINT the machine cannot infer THIS IS EXACTLY WHAT REAL TOOLS DO. A type checker rejects some safe programs because deciding safety exactly is undecidable; a static analyser reports possible null dereferences including false positives; a compiler bounds its optimisation effort rather than seeking the optimal program. EACH IS A DELIBERATE RETREAT FROM AN UNDECIDABLE PROBLEM TO A DECIDABLE APPROXIMATION OF IT, and recognising when that retreat is necessary is the practical value of this entire section.