Textbook of AI

The Church–Turing thesis states that any function which can be computed by an "effective procedure", that is, by an algorithm in the informal pre-mathematical sense, can be computed by a Turing machine, equivalently by a term in Church's lambda calculus, equivalently by a partial recursive function. It is named for Alonzo Church and Alan Turing, who in 1936 independently produced the first two equivalent formal characterisations of effective computability.

The thesis is not a theorem and cannot be proved formally because one of its two sides, the informal notion of "effective procedure" , has no mathematical definition that the thesis itself does not provide. It is supported by the convergence of every reasonable model of computation ever proposed (lambda calculus, Turing machines, register machines, Markov algorithms, recursive functions, cellular automata, term rewriting, neural networks of sufficient capacity) to exactly the same class of computable functions, and by the fact that no convincing counterexample has ever been produced.

The thesis bounds what can be done by any AI system whose underlying physical substrate (silicon, neurons, photonic gates) is itself effectively computable. Hypercomputation, proposed models that exceed Turing-computability, such as oracle machines or analog computers exploiting infinite-precision real numbers, remains speculative and physically dubious. The thesis remains one of the most robust empirical generalisations in mathematics.