<!-- Generated from https://www.teclamairme.com/#ch-T9 by readviews.py; never edited by hand. -->

# Chapter ᚇ(D): The locomotive

*Teclam Áirme, the Mathematical Compendium — a copy for AI readers of https://www.teclamairme.com/#ch-T9, as of 2026-09-30. Links are relative to https://www.teclamairme.com/fortheaireaders/.*

[Guide for AI readers](index.md) · [Its glossary cards](ch09-cards.md) · [Its references](ch09-refs.md) · [Previous chapter](ch08.md) · [Next chapter](ch10.md)

*A footnote such as [r-9.3] is reference entry 9.3 and links to it. Section 9 of 28; chapters are named by their Ogham letter, never by number.*

ᚇ – [Dair](ch09-cards.md#g-og-dair): associated with the oak tree, Section 9

## Chapter ᚇ(D): The locomotive

> “The ‘computable’ numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.”

> — Alan Turing · opening sentence of On Computable Numbers, with an Application to the Entscheidungsproblem, 1936 [r-9.23](ch09-refs.md#r-9.23)

Formula: (([(λf.λx.x) S 0](ch09-cards.md#g-church)) + [[∃ a halting decider]](ch09-cards.md#g-halting))/([BB(5)](ch09-cards.md#g-bb5) + [A(3, 3)](ch09-cards.md#g-ack) + [BB(1) + BB(2) + BB(3) + BB(4)](ch09-cards.md#g-bbsmall)) {brace: [computability](ch09.md#ch-T9-computability)} · [[P ⊆ NP]](ch09-cards.md#g-pnpsub) {brace: [complexity](ch09.md#ch-T9-complexity)} · ([fl<sub>64</sub>(1+2<sup>−53</sup>)−1](ch09-cards.md#g-float64zero))/([2<sup>−52</sup>](ch09-cards.md#g-eps64)) {brace: [numerical analysis](ch09.md#ch-T9-numerical-analysis)}

Key concepts: Computability, complexity, and numerical analysis. It includes symbols you may not have seen before, such as: [λ](ch09-cards.md#g-lambdacalc), [fl<sub>64</sub>](ch09-cards.md#g-float64zero), and [P ⊆ NP](ch09-cards.md#g-pnpsub). Zero here is a limit on machines: no program can decide halting, and a computer rounding 1 + 2<sup>−53</sup> lands back on exactly 1.

You can hear the machinery before we reach it. Here in the locomotive, we can let it handle the traveling while we ask three questions about instructions: what can they accomplish in principle, how much work will they take, and what happens when their numbers have to fit inside a finite machine? Computability, complexity, and numerical analysis each examine a different limit. A machine can encounter one without encountering the others.

Church, Turing, and others made the first question precise in the 1930s. [Church’s lambda calculus](ch09-cards.md#g-lambdacalc) describes computation through functions and their application. Turing imagined [a machine reading and writing symbols on a tape according to fixed rules](ch09-cards.md#g-turingm). Along with [general recursive functions](ch09-cards.md#g-genrec), these apparently different constructions describe the same computable functions. [The Church–Turing thesis](ch09-cards.md#g-churchturing) identifies this mathematical class with what an effective mechanical procedure can calculate; it is not a promise that every physical computer has unlimited tape or time. [r-9.1](ch09-refs.md#r-9.1) [r-9.3](ch09-refs.md#r-9.3) [r-9.4](ch09-refs.md#r-9.4)

Field notes

### [computability](ch09.md#ch-T9-computability) {#ch-T9-computability}

What instructions can accomplish in principle: one instruction that returns zero, and one universal instruction that cannot exist.

#### Numerator

[(λf.λx.x) S 0](ch09-cards.md#g-church) = 0; Church’s zero, the simplest instruction there is, carried out on an ordinary number.

A Church numeral says how many times to apply a function. Its zero, λf.λx.x, accepts a function f and a starting value x and returns x untouched. Given the successor S (“add one”) and the start 0, applying add-one zero times leaves 0: [(λf.λx.x) S 0](ch09-cards.md#g-church) → (λx.x) 0 → 0. An instruction can leave its starting value alone and still have been carried out perfectly. [r-9.1](ch09-refs.md#r-9.1) [r-9.19](ch09-refs.md#r-9.19)

[[∃ a halting decider]](ch09-cards.md#g-halting) = 0; Turing’s halting problem, the founding impossibility of computer science.

A halting decider would be one algorithm that correctly answers, for every program and input, whether the program eventually stops. Turing proved none exists. Suppose we had one. Build a contrary program that asks the decider about itself and then does the opposite: if the decider predicts it will halt, it runs forever; if the decider predicts an endless run, it halts. Either prediction fails, so no decider exists and the bracket is 0. Many individual programs are easy to analyze; it is the universal method that is impossible. [r-9.2](ch09-refs.md#r-9.2)

The verdict spreads. [Rice’s theorem](ch09-cards.md#g-rice) widens it to every nontrivial question about what a program computes, such as whether it ever prints 0. [r-9.16](ch09-refs.md#r-9.16) Turing used the halting result to answer Hilbert’s [Entscheidungsproblem](ch09-cards.md#g-entscheidung): no algorithm decides which statements of logic are valid. [r-9.21](ch09-refs.md#r-9.21) And it is the boundary behind [Chaitin’s Ω](ch05-cards.md#g-omega) and [the Busy Beaver function](ch09-cards.md#g-busybeaver) in Chapter ᚃ(F). [r-9.8](ch09-refs.md#r-9.8)

#### Denominator

[Busy Beaver](ch09-cards.md#g-busybeaver) asks how long a halting machine can run; [Ackermann](ch09-cards.md#g-ackfn) shows how fast a function can grow while still having an algorithm.

[BB(5)](ch09-cards.md#g-bb5) = 47,176,870; the largest Busy Beaver value anyone has proved, settled in 2024.

[BB(n)](ch09-cards.md#g-busybeaver) asks a simple question. Take every [Turing machine](ch09-cards.md#g-turingm) with n states (n sets of instructions it switches between) that writes only two symbols and starts on a blank tape, and set aside the ones that never halt: how many steps does the longest-running of the rest take? For five states the answer is 47,176,870, and it took the Busy Beaver Challenge to prove it. No algorithm can produce BB(n) for every n, but a single value can still be pinned down, one hard proof at a time. [r-9.5](ch09-refs.md#r-9.5) [r-9.6](ch09-refs.md#r-9.6) [r-9.7](ch09-refs.md#r-9.7) [r-9.8](ch09-refs.md#r-9.8)

[BB(1) + BB(2) + BB(3) + BB(4)](ch09-cards.md#g-bbsmall) = 1 + 6 + 21 + 107; every Busy Beaver value below [BB(5)](ch09-cards.md#g-bb5), for completeness.

Each is a plain count of steps, known exactly: 135 in all.

[A(3, 3)](ch09-cards.md#g-ack) = 61; [Ackermann’s function](ch09-cards.md#g-ackfn), a reminder of how much happens on the computable side of the line.

Ackermann’s function is defined by a short rule that calls on itself (this book uses the two-argument [Ackermann–Péter form](ch09-cards.md#g-ackfn)), and a computer can in principle work out any of its values. Yet it grows faster than every primitive recursive function, the kind built only from loops whose number of repetitions is fixed before they start, so no program of that simpler kind can compute it. [A(3, 3)](ch09-cards.md#g-ack) is a modest 61; A(4, 2) already runs to 19,729 digits. A function can grow extraordinarily quickly and still have an algorithm. [r-9.9](ch09-refs.md#r-9.9) [r-9.10](ch09-refs.md#r-9.10)

The first fraction is 0/47,177,066: 47,176,870 + 61 + 1 + 6 + 21 + 107 = 47,177,066, positive, and built only from values known exactly. [r-9.19](ch09-refs.md#r-9.19)

**Fine print.** The train’s onboard computer has only so much memory, so it can be in only finitely many complete configurations (everything in its memory, taken together). Following fixed rules with nothing new coming in, it must eventually either stop or return to a configuration it has been in before, and from then on it repeats forever; in principle, we could simply watch and find out. The wait could be hopelessly long, but it is not what Turing’s theorem forbids: the impossibility concerns programs with potentially unbounded storage.

### [complexity](ch09.md#ch-T9-complexity) {#ch-T9-complexity}

How much work instructions take. This brace is a single factor, not a fraction: it holds the half of this field’s most famous question that is already settled.

#### The displayed factor

[[P ⊆ NP]](ch09-cards.md#g-pnpsub) = 1; the known half of the most famous open question in computer science.

P contains the yes-or-no problems a computer can solve in polynomial time: as the input grows, the work grows no faster than some fixed power of its size. NP contains the yes-or-no problems where every yes answer comes with evidence, a certificate, that can be checked in polynomial time. For “can the variables of this Boolean formula be set so that it comes out true?”, the certificate is one such setting: plug it in and look. If we can solve a problem within the bound, we can check a yes answer by simply solving it and ignoring the evidence. Hence [P ⊆ NP](ch09-cards.md#g-pnpsub), and the bracket is 1. Whether every efficiently checkable problem is also efficiently solvable is the [P versus NP](ch28-cards.md#g-pnp) question of the epilogue. [r-9.11](ch09-refs.md#r-9.11) [r-9.12](ch09-refs.md#r-9.12)

The second factor is 1: there is no denominator, and a bracket around a true statement is the ordinary integer 1.

**Fine print.** Polynomial time concerns growth, which is what [big-O notation](ch09-cards.md#g-bigO) records: doubling the input might multiply an n² bound by four. It does not guarantee that every polynomial algorithm is useful at practical sizes. Checking a proposed round trip that visits every stop exactly once takes a single pass along it; finding one in a large network is one of the twenty-one hard problems Richard Karp listed in 1972, and nobody knows a quick way to do it, exactly the gap P versus NP asks about. [r-9.12](ch09-refs.md#r-9.12) Computability asks whether a method exists at all; complexity studies the resources of methods that do.

### [numerical analysis](ch09.md#ch-T9-numerical-analysis) {#ch-T9-numerical-analysis}

What happens when numbers must fit inside a finite machine. A display has limited room for digits, and the calculation behind it can have a limit of its own.

#### Numerator

[fl<sub>64</sub>(1+2<sup>−53</sup>)−1](ch09-cards.md#g-float64zero) = 0; a zero the machine itself produces, built from a tie that rounds away.

fl₆₄ means: work out the exact answer, then round it to the nearest number that [binary64](ch09-cards.md#g-ieee754) can store. Binary64 is the double-precision format of the standard almost every modern computer follows, and when an answer falls exactly halfway between two storable numbers, the standard’s default is to pick the one whose last binary digit is 0 (“ties to even”). The format keeps 53 binary digits of precision, so just above 1 the storable numbers are [2⁻⁵²](ch09-cards.md#g-eps64) apart. Our increment, 2⁻⁵³, is half that gap, which leaves the exact value halfway between 1 and its next neighbor; the tie rule picks 1, whose last binary digit is 0. Subtracting 1 then gives exactly 0, where ordinary real arithmetic would give 2⁻⁵³. [r-9.13](ch09-refs.md#r-9.13) [r-9.14](ch09-refs.md#r-9.14) [r-9.22](ch09-refs.md#r-9.22)

#### Denominator

[2<sup>−52</sup>](ch09-cards.md#g-eps64) ≈ 2.22 × 10⁻¹⁶; the full gap our increment was half of, known in the mainstream definition as [machine epsilon for binary64](ch09-cards.md#g-eps64).

It is the distance from 1 to the next double-precision number, positive and exactly representable. The rounded numerator divided by it remains zero.

The third and final fraction is 0/[2⁻⁵²](ch09-cards.md#g-eps64).

**Fine print.** The format and operation order are part of the example; other precisions or rounding modes can behave differently. Limited precision is a separate issue from uncomputability: many numbers can be approximated as accurately as we like with more storage and a suitable algorithm. Ω lacks such an algorithm; this increment merely met a format that could not retain it.

What this chapter adds to the formula: 0/47,177,066 · 1 · 0/[2⁻⁵²](ch09-cards.md#g-eps64) = 0 × 1 × 0 = 0

An instruction returned zero, a universal prediction proved impossible, and a specified rounding rule lost a small increment: a zero the machine made by discarding a distinction that exact arithmetic keeps.

The instructions are running; now we need the map they run over. Let’s visit the caboose, the conductor’s office at the back, where the maps live. Besides, it is quieter in there so we can talk.

Watch and read

- [Lambda Calculus - Computerphile](https://www.youtube.com/watch?v=eis11j_iGMs) Computerphile, Graham Hutton: Church’s calculus and the numerals, with the encoding of zero on paper

- [Turing & The Halting Problem - Computerphile](https://www.youtube.com/watch?v=macM_MtS_w4) Computerphile, Mark Jago: the proof that no program can decide halting, in eight minutes

- [Halting problem](https://en.wikipedia.org/wiki/Halting_problem) Wikipedia