# 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: 1. **Define** a deterministic Turing machine (DTM) by its tape, states, and transition function, and hand-simulate one step. 2. **Define** the Boolean circuit model and contrast its *non-uniformity* with the uniformity of a Turing machine. 3. **Prove** that $\{\text{NAND}\}$ is functionally complete (universal) for Boolean functions, and build XOR from NANDs. 4. **State** the Church–Turing thesis and distinguish it from the **Extended** (efficiency) form. 5. **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](../../term-2-qc-core/c01-gates-circuits/01-single-qubit-gates.md). ### 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)$. 1. **NOT.** Feed both inputs the same wire: $$ x \uparrow x \;=\; \lnot(x \land x) \;=\; \lnot x . $$ 2. **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$.) 3. **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](../../term-3-algorithms/c06-complexity/01-bqp-quantum-complexity.md). --- ## 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. ```python """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.
--- ## Further Reading - **[Sip §3.1, §3.3]** Sipser — Turing machines, configurations, the Church–Turing thesis. The cleanest first source for the DTM formalism used here. - **[AB §1.2, §6.1–6.2]** Arora & Barak — Turing machines, the circuit model, uniformity, and the $\mathrm{P}$ ↔ uniform poly-size circuits equivalence. - **[NC §3.1]** Nielsen & Chuang — Turing machines and the (Extended) Church–Turing thesis, framed toward quantum computation; sets up the same "which thesis does quantum break" question. - **[Aar]** Aaronson — Chs. on computability and complexity for the intuition behind the ECT and $\mathrm{BQP}$. --- ← Prev: [Discrete Fourier Transform](../c03-fourier-methods/03-discrete-fourier-transform.md) · Up: [Term 0](../README.md) · Next: [Complexity Classes](02-complexity-classes.md) →