Philosophy of Computer Science

What Is Hypercomputation?

(Boldface items are particularly useful, important, or interesting.)

Last Update: 25 March 2007, 9:33 p.m.

Note: NEW or UPDATED material is highlighted


Bibliographies

  1. Burgin, Mark, & Wegner, Peter (organizers) (2003), Special Sessions on Beyond Classical Boundaries of Computability [PDF] (Parts I,II,III, & IV),2003 Spring Western Section Meeting, American Mathematical Society.


Articles

  1. Wegner, Peter (1997), "Why Interaction Is More Powerful than Algorithms", Communications of the ACM 40(5) (May): 80-91.

  2. Copeland, B. Jack, & Proudfoot, Diane (1999), "Alan Turing's Forgotten Ideas in Computer Science", Scientific American (April): 98-103.

  3. Milner, Robin (1993), "Elements of Interaction", Communications of the ACM 36(1) (January): 78-89.

  4. Schächter, Vincent (1999), "How Does Concurrency Extend the Paradigm of Computation?", The Monist 82(1) (January): 37-57.

  5. Davies, E.B. (2001), "Building Infinite Machines", British Journal for the Philosophy of Science 52: 671-682.

  6. Bringsjord, Selmer, & Zenzen, Michael (2002), "Toward a Formal Philosophy of Hypercomputation", Minds and Machines 12(2) (May): 259-280.

  7. Steinhart, Eric (2002), "Logically Possible Machines", Minds and Machines 12(2) (May): 281-301.

  8. Cotogno, P. (2003), "Hypercomputation and the Physical Church-Turing Thesis", British Journal for the Philosophy of Science 54(2): 181-224.

  9. Davis, Martin (200x), "The Myth of Hypercomputation".

  10. NEW
    Chaitin, Gregory (2004-2005),
    "How Real Are Real Numbers?".

  11. NEW
    Hypocomputation: If "hyper"computation is computing that is "above" the Turing "speed limit", so to speak, then "hypo"computation is computing "below" it.

    1. Lindell, Steven (2004), "Revisiting Finite-Visit Computations" [PDF slide show]

      • Abstract: Incorporating matter and energy requirements into physically implemented machines sheds new light on feasible computability. Under certain circumstances, conventional mathematical models may not be asymptotically realizable due to the limited availability of resources required to store data and execute instructions.

    2. NEW
      Lindell, Steven (2006),
      "A Physical Analysis of Mechanical Computability" [PDF slide show]

      • Abstract: Turing's model of autonomous computation is based on the idealized psychological characteristics of a human calculator—its ability to change its "state of mind" in a stepwise fashion based on the recognition of symbolic configurations. This leads to a mathematical model of effective computability, with its well known capabilities and limitations. We extend this analysis to the idealized physiological characteristics of a machine computer—its ability to manipulate matter using energy. This leads to a new notion of feasibility based on physical resource bounds, in which mass and energy constraints further restrict the usual notions of space and time complexity.



Copyright © 2004-2007 by William J. Rapaport (rapaport@cse.buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/584/S07/whatishypercomputation.html-20070325