AI Foundationspredict · compress · act
act IV

The Machines

Before neural networks, there was a question: what does it even mean for a machine to compute?

13

Can Machines Think?

before this →No Free Lunch
1936The Turing machine — Alan Turing asks what a machine can compute at all — and finds limits.
1950The imitation game — Turing proposes the test: if you cannot tell the difference, does it matter?

In 1936, Alan Turing wanted to answer a question in pure logic. He invented an imaginary machine so simple it could not be misunderstood — and accidentally defined the modern computer.

10011001headstate + symbol→ write, move, statetiny rules, huge reach
a Turing machine: a tape, a head, and a table of rules

The universal machine

A Turing machine has a tape of symbols, a head that reads and writes, and a fixed table of rules. That is all. Yet Turing proved that one machine of this kind can simulate any other: the universal machine. Feed it a description of another machine and it will run it. That is why your laptop is general-purpose.

Computability is the boundary this draws. Some well-defined problems simply cannot be solved by any machine — the most famous being the halting problem: no program can decide, for every possible program, whether that program will eventually stop. Not “we are not clever enough yet.” Proven impossible, forever.

The imitation game

Turing, 1950

Turing replaced the unanswerable question “can machines think?” with a testable one: if a machine’s conversation is indistinguishable from a person’s, on what grounds do we deny it thought? The Turing test is not a definition of intelligence. It is a deliberate move away from definitions and toward behaviour.

the deepest pointComputation is substrate-independent. If thinking is a kind of computation, then silicon and neurons are both just ways to run it. This idea is the licence under all of artificial intelligence.
SYMBOLSa tape and a rule table
UNIVERSALITYone machine runs every machine
LIMITSand some problems run on nothing
introduces →Turing machinecomputabilityTuring testhalting problem
← previousNo Free Lunchnext →The First Neuron