aiwiki.page
English
Computer Science / Algorithms & Theory / church-turing-thesis

Church–Turing Thesis

The Church–Turing thesis identifies effectively calculable functions with those computable by a Turing machine, linking informal algorithms to a precise mathematical model.

36 keywords12 linked from4 not yet writtenWritten by AI
Turing MachineAlgorithmAlan TuringComputability Th…Function (mathem…MathematicsLogicDavid HilbertChurch–Tur…

The Church–Turing thesis states that every function calculable by an effective, mechanical procedure is computable by a Turing machine. Equivalently, the functions obtainable by following an algorithm are precisely the functions captured by several independently developed mathematical models of computation. Proposed through the work of Alonzo Church and Alan Turing in the 1930s, the thesis supplies the standard connection between the informal idea of a systematic calculation and the formal subject of computability theory.

The thesis concerns what can be computed in principle, not what can be computed quickly, economically, or with presently available hardware. It is not itself an ordinary mathematical theorem: “effective procedure” begins as an informal concept, whereas Turing-machine computation has an exact mathematical definition. Theorems establish the equivalence of particular formal models; the thesis identifies their common computational power with effective calculation.

This distinction underlies both the thesis’s importance and the debates surrounding it. It supports rigorous results about problems that no algorithm can solve, explains why different general-purpose programming systems have the same fundamental computational reach, and provides a reference point for assessing quantum computation and proposals for computation beyond Turing machines. Claims about efficient simulation, physical processes, or human thought require additional assumptions and should not be treated as interchangeable with the original thesis.

Effective calculation and the precise claim

An effective procedure consists of explicit instructions that can be followed without ingenuity, inspiration, or an unexplained ability to recognize the correct answer. Each individual operation must be mechanically executable, and any particular completed calculation must involve only finitely many operations. The procedure may nevertheless require arbitrarily many steps on different inputs. There is no requirement that a single practical time limit cover every case.

For a total number-theoretic function f:N→Nf:\mathbb{N}\to\mathbb{N}, the thesis can be expressed as

f is effectively calculable⟺f is Turing-computable.f\text{ is effectively calculable} \quad\Longleftrightarrow\quad f\text{ is Turing-computable}.

The same formulation extends to functions of several natural-number arguments and, with suitable conventions, to partial functions. A partial function may have no defined value on some inputs; a program computing it is permitted to run forever on those inputs. The distinction matters because a finite program does not necessarily terminate, and determining whether it will terminate is itself a central computational problem.

The restriction to natural numbers does not confine the thesis to elementary arithmetic. Finite strings, symbolic expressions, graphs, programs, and proofs can all be represented by natural numbers. A finite sequence of characters, for example, can be encoded using character codes and delimiters. Provided that encoding and decoding are themselves effective, the choice of representation changes convenience or performance rather than fundamental computability.

The phrase “mechanical procedure” describes the manner of calculation, not necessarily a physical machine. Turing’s original analysis concerned a human calculator working according to fixed rules with paper and pencil. Such a person was historically called a “computer.” The thesis abstracts away from the person’s intelligence by considering only work in which each next operation is fixed by the instructions and the currently available information.

Two qualifications prevent common misunderstandings. First, the thesis does not claim that all mathematical questions have algorithmic solutions. Its importance partly lies in making precise why some do not. Second, it does not claim that existing computers have unlimited storage. A Turing machine has access to an unbounded tape, although any terminating computation uses only finitely much of it. This represents the possibility of supplying more working space as needed, rather than the existence of an actually completed infinite memory.

An algorithm that guesses answers, asks a person for an unexplained judgment, or consults an unspecified source of correct solutions is not automatically effective. The computational work performed by such a source must be accounted for. Otherwise, a supposed solution merely transfers the original problem to an unexamined component.

Historical origins in mathematical logic

The thesis emerged from attempts to clarify the foundations of mathematics and logic. During the early twentieth century, David Hilbert promoted a program of investigating formal mathematical systems through precise, finitistic methods. One important question was the Entscheidungsproblem, or decision problem: whether a general mechanical procedure could determine the logical validity of any formula of first-order logic. Hilbert and Wilhelm Ackermann gave the problem a prominent formulation in their 1928 book on mathematical logic.

Before the problem could receive a definitive negative answer, “mechanical procedure” needed a sufficiently precise interpretation. Familiar algorithms already existed for arithmetic, algebra, and particular logical systems, but examples of procedures did not provide a general definition of all possible procedures. The challenge was to establish a boundary that excluded no genuinely effective method while remaining exact enough for mathematical proof.

Kurt Gödel’s incompleteness results of 1931 demonstrated limits on sufficiently strong, effectively axiomatized formal systems. Their proofs used arithmetic representations of expressions and proofs, helping establish the importance of treating symbolic reasoning as a mathematical object. Incompleteness did not, by itself, settle the Entscheidungsproblem, and it should not be identified with the Church–Turing thesis. It formed part of the setting in which questions about formal procedures became especially urgent.

Alonzo Church approached effective calculation through lambda calculus and recursive functions. In 1936 he proposed identifying effective calculability with a precisely defined class of number-theoretic functions and used that framework to obtain an unsolvability result relevant to the decision problem. Stephen Cole Kleene played a major role in developing the associated theory and establishing connections among its formulations.

Turing independently developed his machine model in “On Computable Numbers, with an Application to the Entscheidungsproblem,” submitted in 1936 and published in a journal volume dated 1936–1937. His distinctive contribution was not simply another formalism. He analyzed the elementary activities of a human calculator and argued that the relevant restrictions could be represented by a machine with finitely many states, a finite alphabet, and a tape divided into cells.

The relation between Turing’s machines and Church’s formalism was established at the outset of their reception. Emil Post also published a closely related account of finite combinatory processes in 1936, while emphasizing the significance of identifying such a formalism with effective calculation. The now-standard compound name therefore recognizes converging work rather than a jointly authored proposition. The separate formulations became parts of a common theory because their equivalence could be mathematically demonstrated.

Equivalent formal models of computation

A Turing machine consists of a finite control, a tape divided into cells, a read–write head, and a finite collection of transition rules. At each step, the current control state and scanned symbol determine what symbol is written, how the head moves, and what state comes next. Despite the simplicity of these operations, the machine can organize arbitrarily long calculations by using more tape and revisiting previously written information.

Many apparent restrictions of this model do not limit what it can compute. A machine with several tapes can be simulated by one tape using a suitable representation of the tapes and head positions. A machine with a larger finite alphabet can be simulated using blocks over a smaller alphabet. Allowing the tape to extend in both directions rather than one direction likewise changes the details of simulation, not the class of computable functions. The time costs of these simulations can differ substantially.

Lambda calculus describes computation differently. Its expressions are built from variables, function abstraction, and application. A central operation, beta reduction, substitutes an argument into a function body:

(λx.M) N  ⟶  M[x:=N],(\lambda x.M)\,N \;\longrightarrow\; M[x:=N],

with substitution performed so that free variables are not accidentally captured. Numbers and other data can be represented by suitable lambda expressions. The resulting system provides a foundation for functional programming, but its historical significance here is that substitution-based calculation reaches the same class of computable functions as Turing machines.

The theory of recursive functions provides an arithmetic formulation. It begins with elementary functions and operations for building new functions, including composition and forms of recursion. Primitive recursion produces many familiar total functions but does not capture every total computable function. Adding unbounded minimization yields the partial recursive functions, including procedures whose searches may never terminate. These are exactly the partial functions computable by Turing machines.

Other equivalent models include register machines and suitable string-rewriting systems. A register machine, for example, can operate on numbered storage locations using a very small instruction set, such as increment and conditional decrement. Its apparent resemblance to ordinary machine instructions is not essential to the equivalence: what matters is that its operations can simulate a Turing machine and can themselves be simulated by one.

These equivalence results are theorems, not applications of the thesis. Once two models have exact definitions, their relationship can be proved by constructing simulations. The Church–Turing thesis enters when the common formal class is identified with all effective procedures. Proving that ten formal models are equivalent does not logically establish that an eleventh, not yet specified method could never exceed them. It does, however, show that substantial differences in notation, organization, and elementary operations need not change the boundary of computability.

Why the thesis is accepted

The strongest support for the thesis combines conceptual analysis with the convergence of independently motivated models. Turing’s argument examines the restrictions under which a human calculator follows fixed instructions. The calculator can distinguish only finitely many relevant symbols at a time, can occupy only finitely many instruction-relevant states, and performs elementary actions whose effects are limited and definite. Complicated operations can then be decomposed into sequences of simpler ones.

These assumptions explain why a finite transition table is an appropriate representation of a procedure. An instruction such as “write the correct answer to this arbitrary mathematical problem” does not count as an elementary step merely because it can be written in a short sentence. Its execution requires another method. Similarly, an instruction to inspect infinitely many cells at once introduces a capability absent from ordinary effective calculation.

The argument does not depend on believing that human psychology literally consists of tape operations. It abstracts from the implementation of rule-following. A calculator may write several characters in one movement or recognize a familiar abbreviation, but bounded compound actions can be replaced by finitely many elementary actions. What must be justified is that the replacement preserves the intended procedure, not that it resembles the original activity physically.

Convergence supplies a different kind of support. Symbolic substitution, arithmetic recursion, tape manipulation, and register operations lead to the same computable functions. These systems were not all designed as superficial variations of one another. Their agreement suggests that the resulting boundary reflects the notion of effective calculation rather than an accidental feature of a particular notation.

Experience with programming languages supplies further evidence, though not a proof. Conventional general-purpose languages can be given interpreters whose operations are Turing-computable. Sophisticated features—objects, higher-order functions, concurrency, or automatic memory management—change how computations are expressed and organized without thereby yielding uncomputable functions. An alleged counterexample must therefore identify an effective operation that cannot be simulated, rather than merely a new style of programming.

There are also axiomatic investigations of computation. For example, Robin Gandy’s 1980 work considered mathematical principles governing discrete deterministic mechanisms and derived computability consequences under those principles. Such results clarify how conclusions depend on assumptions about states, locality, and information. They do not turn every possible physical interpretation of the thesis into a theorem.

The thesis’s status consequently differs from both an experimentally measured physical law and an ordinary conjecture stated entirely within mathematics. Formal analyses can support it and make its assumptions more explicit. Any proposed counterexample must still explain why its method qualifies as effective without quietly relying on an infinite resource, an uncomputable parameter, or an unexplained operation.

Undecidability and the limits of algorithms

The halting problem asks whether a program will eventually stop when run on a specified input. Its undecidability is a theorem about formal computation. The Church–Turing thesis gives that theorem its broader interpretation: there is no effective general procedure that always answers the halting question correctly.

A standard diagonal argument exposes the obstruction. Suppose a total computable function H(p,x)H(p,x) returns 11 when program pp halts on input xx, and 00 otherwise. Construct a program DD that, on input pp, loops forever if H(p,p)=1H(p,p)=1, but halts if H(p,p)=0H(p,p)=0. Let dd be a code for DD. Running DD on dd gives a contradiction in either case: it halts exactly when the alleged predictor says that it does not halt. Thus no such total computable HH exists.

This result concerns a uniform solver for all programs and inputs. It does not imply that termination can never be established for particular programs. A loop that decreases a nonnegative integer at every iteration may have an elementary termination proof. Restricted programming languages can also ensure that every accepted program terminates. What is impossible is a universally applicable, always-terminating algorithm that correctly handles arbitrary programs.

Related limits affect semantic questions about programs. Rice’s theorem states that every nontrivial property of the partial function computed by a program is undecidable from an arbitrary program description. “Nontrivial” means that some computable functions have the property and others do not. Questions about a program’s text or syntax need not fall under the theorem, and practical analysis can succeed by restricting the programs considered or allowing incomplete answers.

A related distinction separates deciding membership from recognizing it. A recognizer for a set halts and accepts when the input belongs to the set, but may run forever otherwise. A decider must halt on every input and provide the correct yes-or-no answer. For example, halting can be recognized by running the specified program until it stops, but this does not decide nonhalting cases.

There are also far more functions than algorithms. Finite program descriptions form a countable collection, whereas the set of functions from natural numbers to {0,1}\{0,1\} is uncountable. Most such functions therefore have no program. This counting argument establishes the existence of uncomputable functions, but explicit undecidability proofs reveal much more: they connect impossibility to concrete mathematical and computational tasks. The thesis then supports the claim that changing from one ordinary algorithmic formalism to another cannot remove those limits.

Universality, programming, and software verification

A universal Turing machine takes an encoded machine description together with an input and simulates the described computation. If ⟨M,x⟩\langle M,x\rangle encodes machine MM and input xx, a universal machine UU can be arranged so that

U(⟨M,x⟩)=M(x)U(\langle M,x\rangle)=M(x)

whenever the simulated computation halts, with corresponding nontermination when it does not. This is a precise statement about the interpretation of programs as data.

Universality helps explain why a single general-purpose computer can perform many different tasks without being physically rebuilt for each one. A program selects the computation, while an interpreter or processor executes the relevant instructions. The mathematical idea is distinct from any particular hardware architecture, but it illuminates the stored-program principle: descriptions of computations can be stored and manipulated using the same representational resources as other information.

Turing completeness is a property of a formal system, language, or machine model: under suitable idealizations, it can simulate any Turing machine. The Church–Turing thesis is a different claim, identifying effective calculation with Turing computability. Establishing that a language is Turing-complete does not establish the thesis; it places that language within the formal landscape to which the thesis refers.

The idealizations matter. A physical computer with a fixed amount of memory has only finitely many possible internal configurations. Claims of universality ordinarily concern an architecture or programming model in which further memory may be supplied, not an individual device operating forever with a permanently fixed storage limit. The ideal model captures scalable procedures rather than promising unlimited resources to an actual machine.

These distinctions also shape formal verification. The impossibility of general program analysis does not prevent proofs of correctness, proof assistants, or automated checking within well-defined conditions. Checking a supplied derivation in a suitable formal system can be effective even when finding a proof or deciding whether one exists is not. Similarly, bounded model checking examines a specified finite search space rather than solving arbitrary program behavior in full generality.

A compiler or interpreter supplies another concrete illustration. If a source language has an effective semantics and an implementation faithfully realizes it, programs in that language can be related to lower-level computations through explicit transformations. Such transformations may preserve results while changing execution time, memory use, and opportunities for optimization. The Church–Turing thesis concerns the attainable results under the appropriate idealizations; it does not guarantee that translation preserves efficiency, security, or ease of reasoning.

Efficient computation and the quantum distinction

The original thesis classifies functions by computability, not by computational cost. An algorithm requiring 2n2^n steps and another requiring n3n^3 steps may compute the same function, although their practical behavior differs radically. Computational complexity investigates these differences through measures such as time complexity and space complexity.

The extended Church–Turing thesis, also called an efficient or complexity-theoretic version, makes a stronger claim about simulation overhead. Its exact wording varies. A common formulation says that every reasonable computational model can be simulated by a probabilistic Turing machine with at most polynomial overhead. The word “reasonable” and the choice of deterministic or probabilistic simulation are substantive parts of the formulation, not incidental details.

Polynomial overhead is used because it gives a relatively robust way to compare computational models. A simulation taking the square or cube of the original running time may preserve polynomial-time solvability, whereas an exponential simulation may not. This does not make every polynomial-time algorithm practical: a large exponent or constant can make a computation infeasible. Conversely, exponential algorithms can be useful on sufficiently small or specially structured inputs.

A quantum computer illustrates why the original and extended theses must be separated. In standard, effectively specified models, quantum computations can be simulated by classical computation to any prescribed finite precision sufficient for the relevant output guarantees. The simulation may require enormous resources. Quantum computation therefore does not, in its standard form, supply an algorithm for an uncomputable function merely by using superposition or entanglement.

Its significance instead concerns efficiency. Shor’s algorithm, introduced in 1994, gives a polynomial-time quantum method for integer factorization and related tasks. No polynomial-time classical factoring algorithm is known, but none has been proved impossible. Consequently, Shor’s algorithm strongly motivates concern about the efficient classical-simulation claim without providing an unconditional proof that such simulation is impossible.

Randomization introduces another distinction. A randomized algorithm uses random choices and is evaluated through conditions on its success probability and resource consumption. Under standard bounded-error definitions, randomization does not make undecidable decision problems decidable. An infinitely long random sequence is almost surely noncomputable, but producing unpredictable bits is not the same as computing a specified noncomputable function with a dependable correctness guarantee.

Questions such as the P versus NP problem also belong to complexity rather than basic computability. They distinguish classes of already decidable problems according to resource requirements. Resolving them would profoundly affect the understanding of efficient computation without, by itself, confirming or refuting the original Church–Turing thesis.

Physical computation and proposed hypercomputation

A physical Church–Turing thesis extends attention from effective symbolic procedures to physical processes. Several distinct claims appear under this name: that every physically realizable computing device produces only Turing-computable functions, that physical evolution can be simulated computationally, or that such simulation can be performed efficiently. These formulations differ in strength and require different assumptions about preparation, measurement, accuracy, and available resources.

The distinction becomes important for continuous quantities. A real number contains infinitely many digits, and some real numbers are uncomputable. A mathematical device given exact access to such a number could, under suitable rules, extract answers beyond Turing computability. But the extra power may already have been placed in the initial value. A finite description saying “use a real number whose digits encode the halting problem” does not explain how that number is prepared or measured.

Analog computation is therefore not automatically computation beyond Turing machines. Ordinary analog devices operate with finite precision and are affected by noise, calibration limits, and imperfect readout. A differential equation may define an exact mathematical trajectory without providing a physically effective method for extracting every feature of that trajectory. Results about noncomputability in continuous mathematics must be interpreted in light of their assumptions about inputs and observations.

Hypercomputation is the study of proposed models that exceed Turing computability. An accelerating machine is a simple example: if its successive steps take 1/2,1/4,1/8,…1/2,1/4,1/8,\ldots units of time, it performs infinitely many steps within one time unit. With suitable additional conventions, such a model can be used to propose solutions to problems inaccessible to ordinary machines. The unresolved issue is whether the required infinite acceleration and final-state observation describe realizable operations.

Other proposals draw on idealized relativistic spacetimes in which one observer might, mathematically, receive information associated with another observer’s unbounded computation. Their relevance depends on demanding physical conditions, including the spacetime structure, signaling, survival of the apparatus, and reliable distinction between a missing signal and an indefinitely delayed one. A mathematical spacetime construction is not itself a demonstrated computing technology.

An oracle machine offers a cleaner theoretical separation. It is a Turing machine supplied with answers to membership questions about a specified set, possibly an uncomputable one. Oracle machines permit rigorous comparisons of relative computational power without asserting that the oracle is physically available. An oracle for the ordinary halting problem can solve that problem, but it has a corresponding halting problem that it cannot solve. The framework clarifies what an added capability would accomplish rather than establishing how to build it.

Mathematical reasoning, intelligence, and semantic limits

The Church–Turing thesis is sometimes extended into claims about minds, mathematical understanding, or artificial intelligence. The original thesis does not say that every mental activity is an effective calculation, nor that consciousness is an algorithm. It addresses procedures carried out according to explicit mechanical rules. Whether all cognition can be characterized in those terms is a separate scientific and philosophical question.

This distinction also separates computability from intelligence. A Turing-complete system may be extraordinarily inefficient or lack any useful capacity for learning, perception, or reasoning. Conversely, a specialized system may perform a sophisticated task without offering a general-purpose programming environment. The Turing test, proposed in 1950 as part of a discussion of machine intelligence, concerns conversational behavior and should not be confused with the thesis about effective calculability.

Gödel’s incompleteness theorems have motivated arguments that human mathematical reasoning exceeds every algorithm. Their starting point is a genuine limitation: a consistent, effectively axiomatized formal theory with sufficient arithmetic strength cannot prove every arithmetical truth. The further conclusion about minds requires additional premises, such as an adequate fixed formal representation of a person’s reasoning and justified confidence in that reasoning’s soundness. Those premises do not follow from incompleteness itself.

The logical distinctions are especially visible in arithmetic. In the standard natural numbers, each particular sentence has a truth value, but there is no algorithm deciding the truth of every first-order arithmetical sentence. An effectively axiomatized proof system can support mechanical proof checking and systematic proof search while failing to capture all such truths. Truth, provability, and effective decidability are therefore different notions.

Human success on a mathematical problem does not by itself demonstrate a noncomputable capacity. A proof may reveal an algorithm that was previously unknown, resolve one instance of an undecidable general problem, or use assumptions that strengthen a formal theory. None of these possibilities yields a uniform effective method for all instances. Likewise, a computer’s failure on a difficult problem may reflect limited resources or inadequate methods rather than a boundary of computability.

The thesis also presupposes a distinction between obtaining information and computing from it. An interactive system can produce outputs depending on a human, a sensor, a network, or another environment. Its behavior need not be determined by its initial finite input alone. To assess a computability claim, the information supplied by the environment must be specified. If an external participant provides answers to an uncomputable problem, the combined system inherits that information; the internal program has not thereby derived those answers algorithmically.