Paper VIII — Computation
32 QUESTIONS
Paper VIII covers computation in the widest sense the word will bear. Complexity and computability are examined through P versus NP and what a proof either way would forbid, undecidability and Rice’s theorem, Kolmogorov complexity, one-way functions and the recent meta-complexity characterisations, and the Church–Turing thesis in its logical and physical forms. Distributed and quantum computation are examined through FLP impossibility, the CAP theorem and the difference between them, Shor’s algorithm, and the distance between a below-threshold logical qubit and a cryptographically useful machine. Learning theory and machine learning appear as PAC bounds and the VC dimension, over-parameterised generalisation, and grokking. The paper then turns to mind: functionalism and multiple realizability, Marr’s three levels, associative memory as attractor dynamics, the Lucas–Penrose argument, the hard problem, consciousness as a natural kind, the adversarial-collaboration results, predictive processing, and whether a system could pass every behavioural test for understanding and understand nothing. Two later questions ask whether a musical score is a program, and what a navigational metric requires of the entorhinal grid.
Its rubric admits the theoretical study of mind as both science and philosophy of mind, and excludes every question of how minds or machines ought to be treated. What is examined is therefore the ability to hold a formal result and a philosophical claim apart while bringing them into contact: to state exactly what an impossibility theorem assumes, and exactly what follows for the world; to distinguish an empirical thesis about cognition from a metaphor about computers; to say what evidence would bear on a question about consciousness, and to frame the question so that evidence could bear on it at all.
Scope
The theoretical study of mind is admitted as science and philosophy of mind; no moral or ethical question is admissible, including any question about how machines or minds ought to be treated.
Conduct of the response
Answer in the idiom of the college: provocations invite a disciplined essay; technical problems require correct, quantitative reasoning; interdisciplinary questions require two fields to be brought together. A response is an argument, not a survey; where the question admits a position, one is to be taken at the outset and defended. It must be exactly as technical as the question requires, and no more, and its course must remain followable by the educated layman. It may not exceed three thousand words, exclusive of equations, figures, tables, and references; the limit is a ceiling, not a target, and of two answers of equal force the shorter is judged the better. The full statement of the response required is given on the Responses page.
-
1.
Is the mind a computer, or is the computer a mind-shaped tool? Distinguish the empirical claim from the metaphor.
-
2.
What, exactly, does a proof of P ≠ NP forbid? State precisely which claims about the world would be established and which would remain open.
-
3.
Suppose instead that P = NP were proved by a non-constructive argument. What practical consequences would, and would not, follow?
-
4.
The halting problem is undecidable and Rice's theorem generalises this to all non-trivial semantic properties of programs. State Rice's theorem precisely, and identify a non-semantic property to which it does not apply.
-
5.
State the Church–Turing thesis and distinguish it sharply from the physical Church–Turing thesis. Which is a definition, which an empirical conjecture, and why does the distinction matter for claims about hypercomputation?
-
6.
Kolmogorov complexity is uncomputable. Explain why, and explain how an uncomputable quantity can nonetheless ground a working theory of randomness and compression.
-
7.
One-way functions may or may not exist. Explain why their existence would imply P ≠ NP but is not known to be implied by it, and state what their existence would secure for cryptography.
-
8.
Recent meta-complexity results characterise the existence of one-way functions by the average-case hardness of a Kolmogorov-complexity problem. Explain the significance of reducing "does secure cryptography exist?" to a single, natural computational problem.
-
9.
Shor's algorithm factors integers in polynomial time on an ideal quantum computer. Given that fault-tolerant machines at cryptographic scale do not yet exist, explain what the error-correction threshold theorem promises and why crossing the threshold experimentally was the decisive step.
-
10.
Estimate the gap between a below-threshold logical qubit demonstrated in the laboratory and the resources a current estimate assigns to factoring a 2048-bit RSA integer. What does the size of that gap tell you?
-
11.
The FLP result proves that deterministic consensus is impossible in an asynchronous system with even one crash failure. State the assumptions precisely, and explain how real systems achieve consensus in apparent defiance of it.
-
12.
The CAP theorem is often stated as "consistency, availability, partition-tolerance: choose two." Give the precise statement, and explain why the popular slogan is misleading.
-
13.
Distinguish the FLP impossibility from the CAP theorem. Which makes the weaker assumptions, and why does that make it the stronger result?
-
14.
The Curry–Howard correspondence identifies proofs with programs and propositions with types. State the correspondence, and explain what it means to say that to run a program is to normalise a proof.
-
15.
PAC learning bounds the samples needed to learn a concept class. State the role of the VC dimension, and explain what the no-free-lunch theorems deny to any learner that PAC learning does not restore.
-
16.
Modern over-parameterised networks generalise well despite interpolating their training data. Explain the double-descent curve and benign overfitting, and say why classical bias–variance reasoning did not predict them.
-
17.
"Grokking" names delayed generalisation: a network that has overfit continues training and later generalises abruptly. What would have to be true of the loss landscape for this to occur, and what does it show about the relationship between fitting and understanding?
-
18.
What does it mean for a network to memorise? Give an operational criterion that distinguishes memorisation from generalisation in a trained model.
-
19.
Marr's three levels distinguish the computational, algorithmic, and implementational descriptions of a cognitive system. Apply all three to a single capacity — say, associative recall — and state what is lost if any level is omitted.
-
20.
Hopfield networks store patterns as attractors in an energy landscape; the 2024 Nobel Prize in Physics recognised this lineage. Explain associative memory as attractor dynamics, and state the capacity limit as a function of network size.
-
21.
Functionalism holds that mental states are individuated by their causal roles, entailing multiple realizability. State the strongest version of the multiple-realizability thesis, and the strongest objection to it.
-
22.
Searle's Chinese Room argues that syntax is insufficient for semantics. State the argument, the Systems Reply, and Searle's response to it, and say which premise you take to bear the weight.
-
23.
The symbol grounding problem asks how symbols acquire meaning without an infinite regress of definitions. State Harnad's formulation, and explain why sensorimotor grounding is proposed as a solution.
-
24.
Lucas and Penrose argue from Gödel's incompleteness theorems that the mind is not a formal system. State the argument, and the standard objection that it equivocates on what the human mathematician can know to be consistent.
-
25.
The frame problem, in its philosophical form, concerns how a system knows what does not change when it acts. Distinguish the technical frame problem in logic from the philosophical one, and explain why the latter is harder.
-
26.
Chalmers's hard problem distinguishes the functions of consciousness from experience itself. State the explanatory gap precisely, and explain why solving all the "easy problems" would, on Chalmers's view, leave the hard problem untouched.
-
27.
Is consciousness a natural kind? Frame the question so that it has an empirical answer, and say what evidence would bear on it.
-
28.
Integrated Information Theory and Global Neuronal Workspace Theory make divergent predictions about the neural basis of consciousness. Given the 2025 adversarial-collaboration results and the 2023 dispute over whether IIT is falsifiable, assess what an adversarial collaboration can and cannot settle.
-
29.
Predictive processing casts the brain as a hierarchical prediction engine minimising surprise, formalised in Friston's free energy principle. State the principle, and explain the objection that a system could minimise surprise trivially by seeking a dark, unchanging room — and how the theory answers it.
-
30.
Could a system pass every behavioural test for understanding and understand nothing? State the conditions under which that claim would be empirical rather than merely verbal, using the stochastic-parrots-versus-emergent-world-models debate as your test case.
-
31.
Is a musical score a program? Say what it fixes and what it delegates to the performer, and whether the distinction survives a sequencer.
-
32.
Grid cells tile the plane hexagonally. State what a navigational metric must supply, and decide whether the entorhinal code supplies it or merely correlates with it.
Questions added by Examination Expansion v5.0, which extended the examination to music and geography. All earlier questions stand verbatim and unrenumbered.