Models of Computation

Before we can ask what a quantum computer can do faster, we must pin down what "compute" even means. A model of computation is a precise mathematical object — a machine, a circuit, an algebra — against which we measure every claim of correctness and efficiency. The deep surprise of the 20th century is that the most natural-looking models all compute exactly the same functions. The deep surprise of the late 20th century is that they may not all compute them equally fast — and that is the door quantum computing walks through.

Learning Objectives

By the end of this lesson you will be able to:

Define a deterministic Turing machine (DTM) by its tape, states, and transition function, and hand-simulate one step.
Define the Boolean circuit model and contrast its non-uniformity with the uniformity of a Turing machine.
Prove that $\{\text{NAND}\}$ is functionally complete (universal) for Boolean functions, and build XOR from NANDs.
State the Church–Turing thesis and distinguish it from the Extended (efficiency) form.
Explain precisely which thesis quantum computing is conjectured to violate, and why classical models are robust under the polynomial-time-equivalence relation that the Extended thesis demands.

Intuition

You already know algorithms operationally: you write Python, it runs. But "an algorithm" as a mathematical object needs a substrate. Three substrates dominate, and they form a ladder of abstraction:

Turing machine (TM) — a single, fixed finite program scanning an unbounded tape. One machine handles inputs of every length. This is the model of uniform computation and the gold standard for "computable."
Boolean circuit — a finite acyclic network of AND/OR/NOT gates wired to a fixed number of input bits. Each input length $n$ needs its own circuit $C_n$ ; a family $\{C_n\}$ computes a function on all lengths. This is non-uniform hardware.
Boolean algebra — the algebra of bits the circuit gates obey. The pivotal structural fact is that one humble gate, NAND, suffices to express the entire algebra.

The reason to learn all three is that quantum computing borrows from each: the circuit model becomes the quantum circuit (Term 2), reversible gates (next lesson) sit between Boolean algebra and unitary gates, and the efficiency question — does a quantum TM solve some problem polynomially faster than any classical one? — is a statement about the Extended Church–Turing thesis that we set up at the end.

A guiding analogy: a Turing machine is a recipe (one document, works for any quantity of ingredients); a circuit is a factory line hard-wired for one batch size. They are inter-translatable, but the translation has a cost, and cost is the whole story of complexity.

Theory

1. The deterministic Turing machine

A deterministic Turing machine is a 7-tuple [Sip §3.1], [AB §1.2]

M = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ q_{\text{acc}},\ q_{\text{rej}}),

where

$Q$ is a finite set of control states;
$\Sigma$ is the input alphabet (e.g. $\{0,1\}$ ), with the blank symbol $\sqcup \notin \Sigma$ ;
$\Gamma \supseteq \Sigma \cup \{\sqcup\}$ is the tape alphabet;
$q_0 \in Q$ is the start state, and $q_{\text{acc}}, q_{\text{rej}} \in Q$ are the halting states (accept / reject), $q_{\text{acc}} \ne q_{\text{rej}}$ ;
$\delta : (Q \setminus \{q_{\text{acc}}, q_{\text{rej}}\}) \times \Gamma \;\to\; Q \times \Gamma \times \{L, R\}$ is the transition function.

The machine has a two-way infinite tape of cells, each holding one symbol of $\Gamma$ , and a head positioned over one cell. The tape begins with the input $w \in \Sigma^*$ written left-to-right and $\sqcup$ everywhere else; the head starts on the leftmost input cell in state $q_0$ .

A configuration captures the entire instantaneous state: the control state, the tape contents, and the head position. We write it $u\, q\, v$ , meaning the tape reads $uv$ (then blanks), the head is on the first symbol of $v$ , and the control is in state $q$ .

One step. If $\delta(q, a) = (q', b, D)$ , then in state $q$ scanning symbol $a$ the machine (i) overwrites $a$ with $b$ , (ii) moves the head one cell in direction $D \in \{L,R\}$ , and (iii) enters state $q'$ . Because $\delta$ is a function (single-valued), the next configuration is unique — this is exactly what deterministic means. The machine halts on reaching $q_{\text{acc}}$ (accept) or $q_{\text{rej}}$ (reject); it may also run forever.

The machine decides a language $L \subseteq \Sigma^*$ if it halts on every input and accepts exactly the strings in $L$ . The time $t_M(w)$ is the number of steps before halting; the space is the number of distinct tape cells visited. These two cost measures are the seeds of all complexity theory (next lesson).

Why this primitive model? It is deliberately minimal so that anything it cannot do is provably uncomputable, and so that its time/space costs are unambiguous. Realistic features (multiple tapes, random access, a CPU) only change running time by a polynomial factor — a fact we will lean on heavily.

2. The Boolean circuit model

A Boolean circuit $C$ on $n$ inputs is a directed acyclic graph (DAG) whose [AB §6.1]

source nodes are the $n$ input variables $x_1,\dots,x_n$ (and optionally constants $0,1$ );
internal nodes are gates labelled from a basis, classically $\{\land, \lor, \lnot\}$ (AND, OR, NOT), with the in-degree (fan-in) matching the gate's arity;
one node is designated the output (multi-output circuits designate several).

The circuit computes a function $f : \{0,1\}^n \to \{0,1\}$ by evaluating gates in topological order. Two cost measures dominate:

size $\;=\;$ number of gates (analogue of time);
depth $\;=\;$ longest input-to-output path (analogue of parallel time).

The crucial structural difference from a TM is non-uniformity. A single circuit has a fixed number of input wires, so it only handles inputs of one length $n$ . To compute a function on all lengths we need a circuit family $\{C_n\}_{n \ge 0}$ , one circuit per length. There is no a priori requirement that the $C_n$ be related, let alone generated by a single finite program. That freedom makes circuit families strictly more powerful in principle (they can even compute undecidable functions, by hard-wiring the answer into each $C_n$ ) — which is precisely why, when we use circuits as a complexity model, we impose uniformity: a single TM must output the description of $C_n$ given $1^n$ . Uniform polynomial-size circuit families turn out to be equivalent to polynomial-time TMs [AB §6.2].

The quantum circuit model (Term 2) is the direct descendant of this picture: replace Boolean gates with unitary gates on qubit wires. The same uniformity caveat applies. See Term 2.1 · Single-Qubit Gates.

3. Boolean algebra and functional completeness

The gates obey Boolean algebra: the two-element algebra $(\{0,1\}, \lor, \land, \lnot)$ with identities such as $x \lor 0 = x$ , $x \land 1 = x$ , the distributive laws, and the De Morgan duality $\lnot(x \land y) = \lnot x \lor \lnot y$ .

A set of gates is functionally complete (universal) if every Boolean function $f:\{0,1\}^n\to\{0,1\}$ can be expressed using only those gates. The standard basis $\{\land, \lor, \lnot\}$ is complete, via the disjunctive normal form (DNF): for any $f$ ,

f(x) \;=\; \bigvee_{\,a \,:\, f(a)=1}\;\Big(\bigwedge_{i:\,a_i=1} x_i \;\land\; \bigwedge_{i:\,a_i=0} \lnot x_i\Big).

Each clause is an AND of literals that is true on exactly one input $a$ ; OR-ing the true rows reconstructs $f$ . (If $f \equiv 0$ the empty disjunction is $0$ .) This is a complete constructive proof that $\{\land,\lor,\lnot\}$ is universal.

Theorem (NAND is universal)

Let $\operatorname{NAND}(x,y) := \lnot(x \land y)$ . The single gate $\{\operatorname{NAND}\}$ is functionally complete.

Proof. It suffices to reconstruct $\{\lnot, \land, \lor\}$ from NAND, since that set is already complete. Write $a \uparrow b := \operatorname{NAND}(a,b) = \lnot(a\land b)$ .

NOT. Feed both inputs the same wire: $x \uparrow x \;=\; \lnot(x \land x) \;=\; \lnot x .$
AND. Negate the NAND of the inputs: $(x \uparrow y) \uparrow (x \uparrow y) \;=\; \lnot(x \uparrow y) \;=\; \lnot\lnot(x\land y) \;=\; x \land y .$ (We used the just-proved NOT on the wire $x \uparrow y$ .)
OR. By De Morgan, $x \lor y = \lnot(\lnot x \land \lnot y) = (\lnot x)\uparrow(\lnot y)$ . Substituting the NOT construction, $x \lor y \;=\; (x \uparrow x) \uparrow (y \uparrow y).$

Since $\{\lnot, \land, \lor\}$ is complete and each is now a NAND expression, $\{\operatorname{NAND}\}$ is complete. $\blacksquare$

The identical argument shows $\{\operatorname{NOR}\}$ (with $\operatorname{NOR}(x,y)=\lnot(x\lor y)$ ) is universal, using the dual De Morgan law. NAND/NOR universality is why physical logic families are built almost entirely from one gate type. By contrast, $\{\land,\lor\}$ alone is not complete: both gates are monotone (flipping an input from $0$ to $1$ never flips the output $1\to0$ ), so they can only build monotone functions — and $\lnot x$ is not monotone. This monotonicity argument is a clean example of a "no-go" proof by an invariant, a style we will reuse for no-cloning later.

Building XOR from NAND

$x \oplus y = (x \land \lnot y) \lor (\lnot x \land y)$ . A compact, classic 4-NAND realization is

\begin{aligned} t &= x \uparrow y, \\ x \oplus y &= (x \uparrow t) \uparrow (y \uparrow t). \end{aligned}

We verify it exhaustively in the code section (the surest proof for a small Boolean identity is the truth table).

4. The Church–Turing thesis, and its extended form

The models above — TMs, uniform circuits, the $\lambda$ -calculus, general recursive functions, your Python interpreter — all compute exactly the same class of functions. This empirical robustness is crystallized as a thesis (not a theorem — it relates the informal notion "effectively computable" to a formal one):

Church–Turing thesis (CTT). Every function that can be computed by any physically realizable effective procedure is computable by a Turing machine.

The CTT is about what is computable, ignoring efficiency. There is a sharper, far more fragile claim about how fast:

Extended (Strong) Church–Turing thesis (ECT). Every physically realizable model of computation can be simulated by a (probabilistic) Turing machine with at most polynomial overhead in time.

The ECT says the class of efficiently solvable problems — not just the class of solvable ones — is model-independent. It is what licenses us to speak of "polynomial time" $\mathrm{P}$ as a robust, machine-independent notion: RAM machines, multi-tape TMs, your laptop, all simulate one another with polynomial slowdown, so they agree on $\mathrm{P}$ . The ECT is the backbone of the next lesson.

Where quantum enters. A quantum Turing machine (equivalently, a uniform family of quantum circuits) is also physically realizable, in principle. The class of problems it solves efficiently is $\mathrm{BQP}$ (Term 3.6). Shor's polynomial-time factoring algorithm gives strong evidence that

\mathrm{BQP} \;\not\subseteq\; \mathrm{BPP}\quad(\text{conjectured}),

i.e. that a quantum machine is not polynomially simulable by any classical probabilistic one. If true, this refutes the Extended Church–Turing thesis (the efficiency form) — while leaving the original CTT untouched, because a quantum computer still computes only Turing-computable functions (a classical TM can simulate it, just with exponential overhead). Pinning down "where quantum fits" is the punchline of the next two lessons and of Term 3.6 · BQP & Quantum Complexity.

Worked Examples

Example 1 — Hand-tracing a Turing machine

Consider a DTM over $\Sigma=\{0,1\}$ that flips every bit of its input (a unary NOT on the whole string) and halts. Two non-halting states suffice; we sweep right flipping bits until a blank.

\delta:\quad \begin{array}{ll} \delta(q_0, 0) = (q_0, 1, R), & \delta(q_0, 1) = (q_0, 0, R),\\ \delta(q_0, \sqcup) = (q_{\text{acc}}, \sqcup, R). & \end{array}

Trace on input $w = 011$ . We write the configuration as $u\,q\,v$ (head on first symbol of $v$ ):

\begin{aligned} &q_0\,\underline{0}11 &&\xrightarrow{\delta(q_0,0)=(q_0,1,R)}&& 1\,q_0\,\underline{1}1\\ &\; &&\xrightarrow{\delta(q_0,1)=(q_0,0,R)}&& 10\,q_0\,\underline{1}\\ &\; &&\xrightarrow{\delta(q_0,1)=(q_0,0,R)}&& 100\,q_0\,\underline{\sqcup}\\ &\; &&\xrightarrow{\delta(q_0,\sqcup)=(q_{\text{acc}},\sqcup,R)}&& 100\,\sqcup\,q_{\text{acc}} \end{aligned}

Output tape: $100$ — indeed $\lnot(011)$ bitwise. The machine ran in $|w|+1 = 4$ steps and used $|w|+1$ cells: linear time and space. This linear cost is the point — the TM definition makes "how long did it take" a counting question with no ambiguity.

Example 2 — Universality and a non-universal basis

(a) Express the 2-input multiplexer $\operatorname{MUX}(s,a,b) = (\lnot s \land a) \lor (s \land b)$ ("output $a$ if $s=0$ , else $b$ ") in the standard basis — it already is — and note that by NAND universality it has a pure-NAND realization. Concretely, using De Morgan on the outer OR,

\operatorname{MUX}(s,a,b) = \big((\lnot s)\uparrow a\big)\uparrow\big(s \uparrow b\big),

because $\big((\lnot s)\uparrow a\big) = \lnot(\lnot s \land a)$ and likewise for the other term, and the outer NAND combines them as $\lnot(\,\lnot(\lnot s\land a)\land\lnot(s\land b)\,) = (\lnot s\land a)\lor(s\land b)$ . So a 3-to-1 selector is just three NANDs plus one inverter.

(b) Show $\{\land,\lor\}$ cannot compute $\operatorname{NOT}$ . Every function built from $\land,\lor$ (and the inputs) is monotone: if $x \le x'$ coordinatewise then $f(x) \le f(x')$ , by induction on the circuit ( $a\land b$ and $a\lor b$ are each monotone in both arguments, and inputs are trivially monotone). But $\operatorname{NOT}(0)=1 > 0 = \operatorname{NOT}(1)$ violates monotonicity since $0 \le 1$ . Hence no $\{\land,\lor\}$ -circuit computes NOT, so the basis is not functionally complete. $\square$

Hands-on (Python)

Self-contained, dependency-free. We (1) evaluate small Boolean circuits over a NAND basis, including the 4-NAND XOR, verifying it against Python's ^; and (2) implement a toy single-step Turing machine that reproduces Example 1.

"""Models of Computation — runnable demos (plain Python, no dependencies)."""

# ---------------------------------------------------------------------------
# Part A. NAND universality: build NOT, AND, OR, and XOR from NAND alone,
# then verify each against Python's native operators over all inputs.
# ---------------------------------------------------------------------------

def NAND(a: int, b: int) -> int:
    """The one universal gate: NAND(a, b) = NOT (a AND b)."""
    return 1 - (a & b)            # a, b in {0,1}; result in {0,1}

def NOT(x: int) -> int:
    return NAND(x, x)             # x↑x = ¬x

def AND(x: int, y: int) -> int:
    t = NAND(x, y)
    return NAND(t, t)             # ¬(x↑y) = x∧y

def OR(x: int, y: int) -> int:
    return NAND(NOT(x), NOT(y))   # De Morgan: (¬x)↑(¬y) = x∨y

def XOR(x: int, y: int) -> int:
    """Classic 4-NAND XOR:  t = x↑y;  out = (x↑t) ↑ (y↑t)."""
    t = NAND(x, y)
    return NAND(NAND(x, t), NAND(y, t))

def truth_table(f, arity):
    """Yield (inputs_tuple, output) over all 2**arity assignments."""
    for n in range(2 ** arity):
        bits = tuple((n >> (arity - 1 - i)) & 1 for i in range(arity))
        yield bits, f(*bits)

# Verify the NAND-built gates against Python's reference semantics.
assert all(out == (1 - x)        for (x,),    out in truth_table(NOT, 1))
assert all(out == (x & y)        for (x, y),  out in truth_table(AND, 2))
assert all(out == (x | y)        for (x, y),  out in truth_table(OR,  2))
assert all(out == (x ^ y)        for (x, y),  out in truth_table(XOR, 2))
print("All NAND-built gates match their reference truth tables. ✓")

print("\nXOR truth table (built from 4 NANDs):")
for (x, y), out in truth_table(XOR, 2):
    print(f"  {x} XOR {y} = {out}")


# ---------------------------------------------------------------------------
# Part B. A toy deterministic Turing machine: one step at a time.
# We encode the configuration as (state, tape: dict[int,str], head: int) and
# run the bit-flip machine from Example 1.
# ---------------------------------------------------------------------------

BLANK = "_"

def step(delta, state, tape, head):
    """Apply one transition. Returns the next (state, tape, head)."""
    symbol = tape.get(head, BLANK)
    new_state, write, move = delta[(state, symbol)]
    tape = dict(tape)                 # copy so each config is immutable
    tape[head] = write
    head += 1 if move == "R" else -1
    return new_state, tape, head

def run(delta, start, accept, reject, w, max_steps=10_000):
    """Run until a halting state. Returns (accepted, final_tape_string, steps)."""
    tape = {i: ch for i, ch in enumerate(w)}     # input written left-to-right
    state, head, steps = start, 0, 0
    while state not in (accept, reject) and steps < max_steps:
        state, tape, head = step(delta, state, tape, head)
        steps += 1
    # Render the written portion of the tape (min..max index touched).
    lo, hi = min(tape), max(tape)
    out = "".join(tape.get(i, BLANK) for i in range(lo, hi + 1)).strip(BLANK)
    return state == accept, out, steps

# Example 1: flip every bit, then halt-accept on the first blank.
Q0, ACC, REJ = "q0", "qacc", "qrej"
bitflip_delta = {
    (Q0, "0"): (Q0, "1", "R"),
    (Q0, "1"): (Q0, "0", "R"),
    (Q0, BLANK): (ACC, BLANK, "R"),
}

accepted, output, steps = run(bitflip_delta, Q0, ACC, REJ, "011")
print(f"\nTuring machine on '011': output={output!r}, accepted={accepted}, steps={steps}")
assert output == "100" and accepted and steps == 4
print("Matches the hand-trace in Example 1. ✓")

Expected output (abridged):

All NAND-built gates match their reference truth tables. ✓

XOR truth table (built from 4 NANDs):
  0 XOR 0 = 0
  0 XOR 1 = 1
  1 XOR 0 = 1
  1 XOR 1 = 0

Turing machine on '011': output='100', accepted=True, steps=4
Matches the hand-trace in Example 1. ✓

Exercises

Attempt before expanding. Difficulty escalates easy → hard.

1. (Easy) NOR universality. Prove that $\{\operatorname{NOR}\}$ is functionally complete by expressing NOT, OR, and AND using only $\operatorname{NOR}(x,y)=\lnot(x\lor y)$ .

Solution

Write $a \downarrow b := \operatorname{NOR}(a,b)$ .

NOT: $x \downarrow x = \lnot(x \lor x) = \lnot x$ .
OR: $(x \downarrow y)\downarrow(x \downarrow y) = \lnot(x\downarrow y) = \lnot\lnot(x\lor y) = x\lor y$ .
AND: by De Morgan $x\land y = \lnot(\lnot x\lor\lnot y) = (\lnot x)\downarrow(\lnot y) = (x\downarrow x)\downarrow(y\downarrow y)$ .

Since $\{\lnot,\lor,\land\}$ is complete and each reduces to NORs, $\{\operatorname{NOR}\}$ is complete. $\blacksquare$

2. (Easy–Medium) Counting NANDs. Using the constructions in the lesson, count how many NAND gates the expressions for AND, OR, and the 4-NAND XOR use. Then give a NAND realization of $x \to y$ (material implication, $\lnot x \lor y$ ) and count its gates.

Solution

AND uses 2 NANDs ( $t=x\uparrow y$ , then $t\uparrow t$ ).
OR uses 3 NANDs ( $x\uparrow x$ , $y\uparrow y$ , then NAND of those).
XOR uses 4 NANDs as written.
$x\to y = \lnot x \lor y = \lnot(x \land \lnot y)$ . Note $x \uparrow \lnot y = \lnot(x\land\lnot y) = x\to y$ directly, and $\lnot y = y\uparrow y$ . So $x\to y = x \uparrow (y\uparrow y)$ : 2 NANDs.

3. (Medium) Adding a TM transition. Modify the bit-flip DTM so that it instead rejects if the input contains the substring 11, and accepts otherwise (it need not flip bits). Give the full $\delta$ . (Hint: one extra state to remember "the previous symbol was a 1.")

Solution

States $Q=\{q_0, q_1, q_{\text{acc}}, q_{\text{rej}}\}$ , where $q_1$ means "last symbol read was 1." Move right without writing ( $D=R$ , write back the same symbol):

\begin{array}{ll} \delta(q_0,0)=(q_0,0,R) & \delta(q_0,1)=(q_1,1,R)\\ \delta(q_1,0)=(q_0,0,R) & \delta(q_1,1)=(q_{\text{rej}},1,R)\\ \delta(q_0,\sqcup)=(q_{\text{acc}},\sqcup,R) & \delta(q_1,\sqcup)=(q_{\text{acc}},\sqcup,R) \end{array}

Reading two 1s in a row drives $q_1 \xrightarrow{1} q_{\text{rej}}$ . Otherwise a blank is reached in $q_0$ or $q_1$ and we accept. (You can verify by extending the run driver with these rules.)

4. (Medium) Uniform vs. non-uniform. Explain why an arbitrary circuit family $\{C_n\}$ can "compute" an undecidable language, yet no Turing machine can. What single requirement on the family closes this gap, and why?

Solution

Let $L\subseteq\{0,1\}^*$ be any (possibly undecidable) language. For each $n$ there are finitely many strings of length $n$ , so the restriction $L\cap\{0,1\}^n$ is some Boolean function $f_n$ , and every Boolean function has a circuit (DNF). Choosing $C_n$ to compute $f_n$ gives a family that decides $L$ — including undecidable $L$ like the halting set. The catch: there is no finite program producing the $C_n$ ; the family secretly contains the uncomputable information, one circuit at a time. Imposing uniformity — a single TM must output (a description of) $C_n$ on input $1^n$ in, say, polynomial time — forbids this, because then the family is generated by one finite, computable process. Uniform poly-size circuit families are exactly $\mathrm{P}$ [AB §6.2].

5. (Hard) Which thesis does quantum threaten? A colleague claims "quantum computers can compute things classical computers can't." Sharpen or refute this using the CTT vs. ECT distinction, and state precisely what Shor's algorithm is and is not evidence for.

Solution

The claim is false as stated under the standard CTT: a classical Turing machine can simulate any quantum circuit (track the $2^n$ amplitudes, apply each gate as a matrix–vector product), so quantum computers compute exactly the same functions — the original CTT is unthreatened. What quantum may threaten is the Extended CTT (efficiency): the classical simulation costs exponential time and space. Shor's polynomial-time factoring is strong evidence that $\mathrm{BQP}\not\subseteq \mathrm{BPP} $(since factoring is not believed to be in$ \mathrm{BPP}$), i.e. that no classical probabilistic machine simulates a quantum one with only polynomial overhead. That would refute the ECT — not the CTT. (It is evidence, not proof: factoring's classical hardness is itself unproven, and so is $\mathrm{BQP}\ne\mathrm{BPP}$ .) See Term 3.6.

6. (Hard) DNF size blow-up. Show that the DNF construction can produce a circuit of size $\Theta(n\cdot 2^n)$ in the worst case, and name a function achieving it. Why does this not contradict the existence of small circuits for most useful functions?

Solution

DNF has one clause per input $a$ with $f(a)=1$ ; each clause is an AND of $n$ literals (plus the $\lnot$ 's). If $f$ is $1$ on $\sim 2^{n-1}$ inputs — e.g. the parity function $f(x)=x_1\oplus\cdots\oplus x_n$ , which is $1$ on exactly half of all inputs — then DNF has $\sim 2^{n-1}$ clauses of width $n$ , so size $\Theta(n\,2^n)$ . This is a property of the generic DNF method, not of the function: parity actually has a circuit of size $O(n)$ (a chain of $n-1$ XOR gates, each $4$ NANDs). DNF is a universality witness (every $f$ has a circuit), not an efficient compiler. The whole subject of circuit complexity is finding small circuits; information-theoretic counting (Shannon) shows most $n$ -bit functions need size $\Theta(2^n/n)$ — but the functions we care about are rarely "most."

Checkpoint

1. What makes a Turing machine deterministic, and what object enforces it?

The transition $\delta$ is a single-valued function: each (state, scanned symbol) pair maps to exactly one (next state, write symbol, move). Hence each configuration has a unique successor.

2. State the key difference between a Turing machine and a circuit.

A TM is uniform: one finite program handles inputs of all lengths. A circuit is fixed to one input length $n$ ; computing on all lengths needs a family $\{C_n\}$ , which is non-uniform unless we explicitly require a single TM to generate the $C_n$ .

3. Prove in one line that NAND gives you NOT.

$x \uparrow x = \lnot(x\land x) = \lnot x$ . Feeding the same wire to both NAND inputs yields the inverter.

4. Why is $\{\land,\lor\}$ not functionally complete?

Both gates are monotone, so any circuit over them computes a monotone function; but $\operatorname{NOT}$ is non-monotone ( $0\mapsto1$ , $1\mapsto0$ ). Hence NOT is unreachable.

5. Distinguish the Church–Turing thesis from its Extended form.

CTT: every effectively computable function is Turing-computable (about computability). ECT: every physically realizable model is simulable by a (probabilistic) TM with only polynomial overhead (about efficiency). The ECT is what makes $\mathrm{P}$ machine-independent.

6. Which thesis does efficient quantum computation challenge, and why not the other?

The Extended (efficiency) form: a quantum machine appears not to be polynomially simulable classically (Shor). The original CTT survives because a classical TM still can simulate a quantum computer — only with exponential overhead — so the computable functions are unchanged.

Models of Computation

Learning Objectives

Intuition

Theory

1. The deterministic Turing machine

2. The Boolean circuit model

3. Boolean algebra and functional completeness

Theorem (NAND is universal)

Building XOR from NAND

4. The Church–Turing thesis, and its extended form

Worked Examples

Example 1 — Hand-tracing a Turing machine

Example 2 — Universality and a non-universal basis

Hands-on (Python)

Exercises

Checkpoint

Further Reading