Chapter 1 · Python

Python: The Dream of Thinking Machines

Run this example

Edit and run the python example

Change the source and run it here. Use the output panel to compare your result with the expected highlights below.

thinking_machines.py

"""The thinking-machines lineage, run as code.

Part 1  A Turing machine that adds one to a binary number (Turing, 1936):
        a rule table, a tape and a head, traced step by step.
Part 2  Threshold units in the style of McCulloch and Pitts (1943): one unit
        computes AND, OR, NAND or NOT, an exhaustive search shows which
        two-input functions no single unit can compute, and two layers fix it.
Part 3  A handful of ELIZA-style rules (Weizenbaum, 1966) that reproduce the
        opening of his published DOCTOR transcript and answer nonsense just as
        fluently.
Part 4  What testing can certify: when every input can be checked, and how
        many failure-free runs it takes to bound a failure rate when it cannot.

Standard library only and fully deterministic; java/ThinkingMachines.java
prints byte-identical output.
"""

import math

# --- Part 1: a Turing machine -------------------------------------------------------

BLANK = "_"
# (state, symbol read) -> (symbol to write, head move, next state)
INCREMENT = {
    ("right", "0"): ("0", +1, "right"),
    ("right", "1"): ("1", +1, "right"),
    ("right", BLANK): (BLANK, -1, "carry"),
    ("carry", "1"): ("0", -1, "carry"),
    ("carry", "0"): ("1", 0, "done"),
    ("carry", BLANK): ("1", 0, "done"),
}
MOVES = {-1: "L", 0: "-", 1: "R"}

def show_tape(tape, head):
    cells = []
    for position in range(min(min(tape), head), max(max(tape), head) + 1):
        symbol = tape.get(position, BLANK)
        cells.append(f"[{symbol}]" if position == head else f" {symbol} ")
    return "".join(cells).rstrip()

def run_machine(word, trace):
    tape = dict(enumerate(word))
    head, state, steps = 0, "right", 0
    if trace:
        print("step  state  read  write  move  next    tape after the step")
        print(f"{0:>4}  {state:<5}  {'':>4}  {'':>5}  {'':>4}  {'':<6}  {show_tape(tape, head)}")
    while state != "done":
        symbol = tape.get(head, BLANK)
        write, move, next_state = INCREMENT[(state, symbol)]
        tape[head] = write
        head += move
        steps += 1
        if trace:
            print(f"{steps:>4}  {state:<5}  {symbol:>4}  {write:>5}  {MOVES[move]:>4}  "
                  f"{next_state:<6}  {show_tape(tape, head)}")
        state = next_state
    result = "".join(tape[p] for p in sorted(tape)).strip(BLANK)
    return result, steps

def turing_machine():
    print("=== Part 1: A Turing machine that adds one (rule table of 6 entries) ===")
    run_machine("1011", trace=True)
    print()
    print("input        value  output        value  steps  n + k + 2")
    for word in ("1011", "111", "0", "1001", "1111111111"):
        result, steps = run_machine(word, trace=False)
        trailing_ones = len(word) - len(word.rstrip("1"))
        predicted = len(word) + trailing_ones + 2
        print(f"{word:<11}  {int(word, 2):>5}  {result:<12}  {int(result, 2):>5}  "
              f"{steps:>5}  {predicted:>9}")
    print("(n = input length, k = trailing 1s: walk right, turn, carry, write.)")

# --- Part 2: threshold units ----------------------------------------------------------

INPUTS = ((0, 0), (0, 1), (1, 0), (1, 1))

def fires(w1, w2, theta2, x1, x2):
    """A unit fires when w1*x1 + w2*x2 >= theta; theta2 = 2 * theta keeps it exact."""
    return 1 if 2 * (w1 * x1 + w2 * x2) >= theta2 else 0

def pattern(w1, w2, theta2):
    return tuple(fires(w1, w2, theta2, x1, x2) for x1, x2 in INPUTS)

def threshold_units():
    print("=== Part 2: Threshold units (McCulloch and Pitts, 1943) ===")
    units = (("AND", 1, 1, 4), ("OR", 1, 1, 2), ("NAND", -1, -1, -3), ("NOT x1", -1, 0, -1))
    print("unit     w1  w2  theta   (0,0) (0,1) (1,0) (1,1)")
    for name, w1, w2, theta2 in units:
        outputs = "  ".join(f"{bit:>4}" for bit in pattern(w1, w2, theta2))
        print(f"{name:<7}  {w1:>2}  {w2:>2}  {theta2 / 2:>5.1f}   {outputs}")
    found = {}
    settings = 0
    for w1 in range(-3, 4):
        for w2 in range(-3, 4):
            for theta2 in range(-13, 14):
                settings += 1
                found[pattern(w1, w2, theta2)] = found.get(pattern(w1, w2, theta2), 0) + 1
    xor, xnor = (0, 1, 1, 0), (1, 0, 0, 1)
    print(f"Searched {settings:,} settings (weights -3..3, threshold -6.5..6.5 in steps of 0.5).")
    print(f"Two-input functions computed by at least one setting: {len(found)} of 16")
    print(f"Settings that compute XOR: {found.get(xor, 0)}   XNOR: {found.get(xnor, 0)}")
    print("XOR from two layers: hidden OR and NAND, then AND")
    for x1, x2 in INPUTS:
        h1, h2 = fires(1, 1, 2, x1, x2), fires(-1, -1, -3, x1, x2)
        print(f"  x=({x1},{x2})  OR={h1}  NAND={h2}  XOR={fires(1, 1, 4, h1, h2)}")

# --- Part 3: ELIZA-style rules ----------------------------------------------------------

FEELINGS = {"sad", "unhappy", "depressed", "sick"}
REFLECT = {"me": "you", "my": "your", "i": "you", "am": "are", "myself": "yourself",
           "you": "me", "your": "my"}
# (rank, decomposition pattern, reassembly); "*" matches any run of words, a set
# matches one word from the set, and {n} in the reassembly is the nth captured part.
RULES = (
    (10, ["*", "alike", "*"], "IN WHAT WAY"),
    (5, ["*", "i", "am", "*", FEELINGS, "*"], "I AM SORRY TO HEAR YOU ARE {3}"),
    (2, ["*", "my", "*"], "YOUR {2}"),
    (1, ["*", "always", "*"], "CAN YOU THINK OF A SPECIFIC EXAMPLE"),
)

def words(sentence):
    cleaned = "".join(c for c in sentence.lower() if c.isalpha() or c in " '")
    return cleaned.replace("i'm", "i am").split()

def match(pattern_items, tokens):
    """Return the captured parts for the first (shortest-first) match, or None."""
    if not pattern_items:
        return [] if not tokens else None
    item, rest = pattern_items[0], pattern_items[1:]
    if item == "*":
        for take in range(len(tokens) + 1):
            tail = match(rest, tokens[take:])
            if tail is not None:
                return [tokens[:take]] + tail
        return None
    if not tokens:
        return None
    if isinstance(item, set):
        tail = match(rest, tokens[1:]) if tokens[0] in item else None
        return None if tail is None else [[tokens[0]]] + tail
    return match(rest, tokens[1:]) if tokens[0] == item else None

def respond(sentence):
    tokens = words(sentence)
    for _, decomposition, reassembly in sorted(RULES, key=lambda rule: -rule[0]):
        parts = match(decomposition, tokens)
        if parts is not None:
            reply = reassembly
            for index, part in enumerate(parts, start=1):
                reply = reply.replace("{" + str(index) + "}",
                                      " ".join(REFLECT.get(w, w) for w in part))
            return reply.upper()
    return "PLEASE GO ON"

def eliza():
    print("=== Part 3: Four ELIZA-style rules ===")
    transcript = ("Men are all alike.",
                  "They're always bugging us about something or other.",
                  "Well, my boyfriend made me come here.",
                  "He says I'm depressed much of the time.")
    nonsense = ("My gloop made me frimble.",
                "I am deeply sick of purple arithmetic.",
                "The quarterly figures look fine.")
    for sentence in transcript + nonsense:
        print(f"> {sentence}")
        print(f"  {respond(sentence)}")

# --- Part 4: what testing can certify -------------------------------------------------------

def runs_needed(rate, confidence):
    """Failure-free runs after which a failure rate above `rate` is ruled out."""
    return math.ceil(math.log(1 - confidence) / math.log(1 - rate))

def upper_bound(runs, confidence):
    return 1 - (1 - confidence) ** (1 / runs)

def testing_limits():
    print("=== Part 4: What testing can certify ===")
    print("Inputs to check if every case is enumerated:")
    print(f"  three true/false facts                      {2 ** 3:>15,}")
    print(f"  one 32-bit integer                          {2 ** 32:>15,}")
    exponent = 100 * math.log10(128_256)
    print(f"  100 tokens from a 128,256-token vocabulary  {'10^' + format(exponent, '.1f'):>15}")
    print("Failure-free runs needed to rule out a failure rate above the target:")
    print("target   95% confidence   99% confidence   rule of three (3/p)")
    for rate, label in ((0.1, "10%"), (0.01, "1%"), (0.001, "0.1%"), (0.0001, "0.01%")):
        print(f"{label:<6}   {runs_needed(rate, 0.95):>14,}   {runs_needed(rate, 0.99):>14,}"
              f"   {round(3 / rate):>19,}")
    print("Upper bound on the failure rate after zero failures (95% confidence):")
    for runs, name in ((115, "tau-bench retail test tasks"), (500, "SWE-bench Verified tasks"),
                       (3000, "an in-house regression suite")):
        print(f"  {runs:>5,} clean runs  {name:<30}  {upper_bound(runs, 0.95) * 100:.2f}%")

def main():
    turing_machine()
    print()
    threshold_units()
    print()
    eliza()
    print()
    testing_limits()

if __name__ == "__main__":
    main()

Output

Run the code to see output here.

Example 1 - Tracing a Turing Machine by Hand, Then Breaking It

Scenario

You have the six-rule adder from Figure 1.4 and two inputs to try: 1001 (nine) and 1111 (fifteen). Before running any code, predict each output and step count, then trace the machine with pencil and paper. Finally, remove one rule and see what a missing rule does to a machine that otherwise works.

The rule table, written as (state, symbol read) → (write, move, next state):

(right, 0)     -> (0, R, right)
(right, 1)     -> (1, R, right)
(right, blank) -> (blank, L, carry)
(carry, 1)     -> (0, L, carry)
(carry, 0)     -> (1, stay, done)
(carry, blank) -> (1, stay, done)

Step 1: Predict from the formula

For an input of n digits ending in k ones, the machine takes n + k + 2 steps.

1001:  n = 4, k = 1  ->  4 + 1 + 2 = 7 steps, output 1010 (ten)
1111:  n = 4, k = 4  ->  4 + 4 + 2 = 10 steps, output 10000 (sixteen)

Step 2: Trace 1001

The head is shown in brackets.

Step	State	Reads	Writes	Moves	Tape afterwards
0	right				[1] 0 0 1
1	right	1	1	R	1 [0] 0 1
2	right	0	0	R	1 0 [0] 1
3	right	0	0	R	1 0 0 [1]
4	right	1	1	R	1 0 0 1 [_]
5	right	blank	blank	L	1 0 0 [1] _
6	carry	1	0	L	1 0 [0] 0 _
7	carry	0	1	stay	1 0 [1] 0 _

Seven steps, output 1010, as predicted. The chapter's program prints the same row count for 1001 in its summary table.

Step 3: Trace 1111 and watch the overflow

The first five steps walk right and turn around. Steps 6 to 9 turn each 1 into 0, moving left each time, until the head sits on the blank cell to the left of the number. Step 10 applies the rule (carry, blank) → (1, stay, done) and writes the new leading digit: 10000. The number got longer by one digit, exactly as 15 + 1 = 16 needs a fifth binary digit.

Step 4: Remove a rule

Delete the rule for (carry, blank) and run 1111 again. Everything proceeds as before until step 10, when the machine is in state carry reading a blank and finds no rule. A Turing machine with no applicable rule simply stops, leaving 0000 on the tape: a wrong answer produced without complaint. In the Python program the same situation raises a KeyError, which is the better failure because it is loud.

Lesson

A rule table is a complete specification only if it covers every (state, symbol) pair the machine can reach. The inputs that exercise a rarely used rule, here numbers that are all ones, are the ones a small test set is most likely to miss. Enumerating reachable (state, symbol) pairs is cheap for a machine this size, which is why the chapter recommends exhaustive checking wherever the space of cases is small enough to allow it.

Example 2 - Enumerate or Sample? Three Components, Three Answers

Scenario

A claims-processing team is adding three automated components and must tell its risk committee what evidence backs each one.

An eligibility rule: a claim goes to fast-track only if the policy is active, the amount is under the fast-track limit, and the claimant has no open fraud flag. Three yes/no facts.
A validator for a 32-bit policy-number field, which must accept every well-formed number and reject every malformed one.
An AI agent that drafts and runs small scripts to reconcile claim records against the payments ledger.

The committee's question is the same for all three: "How do you know it never does the wrong thing?"

Diagnosing It

Component	Can it express arbitrary behaviour?	Inputs to cover	Evidence you can offer
Eligibility rule	No: a fixed Boolean formula	2³ = 8	Every case, in one unit test
Policy-number validator	No: a fixed function of 32 bits	2³² = 4,294,967,296	Every case, by brute force on one machine
Reconciliation agent	Yes: it writes programs	unbounded	Withheld permissions plus a sampled failure-rate bound

The first two are finite. Checking all eight combinations of the eligibility rule is a table test; checking all 4.3 billion policy numbers against a reference implementation is an overnight job at most. For both, the committee can be told that the behaviour has been verified on every possible input.

The agent is different. The scripts it writes are programs, and Rice's theorem (1953) says no analyser can decide, for every program, a property such as "never modifies a paid claim". The evidence therefore has two parts.

Part 1: Make the worst outcomes impossible

Give the agent read-only credentials on the payments ledger and write access only to a staging table of proposed corrections. A human approves corrections before they reach production. Now "the agent never changes a paid claim" is true by construction, whatever scripts it writes, because the permission does not exist.

Part 2: Bound the rest by sampling

What remains is the rate at which the agent proposes wrong corrections. The team runs the agent on held-out reconciliation cases and counts failures. With zero failures in n independent runs, the highest failure rate still consistent with the data at 95% confidence is 1 − 0.05^(1/n), roughly 3/n:

clean runs    failure rate not yet ruled out (95%)
      115      2.57%
      300      0.99%
      500      0.60%
    3,000      0.10%

If the committee wants the wrong-proposal rate below 1%, the team needs about 300 consecutive clean runs; below 0.1%, about 3,000. A single failure changes the arithmetic: after one failure in n runs the 95% bound is about 4.7/n rather than 3/n, so 300 runs with one failure support only about 1.6%. A failure that repeats across similar cases also means the runs were not independent, so the team reviews every failure it finds.

The Answer to the Committee

For the rule and the validator: verified on every input. For the agent: it cannot change a paid claim because it has no permission to, a human approves every proposed correction, and 3,000 clean runs on held-out cases put its wrong-proposal rate below 0.1% at 95% confidence. The first two answers are proofs. The third is a bound plus a boundary, and it is the strongest honest answer available for a component that writes code.

Lesson

Decide the kind of evidence before arguing about its amount. Where the inputs are few enough to enumerate, enumerate. Where the component can do arbitrary things, remove the dangerous permissions first and then sample, and quote the result as a bound with its confidence, never as "it passed all our tests".

Runnable Example - Four Thinking Machines in One Program

One short program runs four of the chapter's machines: Turing's binary adder, McCulloch and Pitts's threshold units, a few rules in the style of Weizenbaum's ELIZA, and the arithmetic of what testing can certify. It uses only the Python standard library, needs no network, and finishes in well under a second. Its Java twin, in the Java tab, produces output identical to the last byte.

Expected output:

=== Part 1: A Turing machine that adds one (rule table of 6 entries) ===
step  state  read  write  move  next    tape after the step
   0  right                             [1] 0  1  1
   1  right     1      1     R  right    1 [0] 1  1
   2  right     0      0     R  right    1  0 [1] 1
   3  right     1      1     R  right    1  0  1 [1]
   4  right     1      1     R  right    1  0  1  1 [_]
   5  right     _      _     L  carry    1  0  1 [1] _
   6  carry     1      0     L  carry    1  0 [1] 0  _
   7  carry     1      0     L  carry    1 [0] 0  0  _
   8  carry     0      1     -  done     1 [1] 0  0  _

input        value  output        value  steps  n + k + 2
1011            11  1100             12      8          8
111              7  1000              8      8          8
0                0  1                 1      3          3
1001             9  1010             10      7          7
1111111111    1023  10000000000    1024     22         22
(n = input length, k = trailing 1s: walk right, turn, carry, write.)

=== Part 2: Threshold units (McCulloch and Pitts, 1943) ===
unit     w1  w2  theta   (0,0) (0,1) (1,0) (1,1)
AND       1   1    2.0      0     0     0     1
OR        1   1    1.0      0     1     1     1
NAND     -1  -1   -1.5      1     1     1     0
NOT x1   -1   0   -0.5      1     1     0     0
Searched 1,323 settings (weights -3..3, threshold -6.5..6.5 in steps of 0.5).
Two-input functions computed by at least one setting: 14 of 16
Settings that compute XOR: 0   XNOR: 0
XOR from two layers: hidden OR and NAND, then AND
  x=(0,0)  OR=0  NAND=1  XOR=0
  x=(0,1)  OR=1  NAND=1  XOR=1
  x=(1,0)  OR=1  NAND=1  XOR=1
  x=(1,1)  OR=1  NAND=0  XOR=0

=== Part 3: Four ELIZA-style rules ===
> Men are all alike.
  IN WHAT WAY
> They're always bugging us about something or other.
  CAN YOU THINK OF A SPECIFIC EXAMPLE
> Well, my boyfriend made me come here.
  YOUR BOYFRIEND MADE YOU COME HERE
> He says I'm depressed much of the time.
  I AM SORRY TO HEAR YOU ARE DEPRESSED
> My gloop made me frimble.
  YOUR GLOOP MADE YOU FRIMBLE
> I am deeply sick of purple arithmetic.
  I AM SORRY TO HEAR YOU ARE SICK
> The quarterly figures look fine.
  PLEASE GO ON

=== Part 4: What testing can certify ===
Inputs to check if every case is enumerated:
  three true/false facts                                    8
  one 32-bit integer                            4,294,967,296
  100 tokens from a 128,256-token vocabulary         10^510.8
Failure-free runs needed to rule out a failure rate above the target:
target   95% confidence   99% confidence   rule of three (3/p)
10%                  29               44                    30
1%                  299              459                   300
0.1%              2,995            4,603                 3,000
0.01%            29,956           46,050                30,000
Upper bound on the failure rate after zero failures (95% confidence):
    115 clean runs  tau-bench retail test tasks     2.57%
    500 clean runs  SWE-bench Verified tasks        0.60%
  3,000 clean runs  an in-house regression suite    0.10%

What to notice:

Part 1. The whole program is a six-entry dictionary from (state, symbol) to (write, move, next state). The loop never looks further than the cell under the head. The step count follows n + k + 2 for every input, including 1111111111, whose ten carries ripple all the way to a new leading digit.
Part 2. The search tries all 1,323 combinations of integer weights from −3 to 3 and thresholds from −6.5 to 6.5. Fourteen of the sixteen two-input truth tables appear; XOR and XNOR never do. The two-layer network computes XOR by combining OR and NAND, the construction that multi-layer networks generalise.
Part 3. Four rules reproduce the opening of Weizenbaum's published transcript. The same rules turn "My gloop made me frimble" into a confident question-shaped echo and read "sick of" as illness. The rules match word patterns; nothing in them represents what a gloop, a boyfriend or depression is.
Part 4. Enumeration is decisive up to billions of cases and hopeless for free text: the 100-token count is a 511-digit number. The sampling table shows why the rule of three is a good approximation at 95% confidence, and the last block shows how weak a clean pass on a public benchmark is as evidence of a low failure rate. The 3,000-run suite is an illustrative size, not a real benchmark.

Try this:

Delete the ("carry", BLANK) rule and run the machine on 111. Predict what happens before you run it; the answer is the machine-level version of an unhandled case.
Add a rule set that subtracts one instead of adding one. Which states do you need, and what should happen on input 0?
Change the threshold search to real-valued thresholds on a finer grid. Does XOR ever appear? Use the chapter's two-line argument to predict the answer first.
Give the ELIZA rules a new keyword, because, with the reassembly IS THAT THE REAL REASON, and find a sentence where it gives an absurd reply.
Set the confidence to 0.99 in upper_bound and recompute the benchmark rows.