h t t p s : / / p l a t o . s t a n f o r d . e d u / e n t r i e s / c h u r c h - t u r i n g /

Ingest: The Church-Turing Thesis (Stanford Encyclopedia of Philosophy)

Type: types/ingest-report.md · Tags: method-guided-action

Classification

This is secondary scholarship: a peer-reviewed encyclopedia entry (first published 1997, substantively revised 2023) that surveys the history and literature and also argues interpretive positions. Its main arguments are that the 1936 thesis concerns human computation, and that the "equivalence fallacy" and the maximality thesis must be kept separate from it. Those argued positions make it closer to a conceptual essay than to a neutral reference article. Turing's and Church's words reach the reader through Copeland's selection, translation, and framing. Author: B. Jack Copeland, a philosopher and historian of computing and the editor of Turing's collected essential writings. He is also a named proponent of computation beyond Turing machines (accelerating Turing machines, Copeland & Shagrir), which gives him a stake in the thesis-versus-maximality distinction he defends.

Summary

Copeland states the classical four conditions for an effective (equivalently "systematic" or "mechanical") method. The method consists of finitely many exact instructions. It produces the result in finitely many steps if carried out without error. An unaided human with paper and pencil can carry it out. It demands no insight, intuition, or ingenuity from that human. He stresses that these words are terms of art, not everyday senses. The Church-Turing thesis replaces this informal predicate with Turing-machine computability (or λ-definability or recursiveness). Its converse is easy, because a Turing-machine program is itself an effective method that a human can work through without insight. Copeland's central interpretive claim is that "computation" in 1936 meant the work of human rote-workers ("human clerical labour, working to fixed rules, and without understanding", Turing 1945). The thesis therefore bounds what a human following an effective method can do, not what machines can generate. Gandy's Thesis M and the maximality thesis are different claims, and inferring them from the convergence of Turing's, Church's, and Post's analyses is the "equivalence fallacy." The entry also covers Turing's argument from the essential features of human computation, including his "note of instructions" that replaces the computer's state of mind. It reports Turing's view that the thesis sits "between a theorem and a definition" and Post's objection to masking it as a definition. It then sorts later algorithmic, complexity, simulation, and physical "versions" that it treats as distant relatives of the original. Read it for a precise, historically grounded account of what "mechanical procedure" does and does not mean.

Quotes

  1. $M$ is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
  2. $M$ will, if carried out without error, produce the desired result in a finite number of steps;
  3. $M$ can (in practice or in principle) be carried out by a human being unaided by any machinery except paper and pencil;
  4. $M$ demands no insight, intuition, or ingenuity, on the part of the human being carrying out the method. --- kb/sources/.snapshots/church-turing-thesis-sep.md @ sha256:7960e199b0d98984f89d3e3b41f0adc29562a8ff16a2dbf799d0c59b97f178d1 — section 1, effective-method conditions

Turing introduced his machines with the intention of providing an idealized description of a certain human activity, the tedious one of numerical computation. --- kb/sources/.snapshots/church-turing-thesis-sep.md @ sha256:7960e199b0d98984f89d3e3b41f0adc29562a8ff16a2dbf799d0c59b97f178d1 — section 1.4

Connections Found

For the operationalization question, the source serves as the classical limiting case: the most precisely studied instance of a method made executable for a stated executor. The effective-method conditions name an operator (an unaided human), its available operations (paper, pencil, finitely many symbols), and a fidelity requirement (no insight). That is the operator-relative structure that actionable methodology defines (compares-with, axis: executor-relative executability). The effective method is the narrow end of that relation, because it excludes executor judgment entirely while actionability admits judgment-heavy operators.

The source also sharpens methodological and computational closure (compares-with, axis: what the method settles versus who supplies decisions). A human computer working an effective method is that note's "exact checklist, human applies" row: methodologically closed but not computationally closed. Together, the thesis and its converse say that every such row can move to the "validator executes" row, because a Turing machine can do the work. The "unattended agent using judgment" row is what the effective-method concept excludes by condition 4.

The source also acts as a bounding counterpoint for Naur's human-only conclusion (is-evidence-for). The classical notion of computation does equate machine execution with rote rule-following, and this supports reading Naur's bridge premise as an inherited classical assumption. Copeland's separation of the thesis from Thesis M and the maximality thesis shows that the thesis itself does not license extending that premise to all machines. The same axis connects the source to Programming as Theory Building (compares-with, axis: what formal rule-following execution can and cannot do). Naur's "formal symbol manipulation" is the concept that Turing's characterisation fixes.

Three executor-conformance links locate the classical origin of distinctions the KB already draws for LLM systems. Condition 4 is the requirement of zero semantic underspecification for the executor, which prompting changes failure diagnosis with the semantic reference treats as deliberately abandoned in LLM instructions (compares-with). Condition 2's "if carried out without error" builds into the definition the executor-conformance bracket that traditional software can bracket executor conformance attributes to classical stacks (compares-with). Competence theory and problem-solving method construction traces the commitments added while refining competence toward an operational method. The effective method marks the endpoint where refinement has removed every call on executor insight (compares-with).

The ingest originally identified a tension in the earlier codification criterion, which drew its boundary at a symbolic artifact with a unique operational semantics and excluded precise prose. The effective-method tradition treats exact instructions followed by a no-insight human as already "mechanical", and as equivalent to a Turing-machine program. The source does not settle whether codification's real criterion is notation or a consumer that does not reinterpret (compares-with).

Extractable Value

  1. Effectiveness is relative to the description counted as the method. Copeland says in passing that systems such as ChatGPT "implement effective methods." At the level of weights and inference code, an LLM run is mechanical in the technical sense. At the level of the retained task instructions, the same run supplies decisions that no method settled. "Operationalized for an executor" therefore has to name which artifact counts as the method. Otherwise "computationally closed but methodologically open" looks contradictory with classical computability. This bears on the distinctions among making knowledge usable, execution and automation, and it also bears on the closure note. The level-relativity framing is our inference from the source, not Copeland's argument. [deep-dive]
  2. For no-insight methods, operationalization entails automatability; beyond them it does not. The thesis plus its easy converse say that a method operationalized to the human-rote level (conditions 1–4) is exactly one a Turing machine can carry out. Human computers executing effective methods, later replaced by ACE "doing the work of about 10,000 computers", are a historical case of function-level automation following operationalization with no change in decision autonomy: zero decisions were left to either executor. This gives the comparison a clean baseline in which operationalization, execution, and automation come apart, and decision autonomy is held at zero. [quick-win]
  3. "Mechanical" and "computable" are terms of art; do not argue from the thesis to limits on machine judgment. The equivalence fallacy and the Thesis M distinction warn against reading the thesis as a ceiling on what machines (or LLM agents) can generate. They equally warn against reading "mechanical" as "without judgment-like output." This bounds the Naur bridge premise and any claim that automation requires prior effective operationalization. [quick-win]
  4. A defining predicate for executability may be a hypothesis in disguise. Turing calls "systematic method" an inexact everyday term, like "vegetable": ordinary acquaintance is not enough when every proposed method must be classified. He places the thesis "between a theorem and a definition." Post objects that masking the identification as a definition "blinds us to the need of its continual verification." A proposed definition of operationalization that replaces an informal predicate inherits the same status. It should be held as a tentative identification and tested against cases, not stipulated. [quick-win]
  5. Turing's "note of instructions" externalizes executor state. In argument III, the computer's state of mind is replaced by a written note that carries out one step and writes the next, so that the state of progress is "completely determined by the note of instructions and the symbols on the tape." It is a classical form of making an execution resumable from external artifacts alone. The source gives it no mechanism beyond the computability argument, so its transfer value is analogical. [just-a-reference]

Limitations (our opinion)

The entry is secondary scholarship. Attributions to Turing and Church are Copeland's selections and translations, and claims about what Turing meant (especially that his results concern human computers, not machines) are an interpretive position. Copeland's own work on accelerating Turing machines and hypercomputation gives him an interest in that position. The entry reports dissent (Kripke and Dershowitz–Gurevich on provability, and textbook algorithmic readings that omit the human computer), but the framing that later versions are "distant relatives" is Copeland's. Cite the source for the shape of the debate and for the four-condition definition. Do not cite it as settling what Turing intended.

The central concept is admittedly underspecified. The entry itself notes that condition 4, "no insight, intuition, or ingenuity", is left unexplicated. That condition is exactly where the operationalization question lives, so the source supplies a precise boundary on the formal side (Turing-machine computability) but no account of where insight begins. The source never discusses LLMs beyond a one-line remark. Every transfer to agent execution above (level relativity, the closure-table mapping, the codification tension) is our analogy and should be tested against the KB's own cases before being used as warrant. The capture is a full-source text extraction of the main entry. The linked supplementary document on the Entscheidungsproblem is not included. This analysis also relied mainly on sections 1, 4.3, 4.6, 5, 6.1–6.3 and 7, and gave only light attention to the historical backstory (sections 2–3) and the physical versions (6.4).

Use the effective-method case to check the distinction in methodological and computational closure: name which artifact counts as the method, and distinguish a no-insight executor from one supplying decisions the method does not settle.