Philosophy of Computer Science: Online Resources

Further Readings for Chapter 11:

Hypercomputation

Note 1: Many of these items are online; links are given where they are known. Other items may also be online; an internet search should help you find them.

Note 2: In general, works are listed in chronological order. (This makes it easier to follow the historical development of ideas.)

§11.1: Introduction

• On origami considered as an investigation of what paper-folding constructions are possible using only certain basic operations, see:
  • Landesman, C. (2021). A deep dive into the fold. The Paper, page 30.

• On "sub-Turing" computation, see Bernhardt 2016, Ch. 3, or any text on the theory of computation (such as those cited in the Further Readings for Ch. 7, as well as discussions of the "Chomsky hierarchy"

• On "non-Turing" computation (a more generalized notion of computation that is said to be "orthogonal" to Turing Machine computation, but is not considered to be hypercomputation), see:
  • MacLennan, Bruce J. (2004), "Natural Computation and Non-Turing Models of Computation", Theoretical Computer Science 317(1–3):115–145.

  For a related, more general notion of computation, see Piccinini 2020.

• For more on Copeland's views on hypercomputation, see:
  • Copeland 1997

  • Copeland, B.J. (1998). Even Turing machines can compute uncomputable functions. In Calude, C., Casti, J., and Dinneen, M.J., editors, Unconventional Models of Computation, pages 150–164. Springer-Verlag.

  • Copeland, B.J. and Proudfoot, D. (1999, April). Alan Turing's forgotten ideas in computer science. Scientific American, pages 98–103.
    • This elicited a rebuttal by Turing's biographer, Andrew Hodges

  • Copeland, B.J. and Sylvan, R. (1999). Beyond the universal Turing machine. Australasian Journal of Philosophy, 77(1):46–67.

  • Copeland, B.J. and Sylvan, R. (2000). Computability is logic-relative. In Hyde, D. and Priest, G., editors, Sociative Logics and Their Applications: Essays by the Late Richard Sylvan, pages 189–199. Ashgate.

  • Copeland, B.J. (2002a). Accelerating Turing machines. Minds and Machines, 12(2):303–326.

  • Copeland, B.J. (2002b). Hypercomputation. Minds and Machines, 12(4):461 502.

  • Copeland, B.J. and Shagrir, O. (2011). Do accelerating Turing machines compute the uncomputable? Minds and Machines, 21(2):221–239.

  • Copeland, B.J., Dresner, E., Proudfoot, D., and Shagrir, O. (2016). Time to reinspect the foundations? Communications of the ACM, 59(11):34–36.

  • Copeland et al. 2017

  • Copeland et al. 2018

  • Copeland, B.J. and Shagrir, O. (2020). Physical computability theses. In Hemmo, M. and Shenker, O., editors, Quantum, Probability, Logic: The Work and Influence of Itamar Pitowsky, pages 217–232. Springer, Cham, Switzerland

• Yet another form of hypercomputation, which does not fit easily into the categories of this chapter, is a generalization of Turing computability — which can be considered to be a branch of discrete mathematics — to the real numbers, so that there can be a theory of computation within continuous mathematics. This has been investigated in:
  • Blum, L., Shub, M., and Smale, S. (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines. Bulletin of the American Mathematical Society, 21(1):1–46.

  • Blum, L. (2004). Computing over the reals: Where Turing meets Newton.    Notices of the AMS, 51(9):1024–1034
    • (Note: there are two links here!)

  Their form of computation over the real numbers contains Turing computation as a special case.

• On what Turing might have thought about hypercomputation, see:
  • Hodges, A. (2004). What would Alan Turing have done after 1954? In Teuscher, C., editor, Alan Turing: Life and Legacy of a Great Thinker, pages 43–58. Springer, Berlin.

• For more on hypercomputation, see the following:

  • Sloman, A. (1996). Beyond Turing equivalence. In Millican, P.J. and Clark, A., editors, Machines and Thought: The Legacy of Alan Turing, Vol.nbsp;I, pages 179–219. Clarendon Press, Oxford.
    • Clarifies how hypercomputation can show how some aspects of human cognition might not be Turing computable. (Nevertheless, the question remains whether cognition in general is Turing computable (or can be approximated by a Turing Machine).)

  • Shagrir, O. (1997). Two dogmas of computationalism. Minds and Machines, 7:321–344
    • Suggests that a certain kind of hypercomputer "computes" in the sense that its operations are those of a Turing Machine, but its input is not recursive. So it is akin to trial-and-error "computing" or oracle machines.

  • Shagrir 1999, §2, pp. 132–133.
    • Observes that "The Church-Turing thesis is the claim that certain classes of computing machines, e.g., Turing Machines, compute effectively computable functions. It is not the claim that all computing machines compute solely effectively computable functions." That is, if a function is effectively computable, then it is Turing computable. But it is not the case that, if $C$ is a computing machine that "computes" function $f$, then $f$ is effectively computable. This is consistent with Kugel's views on trial-and-error machines; it is also consistent with the view that what makes interaction machines more powerful than Turing Machines is merely how they are coupled with either other machines or with the environment; it is not the machinery itself. Shagrir's goal is to argue for a distinction between algorithms and "computation", with the latter being a wider notion. That is, the scare-quoted term 'computes' in the last sentence of the previous paragraph doesn't refer to Turing computability, but to a more general kind of processing that can also be done on a Turing Machine.

  • Three collections — including essays by Bringsjord, Cleland, Copeland, Kugel, and Shagrir — are:
    • Copeland, B.J., editor (2002). Hypercomputation. Special issue of Minds and Machines 12(4) (November).

    • Copeland, B.J., editor (2003). Hypercomputation (continued). Special issue of Minds and Machines 13(1) (February).

    • Burgin, M. and Wegner, P. (2003). Special sessions on Beyond Classical Boundaries of Computability (parts I, II, III, & IV), 2003 Spring Western Section Meeting, American Mathematical Society

  • Cotogno, P. (2003). Hypercomputation and the physical Church-Turing thesis. British Journal for the Philosophy of Science, 54(2):181–224.
    • Argues that hypercomputation does not refute the Computability Thesis.
    • Welch, P.D. (2004). On the possibility, or otherwise, of hypercomputation. British Journal for the Philosophy of Science, 55:739–746,
      • A reply to Cotogno 2003.

  • Wells, B. (2004). Hypercomputation by definition. Theoretical Computer Science, 317:191–207, §3.
    • Contains a discussion of the relation between the Computability Thesis and the P=NP problem.

  • Dresner, E. (2008). Turing-, human- and physical computability: An unasked question. Minds and Machines, 18(3):349–355.
    • Clarifies the the difference between Turing's mathematical model of human computability and a possibly more extensive notion of physical computability.

  • Parker, M.W. (2009). Computing the uncomputable; or, the discrete charm of second-order simulacra. Synthese, 169:447–463.
    • Argues that "non-computable behavior in a model … [can be] revealed by computer simulation" (which is, of course, computable).

  • Piccinini, G. (2011). The physical Church-Turing thesis: Modest or bold? British Journal for the Philosophy of Science, 62:733–769, §4.
    • Discusses hypercomputational challenges to the "modest" physical Computability Thesis, which states that "any function that is physically computable is Turing computable" (p. 734).

  • Cooper, S. B. (2012). Incomputability after Alan Turing. Notices of the AMS, 59(6):776–784.
    • An interesting, illustrated historical survey.

§11.5: "Newer Physics" Hypercomputers:

• Copeland 1998, p. 151, footnote 2, distinguishes between "accelerating" Turing Machines and "Zeus" machines.
  • See also: Copeland 2002a and Copeland and Shagrir 2011.

• Davies, E.B. (2001). Building infinite machines. British Journal for the Philosophy of Science, 52:671 682.
  • Argues that an accelerating computer could be built "in a continuous Newtonian universe" (as opposed to the Malament-Hogarth spacetime mentioned in the epigraph to this section of the book), though not "in the real universe".

• Cockshott, P. and Michaelson, G. (2007). Are there new models of computation? Reply to Wegner and Eberbach. The Computer Journal, 50(2):232–247, §2.5, p. 235.
  • Rejects such relaxations of the laws of classical physics out of hand. They also give an excellent summary of Turing Machines and complexity theory, and they argue against a number of other hypercomputation proposals, including Wegner's interaction machines.

• On quantum computation — in addition to the Further Readings for Ch. 3 on quantum computing in general — see:
  • Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal computer. Proceedings of the Royal Society of London A, 400:97–117.
    • Discusses the Computability Thesis in the context of quantum computation and proves that quantum computers, although faster than non-quantum computers, are not computationally more powerful.
    • For brief discussion, see Bernhardt 2016, Ch. 4, esp. p. 173, note 5.

  • Brassard, G. (1995). Time for another paradigm shift. ACM Computing Surveys, 27(1):19–21.
    • A commentary on:
      • Hartmanis, J. (1995). On computational complexity and the nature of computer science. ACM Computing Surveys, 27(1):7–16. Reprinted, with added commentaries, from Communications of the ACM 37(10) (October 1994): 37 43. (discussed in §3.15.1)
    • Argues that probabilistic and — especially — quantum computers "may be qualitatively more powerful than classical machines".
    • For a reply, see:
      • Hartmanis, J. (1995). Response to the essays "On computational complexity and the nature of computer science". ACM Computing Surveys, 27(1):59–61.

  • Scott Aaronson has written extensively on quantum computation:
    • Aaronson, S. (2006). Phys771 lecture 4: Minds and machines.
      • Part of a course, "Quantum Computing Since Democritus". The first part discusses oracles and Turing reducibility in a very clear (but elementary) way, concluding that hypercomputation is not a serious objection to the Computability Thesis; later parts discuss AI.

    • Aaronson 2008 says that "Quantum computers would be exceptionally fast at a few specific tasks, but it appears that for most problems they would outclass today's computers only modestly. This realization may lead to a new fundamental physical principle."

    • Aaronson, S. (2013). Quantum Computing Since Democritus. Cambridge University Press, New York.
      • A book-length treatment that contains discussions of both quantum computing and hypercomputation.

    • Aaronson 2014 asks, "If there's no predeterminism in quantum mechanics, can it output numbers that truly have no pattern?"

  • Duwell 2021 is a survey of physical computation, including quantum computation.

• Further Reading on Malament-Hogarth Hypercomputation:

  For those of you curious about the epigraph to this section concerning Malament-Hogarth hypercomputation, here are some suggestions:

  • The 1992 paper cited in the Wikipedia article is:
    • Hogarth, M. (1992). Does general relativity allow an observer to view an eternity in a finite time? Foundations of Physics Letters, 5(2):173–181.

    His machines turn out to be related to Zeus machines. The introduction is worth quoting:

    "Any computer primed to perform an infinite number of computational steps must take an eternity to complete the task, because completion in a finite time would imply an unbounded signal velocity — conflicting with relativity theory. This would seem to suggest that the full potential of these computers is available only to immortal computer users. But … there is no reason why the computer user must remain beside the computer. If he follows a different worldline his clock will tick at a rate different to that of the computer's clock, and perhaps an extreme case could be organized in which the rates are such that the finite proper time as measured by the computer user "corresponds" to an infinite proper time as measured by the computer. In this case, and granting also that the computer can always signal to the computer user, the computer user will take only a finite time to view the eternity of the computer's life and with it the results of its computations." (pp. 173–174)

    And §2 ("The Story of Dave, HAL, and Goldbach") — a science fiction tale to illustrate his argument — is very much worth reading!

  • Button, T. (2009). SAD computers and two versions of the Church-Turing thesis. British Journal for the Philosophy of Science, 60:765–792.
    • Argues that Hogarth's model of hypercomputation is not a counterexample to the Computability Thesis.

  • Shagrir 2016, Fig. 2.2, shows that the Malament-Hogarth hypercomputer works like a trial-and-error machine (discussed in §11.10).

§11.8.1: "Internal" vs. "External" Inputs:

• On external inputs vs. internal states, see the discussion in Ritchie & Piccinini 2018, §§2 and 3.2.

• Other kinds of interactive computing include:
  1. "coupled" Turing Machines, each of whose outputs serve as inputs for the other; see:
     • Copeland and Sylvan 1999
     • Zenil and Hernández-Quiroz 2007

  2. "concurrent" computation.

• On reactive systems, see also Knuth, D.E. (2014, 20 May). Twenty questions for Donald Knuth, Question 13.

• Gurevich, Y. (1999). The sequential ASM thesis. Bulletin of the European Association for Theoretical Computer Science, 67:93–124, esp. pp. 93, 98.
  • Talks both about "algorithms that are closed in the sense that they do not interact with their environments" and about ones that do so interact (§5, pp. 111–115).
  • He also notes that, in the case of non-deterministic algorithms, "the active environment will make the choices" (p. 116).

§11.8.4: Can Interaction Be Simulated by a Non-Interactive Turing Machine?

• On the S-m-n Theorem:
  • First stated and proved in Kleene 1952, Theorem XXIII, p. 342.

  • It gets its name from the form that Kleene expressed it in, using a function that he called 'S^m_n'.

    It is also sometimes called the "Parameter Theorem" or the "Iteration Theorem" (Davis and Weyuker 1983, p. 64).

    Rogers 1967, Theorem IV, p. 22, calls it the "enumeration theorem" (but distinguishes it from what he calls the "s-m-n theorem" (Rogers 1967, Theorem V, pp. 23–24). Rogers 1967, p. 23, notes that it "shows that the computing agent … need not be human" — because the human "computing agent" in Turing's informal analysis can be replaced by a Universal Turing Machine.

  • My interpretation of the theorem is due to Case, J. Motivating the proof of the Kleene recursion theorem.

    In lectures at the University at Buffalo in the early 1980s, Case used the mnemonic "Stuff-em-in theorem" to emphasize that the external inputs could be "stuffed into" the computer program.

    Similar interpretations can be found in Cooper 2004, p. 64, and Homer and Selman 2011, p. 53.

    Kfoury et al 1982, p. 82, give a version of it stated in terms of computer programs.

  • Cooper 2004, p. 64, also notes that the existence of the Universal Turing Machine can be expressed — using our notation above (instead of his) — by taking y as a ("hardwired", non-universal) Turing Machine and s(x,y) as a Universal Turing Machine with y stored on its tape (as its software).

  • Ritchie & Piccinini 2018, §3.2, observe that "the different inputs and outputs of an ordinary finite-state automaton can be encoded in the initial and final states of an inputless and outputless finite-state automaton."

• For more on interactive computing, see:
  • van Leeuwen, J. and Wiedermann, J. (2000). The Turing machine paradigm in contemporary computing. In Engquist, B. and Schmid, W., editors, Mathematics Unlimited — 2001 and Beyond, pages 1139–1155. Springer-Verlag, Berlin.
    • Formalizes Wegner's ideas about interaction machines, arguing that "'interactive Turing machines with advice' … are more powerful than ordinary Turing machines."

  • For a debate between a hypercomputation skeptic and a believer, see Interactive Computation Is More Powerful Than Non Interactive (2014).

  • For more by Wegner and his colleagues, see:
    • Wegner, P. (1999). Towards empirical computer science. The Monist, 82(1):58–108.

    • Wegner, P. and Goldin, D.Q. (1999). Interaction, computability, and Church's thesis.
      • An unpublished attempt at formalizing some of Wegner's claims about interaction machines

    • Eberbach, E. and Wegner, P. (2003). Beyond Turing machines. Bulletin of the European Association for Theoretical Computer Science (EATCS), (81):279–304.
      • A useful survey, but with some seriously misleading comments about the history of computation and the nature of logic. For example, contrary to what the authors say,
        1. Turing 1936 was not "primarily a mathematical demonstration that computers could not model mathematical problem solving" (p. 279) (although it did include a mathematical demonstration that there were some mathematical problems that a computer could not solve).
        2. Hilbert did not take the Entscheidungsproblem "as a basis that all mathematical problems could be proved true or false by logic" (p. 279), simply because mathematical problems cannot be "proved true or false" — rather, mathematical propositions might be provable or not, and they might be true or false, but truth and falsity are semantic notions incapable of proof, whereas provability is a syntactic notion.

    • Wegner, P. and Goldin, D.Q. (2003). Computation beyond Turing machines. Communications of the ACM, 46(4):100–102.

    • Goldin, D.Q. and Wegner, P. (2004). The origins of the Turing thesis myth.

    • Goldin, D.Q., Smolka, S.A., Attie, P.C., and Sonderegger, E.L. (2004). Turing machines, transition systems, and interaction. Information and Computation, 194(2):101–128.
      • "present[s] … a new way of interpreting Turing-computation … that is both interactive and persistent … in the sense that the work-tape contents are maintained from one computation … to the next" (from the abstract)

    • Goldin, D.Q. and Wegner, P. (2008). The interactive nature of computing: Refuting the strong Church-Turing thesis. Minds and Machines, 18(1):17–38.

  • Hewitt, C. (2019, 10 July). Computer science must rely on strongly-typed Actors and theories for cybersecurity.
    • Argues in favor of interactive computation as a better model of computation than Turing Machines, and suggests that his version of it — (based on his Actor formalism for AI, which was a predecessor of object-oriented computing and which, he claims, avoids the Halting Problem) — is important for cybersecurity.

  • Chater, Nick (2022), "The Computational Society", Trends in Cognitive Sciences 26(12):1015–1017.
    • Discusses distributed computation (a form of interactive computation) as a model of "collective" cognition in societies.

  • Martin, Alice; Magnaudet, Mathieu; & Conversyt, Stéphane (2023), "Computers as Interactive Machines: Can We Build an Explanatory Abstraction?", Minds and Machines
    • Critiques both Wegner's approach and the view that oracle machines are a good model of interactive computing, and offers a "sketch" of an "execution model" of interactive computing.

§11.9: Oracle Computation:

• For more on oracle machines, see:
  • Feferman, S. (2006). Turing’s [PhD] thesis. Notices of the AMS, 53(10):1200–1206

  • Soare 2016, pp. xxi–xxii and §§3.2 & 17.4

• An excellent, relatively informal overview of relative computability for philosophers is:
  • Jenny, M. (2018). Counterpossibles in science: The case of relative computability. Noûs, 52(3):530–560, §2.

• Piccinini, G. (2003). Alan Turing and the mathematical objection. Minds and Machines, 13:23–48.
  • Primarily about Turing's views on AI, but also discusses his theory of computation and the role of "oracle" machines.

• For a science fiction treatment, see:
  • Egan, G. (2000). Oracle. Asimov's Science Fiction.

§11.10: Trial-and-Error Computation:

Philosophers, logicians, and computer scientists have all contributed to this theory:

• Hilary Putnam, Trial and error predicates and the solution to a problem of Mostowski. Journal of Symbolic Logic, 30(1) (1965):49–57.
  • Originated the term 'trial-and-error predicate'.

• Hintikka, J. and Mutanen, A. (1997). An alternative concept of computability. In Hintikka, J., editor, Language, Truth, and Logic in Mathematics, pages 174–188. Springer, Dordrecht, The Netherlands.
  • Introduced the phrase 'trial-and-error computability'.

• Gold, E.M. (1967). Language identification in the limit. Information and Control, 10:447 474.
  • Called such computation 'inductive inference'.

• Kugel, P. (2002). Computing machines can’t be intelligent (… and Turing said so). Minds and Machines, 12(4):563 579.
  • Claims to have originated the terms 'trial-and-error machine' and 'Putnam-Gold machine'.

• Soare 2009, §9.2, p. 388, refers to Putnam's trial-and-error predicates as "limit computable functions".

§11.10.2: Does "Intelligence" Require Trial-and-Error Machines?

• On the mathematical abilities of humans vs. machines, see:
  • Post, E.L. (1944). Recursively enumerable sets of positive integers. Bulletin of the American Mathematical Society, 5:284–316, esp. p. 295.

  • Wang 1957, p. 92.

  • Davis, M.D. (1990). Is mathematical insight algorithmic? Behavioral and Brain Sciences, 13(4):659–660.

    and

    Davis, M.D. (1993). How subtle is Gödel's theorem? More on Roger Penrose. Behavioral and Brain Sciences, 16(3):611.

    • Two essays by Davis that challenge Penrose's argument  — in:
      • Penrose, R. (1989). The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford University Press, Oxford

       — that Gödel's Theorem can be viewed as a kind of hypercomputation.

    • See also:
      • Copeland 2002b, §§1.18–1.18.1;
      • Dennett 1995, Ch. 15 (on Penrose)
      • Copeland and Shagrir 2013

• On Gödel, Turing, and mathematical ability, see:
  • Sieg, W. (2007). On mind & Turing's machines. Natural Computing, 6(2):187–205

  • Feferman, S. (2011). Gödel's incompleteness theorems, free will, and mathematical thought. In Swinburne, R., editor, Free Will and Modern Science. Oxford University Press/British Academy

  • Koellner, P. (2018). On the question of whether the mind can be mechanized, I: From Gödel to Penrose. Journal of Philosophy, 115(7):337–360.
    • An excellent summary of the issues.

• For more on Kugel's views, see:
  • Kugel, P. (1986). Thinking may be more than computing. Cognition, 22(2):137–198.

  • Kugel, P. (1986). When is a computer not a computer? Cognition, 23(1):89–94.

  • Kugel, P. (2004). Toward a theory of intelligence. Theoretical Computer Science, 317:13–30.

  • Kugel, P. (2005). It's time to think outside the computational box. Communications of the ACM, 48(11):33–37.
    • Wegner, P. and Goldin, D. (2006). Forum. Communications of the ACM, 49(3):11, is a response.

§11.10.3: Inductive Inference:

For more information on "computational learning theory" and "language learning in the limit", see:

• Gold 1967

• Hauser, M.D., Chomsky, N., and Fitch, W.T. (2002). The faculty of language: What is it, who has it, and how did it evolve. Science, 298:1569–1579.

• Nowak, M.A., Komarova, N.L., and Niyogi, P. (2002). Computational and evolutionary aspects of language. Nature, 417:611–617.

• Johnson, K. (2004). Gold's theorem and cognitive science. Philosophy of Science, 71:571–592.

• Bringsjord et al. 2018

• Scholz, Barbara C., Francis Jeffry Pelletier, Geoffrey K. Pullum, and Ryan Nefdt, "Philosophy of Linguistics", The Stanford Encyclopedia of Philosophy (Spring 2024 Edition), Edward N. Zalta & Uri Nodelman (eds.), esp. §4.2, "Language Learnability"