Philosophy of Computer Science

What Is Hypercomputation?

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

Last Update: 14 May 2012

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 (2004), "The Myth of Hypercomputation", in C. Teuscher (ed.), Alan Turing: The Life and Legacy of a Great Thinker (Berlin: Springer): 195–212. [PDF]

  10. Davis, Martin (2006), "Why There Is No Such Discipline as Hypercomputation", Applied Mathematics and Computation 178: 4–7. [PDF]

  11. Cleland, Carol E. (2004), "The Concept of Computability", Theoretical Computer Science 317: 209-225.

  12. "How Real Are Real Numbers?", International Journal of Bifurcation and Chaos

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

  14. On quantum computers:

    1. Aaronson, Scott (2008), "The Limits of Quantum Computers", Scientific American (March): 62-69.

      • "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."

    2. Monroe, Christopher R.; & Wineland, David J. (2008), "Quantum Computing with Ions", Scientific American (August): 64-71.

    3. Bacon, Dave; & van Dam, Wim (2010), "Recent Progress in Quantum Algorithms", Communications of the ACM 53(2) (February): 84–93.

  15. Dresner, Eli (2008), "Turing-, Human- and Physical Computability: An Unasked Question", Minds and Machines 18(3) (Fall): 349-355.

  16. Button, Tim (2009), "SAD Computers and Two Versions of the Church-Turing Thesis", British Journal for the Philosophy of Science 60: 765–792.



Copyright © 2004–2012 by William J. Rapaport (rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/584/hypercompn.html-20120514