What Is Hypercomputation?

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.
   • Excerpts from the program, plus abstracts of some of the talks.

Articles

1. Wegner, Peter (1997), "Why Interaction Is More Powerful than Algorithms", Communications of the ACM 40(5) (May): 80-91.
   • Many of Wegner's papers are online in various formats at his homepage (click on his name).

   • Wegner is a proponent of "interactive computing".
     There is also something called "reactive systems", which may be the same thing, but neither body of literature seems to cite the other.
     Their relationships may be worth exploring.

   • A 1994 email exchange with Wegner on the subject of interactive computing, message passing, and AI actors, with numerous references.

   • Follow-up papers by Wegner:
     1. Wegner, Peter (1999), "Towards Empirical Computer Science", The Monist 82(1) (January): 58-108.

     2. Eberbach, Eugene; & Wegner, Peter (2003), "Beyond Turing Machines", Bulletin of the European Association for Theoretical Computer Science (EATCS) No. 81 (October): 279-304. [PDF]
        • This is best compared to Copeland 2002 as being a good survey, with good references.

     3. Wegner, Peter & Goldin, Dina (2003), "Computation beyond Turing Machines", Communications of the ACM 46(4) (April): 100-102.

     4. Wegner, Peter; & Goldin, Dina (2006), "Principles of Problem Solving", Communications of the ACM 49(7): 27-29.

     5. Goldin, Dina; & Wegner, Peter (2008), "The Interactive Nature of Computing: Refuting the Strong Church-Turing Thesis", Minds and Machines 18(1; Spring): 17-38.

2. Copeland, B. Jack, & Proudfoot, Diane (1999), "Alan Turing's Forgotten Ideas in Computer Science", Scientific American (April): 98-103.
   • For a reply, see:
     Hodges, Andrew, "The Professors and the Brainstorms"

   • Follow-up items by, or edited by, Copeland:
     1. Copeland, B. Jack (2002), "Accelerating Turing Machines", Minds and Machines 12(2) (May): 303-326.

     2. Copeland, B. Jack (guest ed.) (2002), Special Issue on Hypercomputation, Minds and Machines 12(4) (November).
        • Click on title for full table of contents.
        • Contains the following two, very interesting papers:
          1. Copeland, B. Jack (2002), "Hypercomputation", pp. 461-502. [PDF]
             • A good overview and survey.

          2. Kugel, Peter (2002), "Computing Machines Can't Be Intelligent (…and Turing Said So)", pp. 563-579. [PDF]
             • This paper has almost convinced me that there just might be something to all of this "hype" about "hypercomputation".
               • For related papers, see:
                 1. Kugel, Peter (1986), "Thinking May Be More than Computing", Cognition 22(2) (March): 137–198.

                 2. Kugel, Peter (1986), "When Is a Computer Not a Computer?", Cognition 23(1) (June): 89–94.

                 3. Kugel, Peter (2004), "Toward a Theory of Intelligence", Theoretical Computer Science 317: 13-30.

             • For more information on the application of Putnam-Gold machines to "computational learning theory", see:
               1. John Case's COLT Page

               2. Nowak, Martin A.; Komarova, Natalia L.; & Niyogi, Partha (2002), "Computational and Evolutionary Aspects of Language", Nature 417 (6 June): 611-617.

             • On Putnam-Gold machines, see also:
               • Gold, E. Mark (1967), "Language Identification in the Limit", Information and Control 10: 447-474.

               • 
                 Hintikka, Jaakko; & Mutanen, Arto (1997), "An Alternative Concept of Computability", in Jaakko Hintikka (ed.), Language, Truth, and Logic in Mathematics (Dordrecht, The Netherlands: Springer): 174–188.

               • Johnson, Kent (2004), "Gold's Theorem and Cognitive Science", Philosophy of Science 71 (October): 571-592.

     3. Copeland, B. Jack (guest ed.) (2003), Special Issue on Hypercomputation (continued), Minds and Machines 13(1) (February).
        • Click on title for full table of contents.

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.
    Also see:
    • Does a function in mathematics change anything?

12. "How Real Are Real Numbers?", International Journal of Bifurcation and Chaos
    • Also see:
      Chaitin, Gregory (2006), "The Limits of Reason", Scientific American (March): 74-81.

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.
    • This is the first paper I've read on the subject that clarified what the issue is, namely, is there a difference between Turing's mathematical model of human computability and a possibly more extensive notion of physical computability?

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