# Church-Turing thesis

## Summary

The Church-Turing thesis is the hypothesis that any function which can be computed (by any deterministic procedure) can be computed by a Turing machine. Equivalently, it holds that a function is recursive if and only if it is computable. While this thesis is not a precise mathematical statement, and therefore cannot be proved, it is almost universally held to be true.

## Context

This concept has the prerequisites:

- Turing machines (The Church-Turing thesis references Turing machines.)
- decidability (The Church-Turing thesis is about decidability.)
- recursive functions (One formulation of the Church-Turing thesis is that a function is computable if and only if it is recursive.)

## Goals

- Know the statement of the Church-Turing thesis

- Know why it is not a precise mathematical statement

- Show that Turing machines and lambda calculus are equivalent

- Show that a function is recursive iff it is computable (by some Turing-complete formalism)

## Core resources (read/watch one of the following)

## -Paid-

→ A Mathematical Introduction to Logic

An undergraduate textbook in mathematical logic, with proofs.

Location:
Section 3.3. "A subtheory of number theory," subsection "Church's Thesis," pages 206-210

Additional dependencies:

- representability in arithmetic

Other notes:

- The definition of recursive functions (i.e. those representable in axiomatic number theory) is different from (but equivalent to) the usual one.

→ A Course in Mathematical Logic

A graduate textbook in mathematical logic.

- Section 6.5, "Recursive functionals and functions," starting with Theorem 5.5, pages 242-247
- Section 6.7, "Church's Thesis," pages 257-259
- Section 6.8, "Recursiveness of computable functionals," pages 259-265

Additional dependencies:

- register machines

## Supplemental resources (the following are optional, but you may find them useful)

## -Free-

→ Stanford Encyclopedia of Philosophy

## See also

-No Additional Notes-