AI Prehistory | Two Legends Who Made Encoding Possible · Part I · Gödel

Preface — Programs can read programs; machines can simulate machines. Today’s AI systems likewise run as programs, while language must first become tokens and vectors before a model can process it. Beneath all of this lies an idea that once looked absurd: encoding.

Reverse the two sides and 2 < 3 becomes another statement, which the same method writes as 3,240. Neither 2,250 nor 3,240 is the result of a calculation. They are codes. Factor the two integers and the original statements—3 > 2 and 2 < 3—can be recovered.

A digital photograph is made of pixels; a sound recording is digitised through successive samples. Such conversions are now easy enough to grasp. What Gödel encoded in 1931 was more abstract: what a mathematical statement says on the page, and which rules a mathematical derivation follows. Symbols, formulae, and even entire proofs could all be encoded as integers.

The crucial move was not merely turning abstractions into numbers. Once statements and rules could be encoded as integers, mathematics could turn back and operate on them.

At twenty-five, Kurt Gödel was not devising a convenient file format. He was redrawing the boundary of what a number could represent. A number need not stand only for three apples, twenty metres, or the answer to a calculation. It could preserve the complete structure of a formula—even an entire chain of reasoning.

01How can “three is greater than two” fit inside 2,250?

Begin with a deliberately simplified example. Suppose we assign a number to each symbol:

3 → 1, > → 2, 2 → 3, < → 4, 5 → 5, + → 6, = → 7, 8 → 8

Then 3 > 2 can first be written as 1, 2, 3. But these are still three separate numbers. Gödel needed every string of symbols to correspond to one unique integer—from which the original string could be recovered in full.

Prime numbers provide exactly such a method. They preserve the order of the symbols without scrambling it during factorisation. Take 2, 3, 5, 7 … in sequence, and place each symbol code in an exponent:

2¹ × 3² × 5³ = 2,250

In this simplified example, 2,250 represents 3 > 2. Factor 2,250 into primes and the exponents return 1, 2, 3; consult the codebook and the statement reappears.

Actual Gödel numbering is far more complete. It must handle variables, brackets, symbols meaning “for all” or “there exists” (quantifiers), sequences of formulae, and entire proofs. The resulting integers also become absurdly large.

Their size does not matter. Gödel’s task was not to sit down and calculate every encoded result. What mattered was proving that the scheme could do three things.

01 · UNIQUENo collisionsDifferent symbol sequences never receive the same number. Even with the same symbols, a change of order changes the code.

02 · REVERSIBLEReversiblePrime factorisation recovers every original symbol and its position.

03 · MECHANICALMechanicalEncoding and decoding follow fixed steps. No interpretation of the sentence is required.

Why does the encoding still work with a different codebook?

A formula has no single, preordained Gödel number. You may code 3 as 1 or as 7. The integer will change, but the encoding remains valid so long as the mapping is explicit, unique, and mechanically reversible.

The interactive tool above lets you switch codebooks. 3 > 2 will no longer become 2,250, yet the new integer still decodes precisely. What matters is the structure of the encoding, not any particular number.

02When mathematical statements become mathematical objects

A formula is, at one level, simply an ordered string of symbols, and can therefore be encoded as an integer. A proof is an ordered sequence of formulae, so it can be encoded as another integer in turn.

With these successive layers of encoding, questions about mathematical formulae and proofs can be reframed as relationships among integers:

This does not mean that mathematics simply replaces language, still less that a machine suddenly understands what a sentence means. Encoding mathematical language makes a proof checker possible: a program that reads the integers representing formulae or proofs, then applies fixed rules to check their form and every step of the derivation.

Without such an encoding, one confronts line after line of symbols on paper. For a mechanical procedure to verify a proof, its formulae, inferential steps, and rules must first become input that the procedure can read and inspect one item at a time.

The checker no longer works only on marks written on paper; it operates on integers representing those long strings of symbols. Once syntax has been “arithmetised”, statements and proofs themselves become objects that mathematics can study.

Can a mathematical statement refer to itself through encoding?

Begin with a direct example:

Natural language can use “this sentence” to point directly to itself, and readers barely hesitate. Formal mathematics cannot simply write “this statement” and assume that the system knows which one is meant. The object must be specified mathematically and exactly.

Gödel numbering first assigns integers to the symbols, formulae, and mathematical statements in a formal system. One can then construct a statement about “the mathematical statement with code n”, and substitute that very statement’s own code for n. The method by which a statement ultimately points to its own encoding is called diagonalisation.

Encoding alone is not yet self-reference, but it opens the door. Before encoding, “a mathematical statement” and “an integer” belong to different levels. With encoding, a statement can point indirectly, through integers, to other statements—and even to itself. We will stop at the threshold here, and enter the magic of self-reference together in the later article on Gödel, Escher, Bach.

Gödel made it possible for mathematics to operate not only on quantities, but on descriptions of mathematics itself. The next step shifts the question from “How can a statement be encoded?” to “How can an executable procedure be described exactly?”Part II: how Turing turned machine instructions into input, opening a path towards the universal machine, programming, and AI.

Part II: Turing and the machine that could read instructions →

Sources and further reading

1. Stanford Encyclopedia of Philosophy, “Gödel Numbering”.
2. Kurt Gödel, On Undecidable Propositions of Formal Mathematical Systems, notes from the 1934 Princeton lectures.
3. Image: Young Kurt Gödel. Licensing and provenance appear on the file page.