Philosophy of Computing and Information > Computation and Physical Systems > Noncomputable Processes
Edited by Corey J. Maley (University of Kansas)
|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.|
Using PhilPapers from home?
Create an account to enable off-campus access through your institution's proxy server.
Monitor this page
Be alerted of all new items appearing on this page. Choose how you want to monitor it:
David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers