Alan and his Enigma
Licensed under ::
by ()
@


Alan and his Enigma

The story of Alan Matthison Turing, his machine(s) and his test(s)

Watch: Alan Turing's Machines

We start with a 1966 BBC programme, made twelve years after his death.

While you watch, keep one question in mind: what is this “machine” made of?

Alan Matthison Turing (1912–1954)

Born in London, 23 June 1912. Mathematician: Cambridge, then Princeton.

1936, aged 23: On Computable Numbers — the paper that defines the computer before any computer exists.

1939–45: Bletchley Park, breaking German naval Enigma.

1945–50: designs an electronic computer; 1950: Computing Machinery and Intelligence.

1952: convicted for homosexual acts, chemically castrated. 7 June 1954: dead of cyanide poisoning, aged 41. Royal pardon: 2013.

The man who asked whether machines can think was not allowed to be what he was.

The imitation game

The game as Turing wrote it

Turing refuses to define “think”. He calls the question “too meaningless to deserve discussion” and replaces it with a game.

Three players: A (a man), B (a woman), C (the interrogator, in another room). C types questions and must tell who is the woman. A tries to deceive. B tries to help.

Now let a machine play A. Does C get it wrong as often as before?

His prediction: around the year 2000, an average interrogator would have no more than a 70% chance of a right identification after five minutes.

The game is called imitation — and it is about gender, deception and performance.

Turing test

"A TT is a way how to address the question "Can machines think?" in a scientifically plausible ye deeply empathic way. More concretely, Turing (1950) proposes that the performance of an AA under question shall be evaluated by a human judge J whose objective is to determine which among two entities - with whom J is in real-time interaction - is of human and which is of artificial nature." (Hromada, 2012)

Watch: Can machines think?

The famous question, in video form.

While watching, note the one objection you would raise.

Turing answers his critics

Section 6 of the paper lists nine objections, among them theological, mathematical, from consciousness — and Lady Lovelace's.

Lovelace (1843): the Analytical Engine “has no pretensions to originate anything. It can do whatever we know how to order it to perform.”

Turing: machines surprise me all the time. And instead of programming an adult mind, build a child machine and educate it.

Keep that sentence. It is the first mention of a learning machine.

Does the test still work?

ELIZA (Weizenbaum, 1966): a few pattern rules, and some users confided in it anyway.

The Chinese Room (Searle, 1980): symbols shuffled correctly, nothing understood.

Recent controlled studies report that large language models are judged to be human about as often as, or more often than, real humans (Jones & Bergen).

The test measures our credulity as much as the machine's intelligence.

Exercise · Meet Alan

Alan is a Matrix bot (@alan:udk.ai) running on our own server. You will chat with “Alan” — but behind him may be an AI persona or another student. Alan relays every message, so you are never told which is which.

How to reach him: in Element (with your account on udk.ai or medienhaus.udk-berlin.de) start a direct message with @alan:udk.ai and type start.

Alan pairs you with a waiting fellow student or with an AI persona. After a few minutes he asks: “Am I a human or AI?” Then comes the reveal: which persona (and model) it was — or, if you spoke with a human, who.

Good to know: Alan cannot read encrypted chats, so use a normal unencrypted DM (if you invite him to an encrypted one, he leaves and opens a fresh DM with you). The conversations are stored for the course evaluation — don't share anything private.

Try Turing's own questions: “Please write me a sonnet on the Forth Bridge.” “Add 34957 to 70764.”

Decide: human or machine? Write down the three cues that decided it.

Turing's machine answered 105621. The right answer is 105721.

Debrief · What gave him away?

Which cues did you use? Speed? Spelling? Politeness? Never saying “I don't know”? A body, a weather, a bad day?

Humans make typos and slip. Turing wrote that a machine should deliberately introduce mistakes to be convincing.

Which cues tell you about the machine, and which only about your expectations of humans?

Back to your criterion from the Question of the Day: did Alan meet it?

Enigma

The Imitation Game (2014): the interview scene

Enigma: a German cipher machine. Press a key, a different letter lights up — and the rotors turn, so the next key is scrambled differently.

Bletchley Park: Turing designs the Bombe, a machine that hunts for the day's settings (building on Polish work).

A machine breaking a machine.

And enigma is also what we call a riddle. Keep both meanings in mind.

The question Hilbert asked

1928, David Hilbert: is there a mechanical procedure that decides, for any mathematical statement, whether it is provable?

Leibniz had dreamed of it: let us calculate.

1931, Kurt Gödel: every consistent formal system has true statements it cannot prove.

1936, Alonzo Church and Alan Turing, independently: no such procedure exists.

But to prove that nothing can be done, you first need to say exactly what “a procedure” is.

Computers were people

Until the 1940s a “computer” was a person who computes — often a woman with pencil and paper at a desk.

Turing asks: what does such a person actually do?

Looks at a symbol. Writes a symbol. Changes their state of mind. Moves on to the next square.

Strip away everything else:

a tape, a head, a finite list of rules.

a Turing machine #1

A "theoretical" machine consisting of
  • tape with discrete symbols
  • reading/writing header
  • table of rules
  • tape-moving mechanism
Visualization of the Turing Machine (Rosario van Tulpe, 2007, CC BY-SA)

Exercise · Be the machine

The tape holds a binary number: 1 0 1 1. The head stands on the rightmost digit. State: CARRY.

CARRY reads 1 → write 0, move left, stay in CARRY

CARRY reads 0 or blank → write 1, STOP

Run it with pencil and paper. What is on the tape when it stops? Now try 1 1 1.

It adds one: 1011 → 1100, 111 → 1000. Three rules, no understanding.

Anything you would call an algorithm can be written as such a table (Church–Turing thesis).

Exercise · Your hand is a Turing machine

Counting from 0 to 31 on the fingers of one hand is a Turing machine at work. Here is its anatomy:

Tape — your five fingers: thumb = rightmost cell, little finger = leftmost. Symbols — 1 finger up, 0 finger down.

Head — the finger you are looking at; it starts on the thumb. States — CARRY (start) and HALT.

Transition rules
CARRY reads 1 → write 0 (fold it down), move left, stay in CARRY
CARRY reads 0 → write 1 (raise it), HALT

One run = one count. Take 7 → 8: tape 0 0 1 1 1. Thumb 1→0, index 1→0, middle 1→0, ring 0→1, halt: 0 1 0 0 0.

Counting to 31 means starting the machine 31 times (57 steps in all). Same two rules every time; nothing in it “knows” what a number is. Adding two numbers on two hands is the same idea with a bigger rule table.

Now count up from 31: the head falls off the left end. Turing's tape is infinite; your hand is not. Borrow your other hand — or paper — and keep going.

Universal Turing machine

"It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D ["standard description" of an action table] of some computing machine M, then U will compute the same sequence as M." (Turing, 1936)

The tape can hold a machine

A universal machine reads the rules of another machine from its tape and behaves like it.

Program = data. Your laptop is such a machine; an app is just a long tape.

And a program that treats programs as data can also change them. Hold on to this for the learning machines.

Halting Problem

  • halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever
  • Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist
  • to prove this, he described a paradox involving a concept now known as "Turing machine"

Halting · the trick in four lines

Suppose a program H(p, x) always answers correctly: “p halts on x” or “p loops forever”.

Build D(p): ask H(p, p). If it says halts, loop forever. If it says loops, stop.

Run D on itself. Halts if and only if it loops.

Contradiction: H cannot exist. Some questions about programs no program can answer.

Question of the Day · Can machines think?

Turn to your neighbour. Two minutes.

What would a machine have to do for you to say “yes, it thinks”?

Write the criterion down.

We will test it at the end of the session.

philosopher's definition of "thinking"

“We may say that thinking is essentially the activity of operating with signs.”

— Ludwig Wittgenstein, The Blue Book (1933–1934), p. 6 of the commonly used edition

Computational machinery and intelligence (1950)

The enigma remains

Turing machine: what can be computed — defined by what a procedure does, not what it is made of.

Turing test: what we will call intelligent — defined by how it behaves toward us.

The question moves from “what is it?” to “what does it do with us?”

Next: Claude, Marvin, John &c. — from information theory to Dartmouth.