Automata
What is an automaton?
When we speak of automata in everyday life, we think of coffee machines or ticket dispensers. In computer science the word means something more abstract: an automaton is a machine that doggedly follows a rule. It reads a symbol, looks it up in its table of rules, changes its internal state and carries on. No understanding, no reflection, no intuition. Only rules.
That is precisely where the power of this concept lies. Anyone who wants to understand what computers, and later artificial intelligence, can do in principle must first know what a rule-following machine actually is and where its limits lie.
Turing's idea
In 1936 the British mathematician Alan Turing imagined the simplest machine conceivable: an infinitely long paper tape divided into cells, and a read-write head positioned over the tape.1 The machine can do only four things:
- read the symbol in the current cell,
- write a symbol into it,
- move one cell to the left or to the right,
- switch to a different state.
Nothing more. What it does at each step is laid down in a finite table: "If you are in state 3 and read a 1, then write 0, move right and switch to state 5."
The astonishing part: this machine can compute everything a modern computer can compute. Your laptop is faster and more convenient, but not more powerful.
A Turing machine made of toilet paper and pebbles
You really can build a Turing machine without any electronics at all. A roll of toilet paper supplies the tape, each sheet is a cell. Pebbles or coins are the symbols: a pebble means 1, an empty sheet means 0. You write your state table on a piece of paper, and your state is a matchstick you place on the current row. You yourself are the read-write head.
This is not a gimmick but a serious point: computing needs no chip. It needs a medium, rules, and someone or something that carries out the rules mindlessly. What your computer does, you can do with toilet paper too. Just very much more slowly.
Can automata answer every clearly posed question?
It is tempting to hope that a machine must be able to answer any question, as long as it is posed precisely enough. Turing showed that this hope is mistaken.
His most famous result is the halting problem. The question is this: is there a program that reliably predicts, for any other program whatsoever, whether it will eventually stop or run forever? The question is perfectly clearly posed. And the answer is: no, such a program cannot exist.
The proof works by contradiction. Suppose there were a perfect halting checker. Then one could build a malicious machine that applies this checker to itself and then does exactly the opposite: if the checker says "it halts", it runs forever; if the checker says "it runs forever", it stops at once. So the checker is wrong in either case. Hence it cannot exist.
This is a limit of principle, not a technical one. No faster computer, no larger language model and no quantum computer will ever cross it. There are clearly formulated questions that are undecidable in principle.
Finite, infinite, complicated
Automata come in different strengths, and the differences have to do with memory.
A finite automaton has only finitely many states and no tape. It can control a set of traffic lights or check whether an email address contains an @. But it cannot count how many brackets are still open, because that would require unlimited memory.
The Turing machine with its infinite tape sits at the top of this hierarchy. Between the two lie further models, for instance automata with a stack, which can count brackets but not much else.
Even where a task is solvable in principle, the question of cost remains. Some problems can be solved in a reasonable time, others only after millions of years of computation. This distinction between "computable" and "computable in practice" is the subject of complexity theory and the reason encryption works at all.
Why this page is here
This chapter is about artificial worlds and artificial intelligence. Everything on the following pages, from probabilities through neural networks to large language models, comes down to automata in the end. They are very large, very fast, very impressive automata. But the limits Turing found in 1936 with paper and pencil apply to all of them.