About this topic
Summary In computability theory the class of functions that are computable corresponds to the class of recursive ones. This was proven by Church's lambda-calculus by formulating the former as lambda terms. Turing proved that this class also coincides with the class of functions that are mechanically computable. These results are usually combined in the so-called Church-Turing Thesis: every effectively calculable function is a computable function. This statement remains a thesis (and it thus not a theorem) because there is no formal evidence that non-computable processes are besides the limits of (mechanical or formal) calculability. Nonetheless, it is usually considered true on account of the large amount of evidence in its favour. This immediately defines the class of non-computable function as those that are non-recursively definable and the class of non-solvable problems by means of recursive procedures. Among the most common examples of non-computable function is the busy-beaver function (also known as the productivity function): consider the function executed by a Turing machine that starts on a blank tape and when it halts after scanning a block of strokes, the length of that block is said to be its productivity; but if it does not halt, then its productivity is 0; then the busy-beaver function p(n) is the productivity of the most productive Turing machine of a given class, i.e. with at most n states. Such function corresponds to the Halting Function, based on the idea that all Turing machines can be enumerated and a general procedure can be defined to establish for any given machine and any given input whether that machine with that input halts or does not. This moreover coincides with the Decision Problem for First Order Logic: given a finite set of sentences S, for any given sentence D, establish whether S implies D (in FOL). From a philosophical viewpoint, the uncomputable has generated an enormous amount of work, for example concerning the physical non-computability of non-recursive function (on the assumption that the universe behaves as a Turing Machine); or concerning the limits of Turing-computable mental states. The thesis that it does exist a class of computable functions beyond Turing computability is usually referred to as 'hypercomputability', or 'super-Turing computability' and the supposed corresponding class of algorithms is known as 'super-recursive'. 
Key works For the original works on the definition of computable functions see Church 1936, Turing 1936 and the collection in Davis 1965. For an overview of the field of hypercomputation see Copeland 2002; for a critique see Davis 2006. In Penrose 1999 the thesis is held that the mind is the result of a non-algorithmically computable process. 
Introductions For a general introduction to computable functions and their limits see Boolos et al 2007 and Davis 1958
  Show all references
Related categories
Siblings:
18 found
Search inside:
(import / add options)   Sort by:
  1. Robert Black (2000). Proving Church's Thesis. Philosophia Mathematica 8 (3):244--58.
    Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Rainer P. Born (ed.) (1987). Artificial Intelligence: The Case Against. St Martin's Press.
  3. Selmer Bringsjord (1994). Computation, Among Other Things, is Beneath Us. Minds and Machines 4 (4):469-88.
    What''s computation? The received answer is that computation is a computer at work, and a computer at work is that which can be modelled as a Turing machine at work. Unfortunately, as John Searle has recently argued, and as others have agreed, the received answer appears to imply that AI and Cog Sci are a royal waste of time. The argument here is alarmingly simple: AI and Cog Sci (of the Strong sort, anyway) are committed to the view that cognition (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. Carol E. Cleland (2002). On Effective Procedures. Minds and Machines 12 (2):159-179.
    Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...)
    Remove from this list | Direct download (17 more)  
     
    My bibliography  
     
    Export citation  
  5. B. Jack Copeland (2002). Accelerating Turing Machines. Minds and Machines 12 (2):281-300.
    Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...)
    Remove from this list | Direct download (17 more)  
     
    My bibliography  
     
    Export citation  
  6. B. Jack Copeland (2002). Hypercomputation. Minds and Machines 12 (4):461-502.
    A survey of the field of hypercomputation, including discussion of a variety of objections.
    Remove from this list | Direct download (16 more)  
     
    My bibliography  
     
    Export citation  
  7. B. Jack Copeland & Oron Shagrir (2007). Physical Computation: How General Are Gandy's Principles for Mechanisms? [REVIEW] Minds and Machines 17 (2):217-231.
    What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...)
    Remove from this list | Direct download (15 more)  
     
    My bibliography  
     
    Export citation  
  8. Jack Copeland, Even Turing Machines Can Compute Uncomputable Functions.
    Accelerated Turing machines are Turing machines that perform tasks commonly regarded as impossible, such as computing the halting function. The existence of these notional machines has obvious implications concerning the theoretical limits of computability.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  9. Jack Copeland (1999). Beyond the Universal Turing Machine. Australasian Journal of Philosophy 77 (1):46-67.
    We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.
    Remove from this list | Direct download (12 more)  
     
    My bibliography  
     
    Export citation  
  10. Jack Copeland (1998). Super Turing-Machines. Complexity 4 (1):30-32.
    The tape is divided into squares, each square bearing a single symbol—'0' or '1', for example. This tape is the machine's general-purpose storage medium: the machine is set in motion with its input inscribed on the tape, output is written onto the tape by the head, and the tape serves as a short-term working memory for the results of intermediate steps of the computation. The program governing the particular computation that the machine is to perform is also stored on the (...)
    Remove from this list | Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  11. Amit Hagar & Alex Korolev (2007). Quantum Hypercomputation—Hype or Computation? Philosophy of Science 74 (3):347-363.
    A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  12. Amit Hagar & Alexandre Korolev (2006). Quantum Hypercomputability? Minds and Machines 16 (1):87-93.
    A recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.
    Remove from this list | Direct download (13 more)  
     
    My bibliography  
     
    Export citation  
  13. Paul Livingston (2010). Wittgenstein, Turing, and the "Finitude" of Language. Linguistic and Philosophical Investigations 9:215-47.
  14. Matthew W. Parker (2009). Computing the Uncomputable; or, the Discrete Charm of Second-Order Simulacra. Synthese 169 (3):447 - 463.
    We examine a case in which non-computable behavior in a model is revealed by computer simulation. This is possible due to differing notions of computability for sets in a continuous space. The argument originally given for the validity of the simulation involves a simpler simulation of the simulation , still further simulations thereof, and a universality conjecture. There are difficulties with that argument, but there are other, heuristic arguments supporting the qualitative results. It is urged, using this example, that absolute (...)
    Remove from this list | Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  15. Matthew W. Parker (2003). Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System. Philosophy of Science 70 (2):359-382.
    Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...)
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Gualtiero Piccinini, Computation in Physical Systems. Stanford Encyclopedia of Philosophy.
  17. Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
    Church's thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive. A related thesis asserts that Turing's work yields a conceptual analysis of the intuitive notion of numerical computability. I endorse Church's thesis, but I argue against the related thesis. I argue that purported conceptual analyses based upon Turing's work involve a subtle but persistent circularity. Turing machines manipulate syntactic entities. To specify which number-theoretic function a Turing machine computes, we must correlate these syntactic (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  18. Eric Steinhart (2003). Supermachines and Superminds. Minds and Machines 13 (1):155-186.
    If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...)
    Remove from this list | Direct download (12 more)  
     
    My bibliography  
     
    Export citation