Switch to: Citations

Add references

You must login to add references.
  1. Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
    A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...)
    Download  
     
    Export citation  
     
    Bookmark   20 citations  
  • On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
    Download  
     
    Export citation  
     
    Bookmark   717 citations  
  • (3 other versions)Infinite time Turing machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
    Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.
    Download  
     
    Export citation  
     
    Bookmark   19 citations  
  • Hypercomputation.B. Jack Copeland - 2002 - Minds and Machines 12 (4):461-502.
    A survey of the field of hypercomputation, including discussion of a variety of objections.
    Download  
     
    Export citation  
     
    Bookmark   53 citations  
  • (1 other version)Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
    Download  
     
    Export citation  
     
    Bookmark   70 citations  
  • (3 other versions)Infinite time Turing machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
    We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.
    Download  
     
    Export citation  
     
    Bookmark   52 citations  
  • (2 other versions)Algorithmic Information Theory.Peter Gacs - 1989 - Journal of Symbolic Logic 54 (2):624-627.
    Download  
     
    Export citation  
     
    Bookmark   60 citations  
  • Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
    Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from small (...)
    Download  
     
    Export citation  
     
    Bookmark   72 citations  
  • Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
    Download  
     
    Export citation  
     
    Bookmark   595 citations  
  • Hypercomputation: Computing more than the Turing machine.Toby Ord - 2002 - Dissertation, University of Melbourne
    In this report I provide an introduction to the burgeoning field of hypercomputation – the study of machines that can compute more than Turing machines. I take an extensive survey of many of the key concepts in the field, tying together the disparate ideas and presenting them in a structure which allows comparisons of the many approaches and results. To this I add several new results and draw out some interesting consequences of hypercomputation for several different disciplines.
    Download  
     
    Export citation  
     
    Bookmark   8 citations