What exactly is Turing Completeness?
Evin Sellin's long-form explainer is a useful map of the questions software engineers ask about Turing completeness, but several historical, formal, and resource-boundary claims require correction before reuse.
Evin Sellin's article is unusually ambitious for a software-engineering explainer. It moves from Turing's original sequence-producing machines to description numbers, universal interpretation, modern programming-language claims, bounded implementations, incomputability, oracles, and the Church-Turing thesis. That breadth makes it a valuable question map. It does not make the article a technical authority: the author explicitly presents the piece as a self-directed investigation, and several load-bearing claims blur distinct formal notions.
The complete visible article was read in the browser, including every substantive heading and footnote. The canonical page identifies Evin Sellin as author, gives 2017-01-11T08:16:58Z as creation/publication time, and 2020-07-30T07:06:50Z as modification time. Medium's generic Open Graph field exposes the latter as a publication timestamp, so the structured JSON-LD and visible date are the controlling evidence for the 2017 year. The normalized visible article text had SHA-256 167a24da95df114603cffb4cab9dc18f28819cf4c7fd3ba333260afee781fd95 during ingestion.
What the article contributes #
- It asks what object receives the label: a formal model, a language specification, an implementation, or one physical machine.
- It emphasizes that program descriptions can be data for a universal interpreter.
- It notices that a finite implementation and an idealized language semantics have different resource boundaries.
- It separates solving particular termination cases from a general halting decider.
- It connects software-language claims to the older questions of computability and effective procedure.
GTK keeps those questions but answers them from primary sources and with explicit encodings, simulation invariants, and resource assumptions.
Source claims audit #
| Source claim or framing | Verdict | GTK treatment |
|---|---|---|
| Turing completeness means being as computationally powerful as a Turing machine | current but underspecified | Define equality of partial-function classes under effective input/output encodings; state the lower- and upper-bound simulations separately |
| A universal machine runs an encoded description of another machine | current | Ground in Turing's standard descriptions and universal machine, then express the modern interpreter equation explicitly |
| A fixed real computer is not literally Turing-complete | current after qualification | Prove the finite-configuration argument and distinguish a device from an idealized scalable language semantics |
| A finite tape makes the system a linear-bounded automaton | error in source | A fixed finite tape gives a finite-state system; an LBA receives a tape bound proportional to input length and remains unbounded across the input family |
| A bounded Brainfuck-style implementation is equivalent to an LBA | error in source | Classify the exact bound: a fixed global cap is finite-state; an input-linear cap is LBA-like; neither is Turing-complete |
| Loops, branches, and an unbounded-looking data structure make JavaScript almost certainly complete | useful intuition, not a proof | Require an effective compiler or interpreter, unbounded storage in the semantics, and preservation of output and divergence |
| The modern halting problem is attributed to Martin Davis, with an analogous result in Turing | historically nuanced but undersourced | Preserve the distinction: Turing's circle-free property is a different infinitary liveness question, whereas specified-symbol printing is directly interreducible with modern halting; Davis later used the explicit modern formulation |
| The Church-Turing thesis says human beings are Turing-equivalent | overbroad | State the thesis about the informal notion of effective calculability; do not turn it into a theorem about minds, brains, or every physical process |
| Formal equivalence among models proves the Church-Turing thesis | error in source | Keep formal equivalence as a theorem and the informal identification as a thesis supported by converging analyses |
| An oracle-enhanced language is “super-Turing complete” | nonstandard framing | Describe computation relative to an oracle and Turing degrees; the oracle is an added primitive, not a stronger grade of ordinary Turing completeness |
| Almost all functions are uncomputable | current only with typed domains | Use the countability argument for functions such as N -> {0,1} or sets of naturals, rather than sliding between arbitrary functions and real numbers |
| Compilers solve the halting problem in specific cases | acceptable shorthand | Say that terminating analyses decide restricted fragments or prove particular instances; they do not extend to a total general decider |
| Turing completeness is valuable mainly as an engineering warning about termination | useful but incomplete | Preserve the warning while adding proof obligations, semantic limits, and the distinction from efficiency and safety |
Visual audit #
The article contains one information-bearing figure: a 160 by 116 pixel hand-drawn two-state loop with transitions that alternately write 1 and 0 while moving right. It is correct as an informal trace of an infinite writer, but it is low-resolution, unlabeled beyond the transition marks, and redundant with a clearer independent configuration diagram. It is therefore not retained.
The GTK chapter uses original, theme-aware diagrams for a Turing configuration, a universal simulation pipeline, and the bounded-memory ladder. The author portrait and subscription graphics are decorative and excluded.
Editorial role #
This source is cited for the motivation and the software-engineering questions it surfaced, not for formal definitions or historical priority. Technical claims in the GTK chapter are grounded in Turing's 1936 and 1937 papers, Rice's theorem, and the primary linear-bounded-automata literature.