Discovery Engine — Deep Dive · Turing Series, Part 1

Hiroaki Kitano

Turing built the substrate of discovery fourteen years before he asked his famous question.

Discovery Engine — Deep Dive · Turing Series, Part 1

Turing built the substrate of discovery fourteen years before he asked his famous question.

Before the question, the machine

In the opening post of this blog I argued that Alan Turing gave artificial intelligence its founding question — Can machines think? — and that I wished to pose a successor to it: Can machines discover? That essay treated Turing as the author of a question. This series treats him as something that is less often said aloud: the author of the machines.

The order matters. We tend to remember Turing for 1950 — for Computing Machinery and Intelligence (Turing, 1950), the paper that gave us the imitation game, the prediction, and the question that organized a field. But the conceptual apparatus that made that 1950 paper possible was already complete fourteen years earlier, in a paper with a far more forbidding title: On Computable Numbers, with an Application to the Entscheidungsproblem (Turing, 1936). Turing was twenty-three, and had not yet seen a computer, because no computer yet existed. The 1950 question is downstream of that 1936 invention. You cannot meaningfully ask whether a machine can think until you have first said, with precision, what a machine is — and what, in principle, any machine can and cannot do. That is what the 1936 paper did. It is, I will argue across this series, the true beginning of everything this blog is about.

So we begin where Turing began: not with thought, and not yet with discovery, but with a problem about problems.

1936: a problem about problems

Return to that forbidding title — On Computable Numbers, with an Application to the Entscheidungsproblem. The second half of it is the key. The Entscheidungsproblem — the "decision problem" — had been posed by David Hilbert as part of his program to put mathematics on fully mechanical foundations (Hilbert & Ackermann, 1928). The question was simple to state and enormous in consequence: is there a definite, general procedure that, given any mathematical statement, will decide whether it is provable?

Hilbert hoped the answer was yes. A "yes" would have meant that mathematics, at least in principle, could be done by turning a crank — that truth was, at bottom, a matter of mechanical procedure. Kurt Gödel had already unsettled this dream in 1931 by showing that any sufficiently rich formal system contains true statements it cannot prove (Gödel, 1931). The Entscheidungsproblem was the last load-bearing pillar of the program still standing. Turing — and, independently and almost simultaneously, Alonzo Church in Princeton (Church, 1936) — knocked it down.

To answer a question about every possible procedure, Turing needed something nobody had: a precise, general definition of what a "procedure" is. Logicians had always relied on an intuitive notion of an "effective method" — a recipe a clerk could follow with no insight, only obedience. Intuition is not enough to prove a theorem about all such methods. Turing's move — and this is the act of genius in the paper — was to replace the intuition with a machine.

The machine that was really a definition

The Turing machine is familiar now, which makes it easy to miss how strange it is. The strangeness is the point.

He asked what the most stripped-down imaginable agent of a mechanical procedure would look like. Not a calculating engine of brass and gears, but the logical skeleton of any such engine. He arrived at almost nothing: an endless tape divided into squares, a head that can read and write one symbol at a time, a finite list of internal states, and a table of rules of the form if you are in this state reading this symbol, write that symbol, move one square left or right, and switch to that state. That is the whole machine. There is nothing else in it.

The claim Turing then made is audacious. He proposed that anything a human computer can do by following a fixed procedure, one of these machines can also do. In 1936 a "computer" was still a person — a clerk employed to carry out calculations by hand, one rule at a time. Turing's machine is, quite literally, the logical skeleton of that clerk. Not approximately — exactly. The tape and the rule table are not a model of some computations; they are a model of computation as such. This is now called the Church–Turing thesis, and in ninety years no one has found a counterexample: no effective procedure has ever been described that a Turing machine cannot, given enough tape and time, carry out.

The Turing machine looks like an engineering proposal. It is not — it is a definition wearing the costume of a machine. With it, "computable" stopped being a matter of taste and became a mathematical object you could prove theorems about. And the first theorem Turing proved with it was that the Entscheidungsproblem has no solution: there is no machine, and therefore no effective procedure of any kind, that decides provability in general. Hilbert's crank does not exist.

The universal machine

If Turing had stopped there, he would have a place in the history of logic. What he did next earned him a place in the history of everything else.

Each Turing machine, as described so far, does one job. One machine adds; another sorts; another checks whether a string is a palindrome. The rule table is the machine; change the table and you have a different machine. So far, so unremarkable — this is how all machinery before Turing worked. A loom weaves; a mill grinds; a bombsight computes a release point. Each device has its function built into its body.

Turing then asked a question that, once asked, cannot be unasked. The description of any particular machine — its rule table — is just a finite string of symbols. And a Turing machine can read symbols on a tape. So: could there be a single machine that takes, as input on its tape, the description of any other machine, and then proceeds to behave exactly as that machine would?

There could. He built it — on paper — and called it the universal machine.

A universal machine is one machine that can become any machine, given only a description of the one it should become.

It is easy to glide past this as a technicality; it is one of the deepest ideas anyone has had. Every machine before 1936 had its purpose welded into its physical form. The universal machine dissolves that weld. It separates, for the first time, the machine from the function it performs — turning the function into data, into something you write on a tape and feed in, swap out, edit, share. The hardware becomes general; the behavior becomes soft. We have a word for the function-written-as-data now. We call it software. Turing invented it as a side effect of answering a question in mathematical logic.

The machine and the description it reads live on the same tape, in the same alphabet, indistinguishable in kind. A decade later this idea — program and data sharing one memory — would be written into the architecture of every electronic computer ever built (von Neumann, 1945). Every laptop, phone, and datacenter is a physical approximation of Turing's universal machine. When you install an app, you are doing exactly what the universal machine does: handing a general device the description of a specific one, and watching it become that thing.

You can feel this with your own hands in the simulator below. It is a single Turing machine. Leave the device untouched and swap only the rule table, and it becomes an adder, then a palindrome-checker, then a busy beaver — one machine wearing four behaviours, changed by nothing but its description. Run it, step through it, and you are operating the exact principle this essay turns on.

Why universality is the substrate of discovery

Here is where the 1936 machine reaches forward into the project of this blog.

In the first post I made my largest claim:

A discovering machine is bounded only by the structure of reality itself.

That sentence is easy to mistake for rhetoric. The universal machine is what makes it a literal, technical proposition rather than a poetic one.

A machine with its function welded into its body is bounded by that body. A loom can only weave. If discovery required a different physical contrivance for every kind of question — one engine for chemistry, another for genomics, a third incapable of being repurposed for either — then the reach of machine discovery would be bounded by our ingenuity in building engines, one domain at a time. That is roughly the pre-industrial situation Turing's universal machine ended for computation, and it is roughly the situation that the Discovery Engine proposes to end for science.

Because computation is universal, the ceiling on what a computational system can do is not set by the particular machine in front of you. It is set by computability itself — by what is effectively calculable at all. The same general-purpose hardware can, with nothing changed but the program it is handed, predict how a protein folds, search a space of chemical reactions, model a developing embryo, or play a game of Go.

Set that against the loom and the mill, each with its one function welded into its body. Universal computation is the exact opposite: there is no machine physically specialised to its task, because there does not need to be. AlphaFold runs on the same ordinary, general-purpose computers as everything else — there is no "protein computer," and Turing's result tells us there could not need to be one (Jumper et al., 2021). The robot scientists that run experiments from hypothesis to result need no purpose-built "biology machine" either (King et al., 2009). A single general substrate carries them all, because in 1936 Turing proved there is only one substrate, and it is general.

This is the quiet foundation under the whole argument of this blog. When I say a discovering machine is bounded only by reality, the first half of what makes that true is that the machine is universal — that there is no domain of effective procedure it is constitutionally shut out of. The discovery engine is not a new kind of machine. It is the universal machine, finally pointed at the right problem.

From computation to search

There is a gap in the argument I have just made, and a careful reader will already feel it. Universality guarantees that one machine can carry out any effective procedure. It does not, by itself, guarantee discovery. Those are not the same thing, and the distance between them is where this whole series actually lives.

Computation is following a known procedure to its answer. Discovery is something else entirely: arriving at an object — a fact, a mechanism, a representation — that was not given to you in advance, somewhere in a space of possibilities far too large to enumerate by hand. A universal machine that is merely told what to compute discovers nothing. What turns universal computation into a candidate for discovery is the move from executing a known procedure to searching a space of unknown ones.

This is the missing middle rung, and the whole six-part arc hangs from it:

Computation gives us a universal substrate. Search is what makes that substrate productive. Discovery is what search produces when the space it traverses is the space of the real — and the deepest discoveries may demand not merely traversing a space, but generating a new one.

Look again at the examples. AlphaFold does not merely compute a structure from a formula we already hold; it searches an astronomically large space of conformations for the one reality settles into (Jumper et al., 2021). A robot scientist does not run a fixed experiment; it searches a space of hypotheses, designing the next test from the last result (King et al., 2009). Theorem provers search proof spaces; drug-discovery systems search chemical spaces. Strip the domains away and the same verb is left standing beneath all of them: search. Universality says the substrate can host any of these. Search is what any of them are actually doing on it.

But notice what all of these examples quietly share: in every one, the space to be searched has already been drawn for the machine. The conformations, the hypotheses, the proofs, the molecules — we lay them out in advance, and the system traverses what we have laid out. It searches a space; it does not draw one. That is no small feat, and most of machine discovery to date lives exactly there. But it also marks the harder question this series is really chasing — not how to compute within a known space, but how a machine might discover where the space itself has not yet been drawn.

The word needs two guardrails, because it invites two wrong pictures; a later essay gives the careful version. First: this is not retrieval. The dividing line is not whether the data being searched already exists, but whether the thing found already existed as a record. Looking up a known fact in a library is retrieval; mining the same library for a correlation no one had written down is discovery. What a discovering machine is after is recorded nowhere — it has to be constructed and then judged against the world, not matched against a corpus.

Second, and more subtly: generating states is not the same as generating spaces. A tree search builds its states as it goes rather than listing them in advance — but every state it can reach is already implied by a fixed set of rules (the legal moves, the grammar, the primitives). The space is settled; the search only unfolds it. True novelty has two depths, then. There is search within a fixed space of hypotheses — vast, perhaps, but bounded by a fixed vocabulary — which covers most of what we called Class I and Class II discovery. And there is the rarer act of remaking the vocabulary itself: introducing new primitives, new axes, a new way of carving the world — which is Class III, the generation of new semantic dimensions. I will call the first intraspatial search (logically, explicative: it unfolds what a fixed vocabulary already contains) and the second transspatial search (logically, ampliative: it adds content the old vocabulary could not express). The names, and the question of whether the second ever truly differs from the first, get their own companion essay; here it is enough to feel the difference.

Here the 1936 result returns, with a twist. At the universal limit — the space of all programs — even remaking the vocabulary is just moving to a different program inside the one universal space. Inventing a new representation is, from that vantage, exactly what the universal machine does when you change its description rather than rebuild its body. So transspatial search may be real only relative to a working vocabulary, and dissolve back into ordinary intraspatial search when seen from the universal substrate. Whether that is a genuine reduction or a sleight of hand is one of the deepest open questions this blog has — and it gets its own post.

Universality, then, is necessary but not sufficient. It opens the door to every effective procedure; search is what walks through. Hold that word. The next post in this series is about the first machine Turing ever built whose entire reason for existing was to search — and the rest of the series climbs the same ladder from there: machine, then search, then learning, then discovery.

The edge of the map

The same paper that hands us the universal substrate also draws its boundary, and we should look at the boundary as squarely as the gift.

The Entscheidungsproblem result was a negative one. Turing proved that some questions have no mechanical answer at all. The cleanest example is the one we now call the halting problem: there is no general procedure that can take an arbitrary machine and its input and decide, in finite time, whether that machine will eventually stop or run forever. You can run it and wait — but if it has not stopped yet, you can never be sure whether it is about to, or never will. No cleverer method removes the uncertainty. It is not a gap in our knowledge; it is a theorem about the limits of procedure.

So universality and undecidability arrive together, twins born in the same 1936 pages. The universal machine says: one device can perform any effective procedure. The halting result says: but not every well-posed question corresponds to an effective procedure. The map is universal in extent and yet has an edge, and the edge is provable.

What does this mean for a machine that discovers? It is a useful corrective to a certain triumphalism — including my own. There are truths no engine will grind out, not because the engine is weak but because no procedure for them exists. A discovering machine, however vast, inherits Turing's edge. It will not be omniscient; it will be unboundedly resourceful within a space that is itself bounded. I find this clarifying rather than deflating. The interesting frontier of machine discovery was never the handful of formally undecidable questions at the edge of the map. It is the enormous, decidable, reachable interior that human science has simply never had the bandwidth to explore — the long tail of Class I facts (individual discoveries that fit inside existing frameworks), the unbuilt Class II frameworks (the new organising principles that make scattered facts cohere). The edge is real. We are nowhere near it.

A deeper symmetry may hide here — I plant it as speculation, not argument. Universality arrived bound to undecidability: reach and limit in one breath. The discovery engine may arrive bound to its own version — unbounded search over a space that still holds questions no search resolves. As a speculative analogy: universality is to undecidability what discovery may be to incompleteness. A promissory note, to be discharged later in the series.

Imitation, and what lies beyond it

One more thread from 1936 runs the length of Turing's life, and into this series.

Look again at what the universal machine does. It reads the description of another machine and imitates it — behaves indistinguishably from it. Imitation is not a metaphor I am importing; it is the literal mechanism of universality. The universal machine is an imitation engine.

Fourteen years later, in 1950, Turing took the same verb and moved it from machines to minds. The imitation game asks whether a machine can imitate a human well enough that we cannot tell the difference. Offer this as a reading, not something Turing announced: the imitation that defines universal computation in 1936 reappears, transposed, as the imitation that defines machine intelligence in 1950 — imitation as a kind of deep grammar running through his work. Can a machine become indistinguishable from the thing it models? — first of any machine, then of us.

And this is precisely the hinge on which the Discovery Engine turns away from him. As I argued in the first post:

Turing asked whether machines could simulate humans. I am asking whether machines can transcend them.

A discovering machine, at its most interesting, is not an imitation engine. It is not trying to become indistinguishable from a human scientist. It is trying to reach what human scientists, bounded by human cognition, cannot reach — to arrive at adjacent territories, by adjacent routes, in semantic dimensions that are not yet ours. Universality is the inheritance Turing left us. Going beyond imitation is what the inheritance is for.

That is the arc of this series in a sentence. Turing spent his life building, theorizing, and deploying imitation machines of astonishing depth. The question this blog asks is what happens when their descendants stop imitating and start discovering.

In 1936 the machine was on paper. By 1939 Turing was building a real one, of relays and rotating drums.

The universal machine established that one machine could perform any effective procedure. The Bombe would ask a different question: can one machine traverse a space too large for any human to cross? Discovery begins at exactly that hinge — when universality becomes search.

That machine is the subject of Part 2 — and, as it happens, I will be writing it from Bletchley Park.

What comes next in this series

This is Part 1 of a six-part Deep Dive that reads Turing as the first architect of a discovery engine. The series climbs a single ladder — machine → search → learning → imitation → discovery → engine — one rung per post:

• Part 1 — The Universal Machine (1936) · machine. Computation defined; universality as the substrate of discovery; the provable edge of the map. (This post.)
• Part 2 — The Bombe (1939–45) · search. Turing as a builder of search engines. The Bombe as machine-scale traversal of a combinatorial space no human could cross — the literal ancestor of the engine metaphor. Reported from Bletchley Park.
• Part 3 — Intelligent Machinery (1948) · learning. The unpublished blueprint: unorganised machines, learning, the "child machine," evolutionary search. Turing anticipating the learning core a discovery engine needs.
• Part 4 — The Question (1950) · imitation. A close reading of Computing Machinery and Intelligence, the imitation game, and exactly where Can Machines Discover? departs from it.
• Part 5 — Turing Patterns (1952) · discovery. The series turns here: from machines that might discover to Turing himself discovering — by computation. Computing life forms — his attempt to uncover a principle of biological systems from simple chemistry (reaction–diffusion, the patterns that bear his name), the first great act of computational biology, and the strongest precedent the engine has.
• Coda — The Unfinished Engine · engine. Gathering the six threads into the engine Turing prefigured but never named — and the line that runs from it to the Nobel Turing Challenge.

A note on how this was written

As with everything on Discovery Engine, this post was written by a human author (Hiroaki Kitano) in deep collaboration with AI systems — Claude (Anthropic) as primary collaborator, with Gemini (Google) and ChatGPT (OpenAI) in the loop for cross-checking, alternative framing, and reference work. The historical and mathematical claims have been checked against primary and standard secondary sources; the final editorial judgment is mine. The embedded simulator was built in the same collaboration.

A blog that argues machines will one day discover would be evasive if it hid how much of its own writing is already a human–machine act. This is what the writing layer looks like in 2026. The discovery layer is harder, and is where this series is going.

See the Lab Notebook for this post for source materials, iteration history, and AI inputs.

References

Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2), 345–363.

Copeland, B. J. (Ed.). (2004). The Essential Turing. Oxford University Press.

Davis, M. (2000). The Universal Computer: The Road from Leibniz to Turing. W. W. Norton.

Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38, 173–198.

Hilbert, D., & Ackermann, W. (1928). Grundzüge der theoretischen Logik. Springer.

Jumper, J., et al. (2021). Highly accurate protein structure prediction with AlphaFold. Nature, 596, 583–589.

King, R. D., et al. (2009). The automation of science. Science, 324(5923), 85–89.

Kitano, H. (2021). Nobel Turing Challenge: Creating the engine for scientific discovery. npj Systems Biology and Applications, 7, 29.

Petzold, C. (2008). The Annotated Turing. Wiley.

Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42, 230–265.

von Neumann, J. (1945). First Draft of a Report on the EDVAC. Moore School of Electrical Engineering, University of Pennsylvania.

How to cite this article

Kitano, H. (2026). The Universal Machine. Discovery Engine — Deep Dive, Turing Series, Part 1. https://thediscoveryengine.ai/

@misc{kitano2026universalmachine,
  title  = {The Universal Machine},
  author = {Kitano, Hiroaki},
  year   = {2026},
  howpublished = {\url{https://thediscoveryengine.ai/}},
  note   = {Discovery Engine, Deep Dive, Turing Series, Part 1}
}