AI Prehistory | Two Legends Who Made Encoding Possible · Part II · Turing

The answer changed more than the mathematical understanding of computation. It laid the foundation for programming. One machine can perform countless different tasks because its instructions are not permanently fused into its mechanism: they can be represented, stored, read, and executed.

Preface — Part I began with Gödel and the conversion of mathematical statements and proofs into integers. Part II carries the question forward: can a procedure itself be described exactly, becoming input that a machine can read and execute? That step leads to the universal machine, to programming, and ultimately to AI.

03When descriptions become processable input

Gödel encoded mathematical symbols, formulae, and proofs; a program is a set of executable instructions. They are not the same thing. Yet Gödel revealed a possibility that would become immensely important: once a system of symbols and rules can be encoded precisely, another procedure can read, check, and process it.

In present-day software terms, formulae and proofs may be treated as data. The proof checker is the program; the rules of inference are the logic it follows; and its output is “valid” or “invalid”, together with the point at which an error occurs. Only when a different program actively searches for a proof does the proof found begin to resemble an output.

A proof checker, however, still follows rules written in advance. Push the idea one step further and the question becomes more interesting: which tasks can be reduced to a fixed procedure, carried out step by step by a person or a machine? During the 1930s, Herbrand, Gödel, Church, Kleene, Turing, and Post approached this question from different directions. Within a few years, their paths began to converge.

1931Gödel: arithmetising syntax

Gödel devised mechanically processable integer codes for symbols, formulae, and proofs, making mathematical language itself a mathematical object.

1934Herbrand → Gödel: from recursive equations to general recursive functions

The French logician Jacques Herbrand had proposed an unpublished idea: use a set of equations to specify relationships among the values of a function. Gödel adopted and modified the idea in his 1934 Princeton lectures; Church later credited this form of recursiveness explicitly to Herbrand and Gödel.

This line of work sought a mathematical definition of “repeated calculation according to fixed rules”. Gödel was not yet convinced, however, that the definition captured every procedure that could intuitively be carried out mechanically.

1935–36Church, Kleene, Turing, and Post: different routes to the reach of procedure

Their question was concrete: if someone claims that a task can be completed by following fixed steps, can mathematics define what “fixed steps” means and determine which problems such steps can, in principle, solve?

Church and Kleene described computation by transforming formulae on paper through symbolic substitution (the λ-calculus). Herbrand, Gödel, and Kleene used equations specifying how later values of a function follow from earlier ones (general recursive functions). Turing and Post took another route: imagine an operator who can only move, read, write, or erase symbols according to a finite set of instructions.

These apparently unrelated models were later shown to have the same computational power: any procedure expressible in one can be translated into the others. Church and Turing then used their respective definitions to prove that no fixed procedure can decide whether every mathematical statement written in a prescribed symbolism and grammar must be true.

“Computable” was no longer merely an intuition; it had acquired a precise mathematical scope. The fact that several independent models traced the same boundary became the principal support for the Church–Turing thesis: any calculation that can be completed through finite, explicit steps can be expressed by these models.

1938–39Turing: using Gödel representations to extend systems of logic

Turing’s doctoral thesis examined a new question: could a logical system be extended in stages, with new rules or axioms added at each stage so that it could prove statements about integers beyond the reach of the original system? He organised these systems with mathematical notations representing their order, calling the result ordinal logics.

For formulae at one stage to recognise and operate on formulae from an earlier stage, the formulae first had to become objects that could enter mathematical operations. Turing therefore adopted Gödel’s method explicitly: assign an integer to every symbol, then use prime powers to encode the entire string as a Gödel representation. Other formulae could then enumerate, identify, and transform the encoded formulae through those integers.

Here Gödel’s encoding was not merely a parallel idea. It was an actual tool in Turing’s construction and analysis of ordinal logics.

Before the universal machine

04To study the limits of computation, first define computation

Mathematicians were pursuing a specific problem: could a fixed procedure take any statement of formal logic as input and decide whether it must be true? Before asking whether such a procedure existed, they had to specify exactly what a “fixed procedure” was allowed to do.

What is a “statement of formal logic”?

It is not a sentence that merely sounds formal. It is a mathematical sentence written with prescribed symbols and grammar. A simple pattern of inference is: P → Q; we know P; therefore Q. What P and Q stand for may change, while the structure of the inference remains fixed.

An ordinary sentence such as “Today is good” admits many readings; formal logic deliberately excludes such ambiguity. The role of every symbol, the grammar of a well-formed sentence, and the permissible rules of inference are all specified in advance. The question was whether a general procedure could determine, for every statement written to those specifications, whether it holds in every case satisfying its premises.

Turing imagined a human calculator working strictly by prescribed rules (at the time, computer could also mean a person employed to calculate). At any moment, the calculator inspects only a small area of the paper, writes or erases a symbol, shifts attention left or right, and chooses the next action from the symbol in view and the present state of the work.

Turing abstracted these actions into a paper tape divided into cells, a head that reads or writes one cell at a time, a finite set of internal states, and a table of instructions. An “internal state” records what the machine is currently doing—for example, “move right until the next blank”, “a 1 was just read; write 0 next”, or “the task is complete; stop”.

What had been an intuitive notion of “mechanical calculation” became an exact mathematical model: the Turing machine.

Each Turing machine is defined by its symbols, internal states, and table of instructions. Turing wrote the complete table in a standard form and encoded it as a “description number”. The number does not represent the answer to a calculation; it represents how a Turing machine behaves, step by step.

Once an instruction table can be written on the tape, it ceases to be merely a document for human readers. It can become input to another Turing machine. Turing then asked whether one machine could read the description of any other Turing machine and simulate it by following that table. It could. Such a machine is the universal machine.

A universal machine reads two things: the description of the Turing machine to be simulated, and the input originally intended for that machine. It then reproduces the machine’s behaviour step by step. A different physical mechanism need not be built for every task. The same executing mechanism can do different work simply by reading a different description of instructions.

GödelEncode mathematical descriptions as integersObjects: symbols, formulae, proofs
Method: symbol codes and prime powers
Effect: syntax becomes an arithmetical object

TuringEncode machine descriptions as inputObjects: states, symbols, instruction tables
Method: encode each state, symbol, and action
Effect: one machine can simulate others

The breakthrough shared by Gödel and Turing can be stated plainly: a description need not be written only for human eyes. Once encoded, it can become an object a system can process. Gödel enabled mathematics to operate on descriptions of formulae and proofs. Turing enabled a fixed machine to read the description of another machine and simulate it.

This separates the mechanism that performs the work from the instructions specifying what work to perform. Keep the mechanism fixed, change the instruction description supplied as input, and its behaviour changes. The demonstration below isolates that single idea.

Historical note: was Turing’s universal machine directly inspired by Gödel numbering?

Whether Gödel’s work had a causal role in Turing’s 1936 research cannot now be established. The surviving evidence suggests that Turing may have read Gödel’s paper closely only after the central idea of the universal machine had taken shape. It is therefore more accurate to say that the two men began with different problems and independently made descriptions processable by mathematics or machines—not that Turing simply extended Gödel numbering into the universal machine.

By 1939 the connection is explicit. In his doctoral thesis, Turing used Gödel representations to encode formulae as integers, which other formulae could enumerate, identify, and transform. The timeline above describes this documented technical succession.

05What did these two figures change together?

Gödel encoded mathematical statements and proofs as integers, allowing mathematics to inspect mathematical language. Turing encoded machine rules as description numbers, allowing one machine to read and simulate another. Together they opened a new possibility: encode symbols, structures, and rules as processable input, so that a system can operate on descriptions themselves.

1. Content can be encoded. Formulae and proofs are no longer confined to human reading; their symbols and order can be preserved in full and handed to another formal procedure.
2. Rules can be checked. A proof checker need not understand what a sentence means in order to verify, step by step, whether its form and derivation follow prescribed rules.
3. Instructions can become input. A machine’s operating rules can be read like any other input, allowing another machine to simulate it from the description.
4. Execution can be separated from the task. A universal mechanism can perform different work by reading different programs; programs themselves can be checked, translated, and modified by other programs.

From symbols to AI

06Before AI can process language, it needs a program

Modern AI is not a free-floating “intelligence” detached from a computer. A complete AI system includes programs specifying its computations, vast arrays of numbers recording patterns learned during training (parameters), data, and hardware. Programs make these parts work together: training software repeatedly reads data, calculates results, and adjusts parameters; inference software loads those parameters, reads new input, and computes an output step by step.

Here lies Turing’s most basic contribution to the infrastructure of modern AI. Instructions can be represented, stored, loaded, and executed; the same general computing mechanism can therefore perform different work under different programs. Today, a compiler translates human-written code into executable instructions, an operating system loads and manages programs, and an AI framework directs processors through immense volumes of mathematics. Without programmable computers and these layers of software, neither AI training nor inference could occur.

Foundation A · ProgramFirst, make the machine capable of running AITraining and inference are programs. They direct processors to read data, perform extensive mathematical operations, update or load model parameters, and produce outputs.

Foundation B · EncodingThen, make language admissible to AIText must first become tokens, token IDs, and vectors before it can enter the model as input that software can receive and compute upon.

How does a piece of text actually enter a language model?

A tokenizer first divides the text into smaller units called tokens, then assigns each token an ID. The model uses each ID to retrieve a corresponding vector and passes the sequence into a Transformer—an architecture that computes relationships among tokens layer by layer—before estimating which token is most likely to come next.

The example uses OpenAI’s o200k_base tokenizer. A different tokenizer may segment the same text differently and assign different IDs. The labels v₁, v₂, and v₃ stand only for three vectors; their actual values depend on the model.

So the claim that “AI can process language” conceals two transformations. First there must be a program capable of running the AI; then language must be encoded as numerical representations that the program can process. A Gödel number is not a modern token ID, and a Turing machine is not a Transformer. Yet all three depend on the same condition: symbols and rules must take a form the system can recognise and manipulate before processing can begin.

Mathematical statements became integers; machine instructions became input; language becomes tokens and vectors. The encodings are entirely different, yet the once-absurd turn remains: a description itself can become material for computation.

Mathematical statements can be written as integers; machine instructions can become input; language can become tokens and vectors. The strange conversion that began with 2,250 leads to programs reading programs, machines simulating machines, and AI software turning text into numbers—and numbers back into text.We stop at this threshold for now. In the next article, we will step together through the door into the magic of self-reference.

Scope noteFor narrative clarity, when this article turns to modern examples under the umbrella of “AI”, it focuses mainly on large language models (LLMs). AI is not synonymous with LLMs: recommender systems, diffusion models, computer-vision systems, and other approaches are also AI. This article follows one particular historical and technical path—from descriptions becoming processable input to language models—rather than attempting a complete account of every branch of AI.

← Part I: Gödel and mathematics encoded as integers

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. Alonzo Church, “An Unsolvable Problem of Elementary Number Theory”, 1936; S. C. Kleene, “λ-Definability and Recursiveness”, 1936.
4. Emil L. Post, “Finite Combinatory Processes—Formulation 1”, 1936.
5. Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”, 1936–37.
6. Alan M. Turing, “Systems of Logic Based on Ordinals”, 1939.
7. Rico Sennrich, Barry Haddow & Alexandra Birch, “Neural Machine Translation of Rare Words with Subword Units”, 2016; Ashish Vaswani et al., “Attention Is All You Need”, 2017.
8. OpenAI, “Counting tokens”; tiktoken. The o200k_base tokens and IDs in this article were calculated with that encoding.
9. Stanford Encyclopedia of Philosophy, “The Church–Turing Thesis”.
10. B. Jack Copeland & Zhao Fan, “Did Turing Stand on Gödel’s Shoulders?”, 2022.
11. Thomas Haigh, “Actually, Turing Didn’t Invent the Computer”, 2014; Jürgen Schmidhuber, “Turing Oversold”, included as further reading from a contrasting position.
12. Images: Young Kurt Gödel; Alan Turing, 1951. Licensing and provenance appear on the respective file pages.