Chapter 1 · Lab

Lab: The Dream of Thinking Machines

Run this lab

Edit and run the chapter code

Choose an available implementation, change the code, then run it here or continue in the dedicated Labs workspace.

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.

Lab 1 - Build, Break and Bound Three Thinking Machines

Lab Brief

Difficulty: Beginner Estimated time: 75 minutes Lab ID: VOL1-SEC1-CH1-LAB1

Objective

Extend the chapter's program with a Turing machine, a threshold network and two ELIZA rules of your own, find the inputs that break each one, and finish with an evidence plan that says, for three components of a real workflow, whether you would enumerate or sample and how many runs you need.

Everything runs offline with examples/thinking_machines.py (standard-library Python) or java/ThinkingMachines.java (JDK 21). You can do Parts A to C with pencil and paper first and use the program to check.

Scenario

Your team is adding an AI assistant to the expense-claims process. Before anyone writes production code, your lead wants every engineer to be able to answer two questions in design reviews: "what exactly does this component compute?" and "what would convince you it never does the wrong thing?" This lab practises both on machines small enough to understand completely.

Tasks

Part A - A Turing machine that subtracts one

Write a rule table, in the chapter's (state, symbol) → (write, move, next state) form, that subtracts one from a binary number greater than zero. Hint: walk right to the end as before, then borrow leftwards: a 0 becomes 1 and the borrow continues; a 1 becomes 0 and the machine stops.
Trace your machine by hand on 1100 (twelve) and on 1000 (eight). Record the tape after every step.
Derive a step-count formula like n + k + 2, where k now counts trailing zeros. Check it against your traces.
Decide what your machine should do on input 0, then add the rules to the program as a second dictionary next to INCREMENT (in Java, a second map). run_machine reads INCREMENT directly, so give it the rule table as an extra argument first. Run all three inputs; the output for 1000 keeps its leading zero, 0111, which is still seven.

Part B - Threshold units and a two-layer network

Find weights and a threshold for NOR (fires only on (0, 0)) and for "x1 AND NOT x2". Check each in Figure 1.5 and in the program's pattern function.
Extend the exhaustive search to weights from −5 to 5, and the doubled threshold theta2 to −21 to 21 so that thresholds cover −10.5 to 10.5, and confirm that XOR and XNOR still never appear. Write down, in two or three sentences, why a wider search cannot help.
Build XNOR (fires when both inputs are equal) from two layers of units and print its truth table.

Part C - Make ELIZA fail

Add two rules to RULES: one for the keyword because (reassembly IS THAT THE REAL REASON) and one for mother or father (reassembly TELL ME MORE ABOUT YOUR FAMILY).
Write three sentences that produce fluent but absurd replies, and one sentence where two rules compete and the rank decides which fires.
Draft five questions you would ask any chatbot to separate fluency from knowledge. At least two must have answers you can check, and one must be unanswerable, so that the right response is to say so.

Part D - The evidence plan

The expense workflow has three new components:

a policy check that approves a claim only if a receipt is attached, the amount is under the category limit, and the claimant's manager is not the claimant (three yes/no facts);
a parser for an eight-digit cost-centre code;
an AI agent that reads receipts and proposes the category and amount for each claim.

For each component:

State whether it can express arbitrary behaviour, and count its inputs (or say why they cannot be counted).
Choose enumerate or sample, and justify the choice with the count.
For the agent, compute the clean runs needed to rule out a wrong-proposal rate above 2% and above 0.5% at 95% confidence, using the formula in the chapter and Part 4 of the program. Then name one permission you would withhold so that the worst failure becomes impossible rather than merely rare.

Deliverables

Your subtract-one rule table, two hand traces and the step-count formula, plus the program output for all three inputs.
The NOR, "x1 AND NOT x2" and XNOR settings with their truth tables, and your explanation of why no single unit computes XOR.
The two new ELIZA rules, the four test sentences with the program's replies, and your five chatbot questions.
A one-page evidence plan for the three expense components, ending in the two-sentence answer you would give a risk committee.

Verification

Run the Python and the Java versions after your changes and diff their outputs; if you changed only one, the diff shows exactly what you added.
Every hand trace must match the program's step count, and every step-count formula must predict the traces you did not use to derive it.
Recompute each runs-needed figure with the calculator in Figure 1.6.

Success Criteria

Your Turing machine subtracts one correctly on every input greater than zero, and your document says what it does on 0 and why.
Your XOR explanation would convince a reader who has not seen the chapter, without relying on the search result alone.
At least one of your ELIZA test sentences produces a reply that a careless reader could mistake for understanding.
The evidence plan enumerates both finite components (8 and 100,000,000 inputs), samples the agent with correctly computed run counts (149 clean runs for 2% and 598 for 0.5% at 95% confidence), and removes at least one dangerous permission.