Paper VIII — Computer Science and the Study of the Mind

30 QUESTIONS

1. 1.

   Is the mind a computer, or is the computer a mind-shaped tool? Distinguish the empirical claim from the metaphor.

2. 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. 3.

   Suppose instead that P = NP were proved by a non-constructive argument. What practical consequences would, and would not, follow?

4. 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. 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. 6.

   Kolmogorov complexity is uncomputable. Explain why, and explain how an uncomputable quantity can nonetheless ground a working theory of randomness and compression.

7. 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. 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. 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. 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. 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. 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. 13.

    Distinguish the FLP impossibility from the CAP theorem. Which makes the weaker assumptions, and why does that make it the stronger result?

14. 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. 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. 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. 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. 18.

    What does it mean for a network to memorise? Give an operational criterion that distinguishes memorisation from generalisation in a trained model.

19. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.

Download this paper (Markdown)