Paper VIII — Computation: References
90 SOURCES · 30 QUESTIONS · ALL FREELY AVAILABLE
Each source carries a technical description and a plain one; authors’ own pages and encyclopaedia entries are linked where they exist. Every address on this page was verified live at publication. The paper itself: Paper VIII.
1. Is the mind a computer, or is the computer a mind-shaped tool? Distinguish the empirical claim from the metaphor.
The computational theory of mind
The empirical thesis stated at full strength — mental processes as computations — with its rivals and evidential standing.
In plain terms: The free scholarly account of the claim itself, kept distinct from the loose talk that borrows its words.
The research programme the empirical claim founded — representations and processes as testable hypotheses.
In plain terms: The free survey of the science built on taking the computer comparison seriously rather than figuratively.
The converse direction examined: machines built in the mind's image, and what their successes do and do not show.
In plain terms: The free entry on the tool shaped like its maker — the metaphor's other half, inspected.
Background: Computational theory of mind · Cognitive science
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.
Exactly the question's audit: what a separation would establish, what it would leave open, and the barriers to proving it.
In plain terms: The free definitive survey of the great problem — careful about what an answer would and would not mean.
Computational complexity theory
The conceptual frame: worst-case asymptotic classification, and the gap between class membership and worldly claims.
In plain terms: The free philosophical entry on what complexity statements are actually about.
P vs NP (official problem description)
The problem as formally posed — the precise statement any claimed consequence must be measured against.
In plain terms: The free official formulation, worth a million dollars and stated in one page.
Background: P versus NP problem · Computational complexity theory
3. Suppose instead that P = NP were proved by a non-constructive argument. What practical consequences would, and would not, follow?
The equal-and-opposite scenario treated seriously: galactic algorithms, blowup in constants and exponents, and Levin's universal search.
In plain terms: The free survey that also asks the mirror question — what a 'yes' without a usable algorithm would change.
Computational Complexity: A Modern Approach (open draft)
The machinery for the distinction: self-reducibility turning decision into search, and where non-constructivity blocks the turn.
In plain terms: The free standard textbook draft — the technical difference between knowing a fast method exists and holding one.
Computational complexity theory
The asymptotic–practical gap analysed as a philosophical matter — what polynomial time does and does not promise.
In plain terms: The free entry on why 'efficient in principle' can still leave every safe uncracked.
Background: Constructive proof · NP-completeness
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.
The undecidability lineage in full: halting, its generalisation to semantic properties, and the semantic/syntactic boundary.
In plain terms: The free entry tracing the one impossibility that multiplies into all the others.
Theory of Computation (18.404J, open course)
Rice's theorem stated and proved in Sipser's course — with syntactic properties, such as instruction counts, outside its reach.
In plain terms: The free MIT course where the theorem is an exercise — and the exception the question requests is visible in its hypotheses.
The computability apparatus free and formal: indices, the s-m-n theorem, and reductions — the proof's working parts.
In plain terms: The open textbook where the machinery behind the theorem can be inspected piece by piece.
Background: Rice's theorem · Halting problem
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?
The distinction's authority: the thesis about effective calculability against physical variants — conflations catalogued and corrected.
In plain terms: The free definitive entry separating a near-definition from an empirical bet about nature.
Computation in physical systems
The physical thesis's home ground: what it is for nature to compute, and what hypercomputation would require of physics.
In plain terms: The free entry on the empirical half — whether the universe itself respects Turing's limit.
On computable numbers, with an application to the Entscheidungsproblem
The source text: computability defined by analysis of human calculation — the reason the original thesis resists refutation.
In plain terms: The free founding paper, where the limit was drawn by thinking about what a clerk with paper could do.
Background: Church–Turing thesis · Hypercomputation
6. Kolmogorov complexity is uncomputable. Explain why, and explain how an uncomputable quantity can nonetheless ground a working theory of randomness and compression.
Algorithmic information theory
The uncomputability argument and its uses: invariance, incompressibility, and randomness defined through description length.
In plain terms: The free expert page on measuring information by shortest description — and why no program can compute the measure.
The theory working despite uncomputability: universal priors approximated, bounds one-sided, applications thriving.
In plain terms: The free companion on how an unreachable ideal still steers real inference and compression.
Information Theory, Inference, and Learning Algorithms (open book)
The practical grounding: compression against computable models — the working face of the incomputable ideal.
In plain terms: The free classic where compression is practised daily under a theory whose summit cannot be climbed.
Background: Kolmogorov complexity · Algorithmic information theory
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.
Foundations of Cryptography (open drafts)
The canonical treatment: one-way functions as the minimal assumption from which pseudorandomness and encryption follow.
In plain terms: The free foundational text on the single hard-to-invert function that would underwrite all of cryptography.
Computational Complexity: A Modern Approach (open draft)
The asymmetry explained: existence implies P ≠ NP via easy verification, while worst-case hardness need not yield average-case inversion-resistance.
In plain terms: The free textbook on why the implication runs one way — hard problems somewhere are not hard problems everywhere.
The landscape between the worlds — Impagliazzo's five — locating cryptography's needs above bare separation.
In plain terms: The free survey mapping the possible universes, only some of which keep secrets safe.
Background: One-way function · 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.
On one-way functions and Kolmogorov complexity
The characterisation itself: one-way functions exist if and only if time-bounded Kolmogorov complexity is mildly hard on average.
In plain terms: The free breakthrough tying all of cryptography's possibility to one natural question about description length.
Algorithmic information theory
The problem on the other side of the equivalence — K-complexity and its resource-bounded variants — stated cleanly.
In plain terms: The free expert page on the quantity that turned out to hold cryptography's fate.
Foundations of Cryptography (open drafts)
What the reduction dignifies: the assumption structure of cryptography, now anchored to a single meta-computational problem.
In plain terms: The free foundations against which the new equivalence's significance is measured.
Background: Average-case complexity · Computational hardness assumption
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.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
The algorithm at source — period-finding by quantum Fourier transform — assuming the ideal machine the question brackets.
In plain terms: The free original that made factoring the quantum computer's signature promise.
Fault-tolerant quantum computation with constant error rate
The threshold theorem: below a constant physical error rate, arbitrarily long computation via concatenated correction.
In plain terms: The free theorem that turned 'too noisy' from a verdict into a threshold — a line that could one day be crossed.
Quantum error correction below the surface code threshold
The crossing itself: logical error rate falling as code distance grows — the theorem's premise realised in hardware.
In plain terms: The free landmark showing bigger finally meant better — the decisive experimental step the question names.
Background: Shor's algorithm · Quantum error correction
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?
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
The reference resource estimate: millions of physical qubits, thousands of logical ones, days of coherent operation.
In plain terms: The free benchmark costing — what breaking real keys would actually take, counted honestly.
How to factor 2048 bit RSA integers with less than a million noisy qubits
The estimate's trajectory: algorithmic and code improvements cutting requirements twenty-fold in six years.
In plain terms: The free update showing the mountain shrinking — while remaining a mountain.
Quantum error correction below the surface code threshold
The other side of the gap: one below-threshold logical qubit — against the thousands the estimates require.
In plain terms: The free paper defining today's summit camp, from which the distance to the peak can be measured.
Background: RSA (cryptosystem) · Qubit
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.
Impossibility of distributed consensus with one faulty process
The theorem with its exact assumptions: asynchrony, determinism, one crash — no protocol always terminates.
In plain terms: The free original impossibility — three modest assumptions, and agreement can be postponed forever.
The escape in practice: safety unconditional, termination bought with partial synchrony and leaders — FLP respected, not defied.
In plain terms: The free classic on how real systems agree anyway — by promising correctness always and progress only when the network behaves.
The modern working instance: randomised timeouts supplying what determinism cannot, per the theorem's own loophole.
In plain terms: The free home of the algorithm running the world's databases — the impossibility's daily workaround.
Background: Consensus (computer science) · Paxos (computer science)
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.
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services
The precise statement: linearizability and availability unachievable under partitions in an asynchronous network — nothing about choosing two at leisure.
In plain terms: The free proof behind the slogan — narrower, sharper, and only about what happens when the network splits.
CAP twelve years later: how the 'rules' have changed
The originator's correction: the two-of-three framing misleading, partitions rare, and the real design space continuous.
In plain terms: The free retraction of the slogan by the man whose conjecture it mangled.
Please stop calling databases CP or AP
The misuse audited: definitions in the proof too narrow for the labels practice attaches to systems.
In plain terms: The free essay showing why the popular taxonomy fails even on its own terms.
Background: CAP theorem · Distributed computing
13. Distinguish the FLP impossibility from the CAP theorem. Which makes the weaker assumptions, and why does that make it the stronger result?
Impossibility of distributed consensus with one faulty process
The weaker premises on display: no partitions needed, one crash suffices, and mere asynchrony does the damage.
In plain terms: The free theorem that forbids more while assuming less — the mark of the stronger result.
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services
The comparison's other term: impossibility conditional on partitions — a stronger adversary assumed to get the contradiction.
In plain terms: The free companion proof, needing the network actually to break before agreement must fail.
Please stop calling databases CP or AP
The two results disentangled in practice — which constraints bind which systems, and which get misattributed.
In plain terms: The free essay keeping the two impossibilities from being mistaken for one another.
Background: Fault tolerance · Distributed algorithm
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.
The correspondence stated in full: propositions as types, proofs as programs, normalisation as evaluation.
In plain terms: The celebrated free exposition of logic and programming discovered to be one subject twice.
The technical reference: the dictionary entry by entry, with cut-elimination as computation made precise.
In plain terms: A free working page for the exact translations the slogan compresses.
The framework's foundations: typed lambda calculi and normalisation — what 'running a proof' formally is.
In plain terms: The free scholarly entry on the system in which the identification lives.
Background: Curry–Howard correspondence · Type theory
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.
Understanding Machine Learning: From Theory to Algorithms (open copy)
The complete account: PAC defined, the fundamental theorem tying learnability to finite VC dimension, and no-free-lunch proved.
In plain terms: The free standard textbook — sample bounds, the capacity measure, and the theorem that forbids universal learners, all in one place.
The framework's founding paper: learning as efficient approximation with high probability, from samples alone.
In plain terms: The free original that made 'learnable' a mathematical property.
Machine Learning (6.867, open course)
The theory in teaching form: generalisation bounds and their scope — restrictions on the class, not on the world.
In plain terms: A free MIT course making plain what the guarantees buy — and what no theorem hands any learner for free.
Background: Probably approximately correct learning · Vapnik–Chervonenkis dimension
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.
Reconciling modern machine learning practice and the bias-variance trade-off
The curve named and drawn: risk descending again past interpolation, with the classical U only its first half.
In plain terms: The free paper that redrew the textbook picture — error falling anew exactly where theory said it must rise.
Deep double descent: where bigger models and more data hurt
The phenomenon at scale: descent in model size, data, and epochs across modern architectures.
In plain terms: The free systematic study showing the strange curve everywhere deep learning looks.
Benign overfitting in linear regression
The mechanism isolated: interpolation with vanishing excess risk when noise is absorbed along unimportant directions.
In plain terms: The free theory of fitting every point yet predicting well — the how behind the surprise.
Background: Double descent · Bias–variance tradeoff
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?
Grokking: generalization beyond overfitting on small algorithmic datasets
The phenomenon's discovery: perfect training fit followed, long after, by abrupt test-set generalisation.
In plain terms: The free paper that found networks understanding late — mastery arriving epochs after memorisation.
Progress measures for grokking via mechanistic interpretability
Inside the transition: a Fourier-based circuit forming gradually beneath a flat metric, then cleanup — continuous cause, discontinuous effect.
In plain terms: The free dissection showing the sudden leap was slow building in disguise.
Towards understanding grokking: an effective theory of representation learning
The landscape account: memorising and generalising solutions as competing basins, with regularisation tilting the late flow.
In plain terms: The free theory of the terrain — two valleys, and the slow drift from the shallow one to the true one.
Background: Grokking (machine learning) · Overfitting
18. What does it mean for a network to memorise? Give an operational criterion that distinguishes memorisation from generalisation in a trained model.
Understanding deep learning requires rethinking generalization
The operational baseline: networks fitting random labels perfectly — pure memorisation as demonstrated capacity.
In plain terms: The free experiment proving these models can memorise anything — making the distinction urgent.
Does learning require memorization? A short tale about a long tail
The criterion refined: label memorisation defined by leave-one-out sensitivity — and shown necessary for tail accuracy.
In plain terms: The free theory giving memorisation an exact test — and a surprising defence.
Quantifying memorization across neural language models
The criterion operationalised at scale: extractable verbatim continuation as the measurable signature.
In plain terms: The free measurement study — memorisation caught by asking the model to finish what it should not know.
Background: Generalization error · Language 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.
The computational theory of mind
Marr's trichotomy in its scholarly home: computational problem, algorithm, and implementation as distinct explananda.
In plain terms: The free entry where the three questions — what, how, and in what — are kept properly apart.
The levels at work across the field — and the losses when one is collapsed into another.
In plain terms: The free survey showing why an explanation missing a level explains less than it seems.
The worked capacity: associative recall as content-addressed retrieval, gradient-descent dynamics, and neural realisation — all three levels on one example.
In plain terms: The free expert page on remembering-by-settling — the single capacity the question asks to be described three ways.
Background: David Marr (neuroscientist) · Level of analysis
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.
Neural networks and physical systems with emergent collective computational abilities
The founding construction: symmetric weights, an energy function, and memories as minima retrieved by descent.
In plain terms: The free original — memory as a landscape, recall as rolling downhill to the nearest stored valley.
Physics for neural networks and machine learning (Nobel lecture)
The lineage from spin glasses to modern learning, recounted at the recognition the question cites.
In plain terms: The free lecture given for the prize itself — the story of attractor memory told by its author.
The capacity result stated: roughly 0.14N random patterns storable before retrieval degrades — with the phase-transition analysis behind it.
In plain terms: The free reference page — written by Hopfield — giving the exact limit the question requests.
Background: Hopfield network · Content-addressable memory
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.
The doctrine entire: states individuated by causal role, with the realizability corollary and its costs.
In plain terms: The free standard account of minds defined by what they do rather than what they are made of.
The thesis at maximum strength — and the Shapiro–Polger counterattack that realisations differ or do not multiply.
In plain terms: The free entry housing both the strongest statement and the strongest objection the question demands.
The mind/brain identity theory
The rival the argument targets — type identity — and its modern species-specific rejoinders.
In plain terms: The free account of the position multiple realizability was built to refute, still answering back.
Background: Functionalism (philosophy of mind) · Multiple realizability
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.
The argument, the Systems Reply, and Searle's internalisation response — the full dialectic with its pressure points.
In plain terms: The free definitive survey of the room, the replies, and where the burden finally rests.
A second full treatment, weighing which premise — syntax's insufficiency or the system's unity — carries the load.
In plain terms: A free companion account from an independent editorial tradition.
The computational theory of mind
The target doctrine — semantics from computation — whose viability the room contests.
In plain terms: The free entry on the thesis under attack, so the argument's stakes stay visible.
Background: Chinese room · John Searle
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.
The formulation at source: the merry-go-round of ungrounded symbols, and iconic–categorial grounding as the exit.
In plain terms: The free original stating the regress — dictionary entries defined only by other entries — and the sensorimotor way out.
The problem's setting: theories of content, and where bare symbol-manipulation fails to fix meaning.
In plain terms: The free survey of how inner states come to be about anything at all.
The proposed solution's programme: perception and action as constitutive of content, assessed with its evidence.
In plain terms: The free entry on grounding meaning in a body — the cure Harnad prescribed, examined.
Background: Symbol grounding problem · Embodied cognition
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.
Gödel's incompleteness theorems
The theorems with the hypothesis the argument trades on — consistency — and the standard diagnosis of equivocation.
In plain terms: The free careful statement of what was proved, against which the anti-mechanist leap is measured.
The Lucas–Penrose argument about Gödel's theorem
The argument and objection in dedicated form: outstripping the machine requires knowing one's own consistency — which Gödel denies.
In plain terms: The free entry devoted to the exact exchange the question sets — claim, objection, and the equivocation named.
Gödel's own disjunctive caution — mind exceeding machine or absolutely unsolvable problems — against the argument's confidence.
In plain terms: The free account of what the theorems' author thought they showed about minds: strictly less than Lucas claimed.
Background: Penrose–Lucas argument · Gödel's incompleteness theorems
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.
Both problems distinguished by their historian: the logical puzzle largely solved, the epistemological one — relevance itself — open.
In plain terms: The free authoritative entry on knowing what to ignore — easy to axiomatise, hard to possess.
Some philosophical problems from the standpoint of artificial intelligence
The origin: the frame axioms' proliferation in situation calculus — the technical problem as first posed.
In plain terms: The free founding paper where the difficulty was discovered by trying to write the world down.
Logic and artificial intelligence
The technical resolutions surveyed — circumscription, successor-state axioms — marking the residue logic does not touch.
In plain terms: The free entry on the machinery that tamed the formal problem, leaving the philosophical one standing.
Background: Frame problem · Situation calculus
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.
Facing up to the problem of consciousness
The distinction at source: functions dischargeable by mechanism, experience left over — the gap in its original wording.
In plain terms: The free paper that split the problem in two — and named the half that explanation keeps missing.
The gap situated among responses — from deflation to dualism — with the easy/hard architecture assessed.
In plain terms: The free survey of the whole debate the distinction reorganised.
The residue itself analysed: what-it-is-likeness, and the arguments that it outruns functional description.
In plain terms: The free entry on the felt quality that remains when all the mechanisms are accounted for.
Background: Hard problem of consciousness · Qualia
27. Is consciousness a natural kind? Frame the question so that it has an empirical answer, and say what evidence would bear on it.
The criteria that make the question empirical: projectibility, shared mechanism, cluster stability.
In plain terms: The free entry supplying the test — what any category must exhibit to be nature's own.
The neuroscience of consciousness
The evidence that would bear: whether measures and mechanisms converge on one phenomenon or fragment it.
In plain terms: The free survey of the experiments that could tell a single natural thing from a family resemblance.
The concept's varieties — access, phenomenal, self — whose unity or disunity is exactly what is at stake.
In plain terms: The free map of the concept whose seams the empirical question would find or fail to find.
Background: Natural kind · Neural correlates of consciousness
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.
The collaboration's results: preregistered predictions from both theories, each partly confirmed and partly violated.
In plain terms: The free landmark study the question cites — rival theories tested jointly, and neither emerging unscathed.
Integrated information theory (IIT) 4.0
The theory in its current formalisation — the axioms-to-postulates structure at the centre of the falsifiability dispute.
In plain terms: The free statement of the contested theory, exact enough for the argument about testability to be had.
The neuroscience of consciousness
The methodological frame: what adversarial collaboration can settle — predictions — and what it cannot — the theories' cores.
In plain terms: The free scholarly account of the experiment's reach, and the parts of the dispute no experiment closes.
Background: Integrated information theory · Global workspace theory
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.
Free-energy minimization and the dark-room problem
The objection and the official answer in one paper: expected surprise relative to a phenotype's priors, which no dark room satisfies.
In plain terms: The free exchange the question stages — why creatures built to expect a world cannot rest in an empty one.
The predictive-processing programme in context: action and perception under one imperative, with its critics.
In plain terms: The free entry situating the prediction-engine picture among theories of mind.
The explanatory standard: what a unifying principle owes — constraint, prediction, mechanism — for the field to count it.
In plain terms: The free survey against which a theory of everything mental is asked to earn its title.
Background: Predictive coding · Free energy principle
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.
Climbing towards NLU: on meaning, form, and understanding in the age of data
The sceptical pole made precise: form-only training cannot yield meaning — the octopus test as the behavioural-success-without-understanding case.
In plain terms: The free paper behind the parrot slogan — arguing perfect mimicry from text alone grounds nothing.
Emergent world representations: exploring a sequence model trained on a synthetic task
The empirical turn: a board-state model recovered from a next-move predictor's activations, and causally manipulated — the internal-representation criterion in action.
In plain terms: The free experiment that makes the dispute testable — opening the model and finding a world inside.
The debate over understanding in AI's large language models
The conditions clarified: which construals make the claim empirical — probes, interventions, generalisation — and which leave it verbal.
In plain terms: The free survey of the argument itself — sorting the testable question from the war of definitions.
Background: Stochastic parrot · Large language model