# Noncomputable Processes

Edited by Corey J. Maley (University of Kansas)
Assistant editors: Bert Baumgaertner, Giuseppe Primiero
 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:
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.

Export citation

My bibliography   5 citations
2. Rainer P. Born (ed.) (1987). Artificial Intelligence: The Case Against. St Martin's Press.
Remove from this list

Export citation

My bibliography
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 (...)

Export citation

My bibliography   1 citation
4. Cristian Calude, Douglas Campbell, Karl Svozil & Doru Ştefănescu (1995). Strong Determinism Vs. Computability. Vienna Circle Institute Yearbook 3:115-131.
Penrose [40] has discussed a new point of view concerning the nature of physics that might underline conscious thought processes. He has argued that it might be the case that some physical laws are not computable, i.e. they cannot be properly simulated by computer; such laws can most probably arise on the “no-man’s-land” between classical and quantum physics. Furthermore, conscious thinking is a non-algorithmic activity. He is opposing both strong AI , and Searle’s [47] contrary viewpoint mathematical “laws”).

Export citation

My bibliography   1 citation
5. 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 (...)

Export citation

My bibliography   4 citations
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.

Export citation

My bibliography   23 citations
7. 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 (...)

Export citation

My bibliography   9 citations
8. B. Jack Copeland & Oron Shagrir (2007). Physical Computation: How General Are Gandy's Principles for Mechanisms? 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 (...)

Export citation

My bibliography   5 citations
9. 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

Export citation

My bibliography   2 citations
10. 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.

Export citation

My bibliography   6 citations
11. 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 (...)

Export citation

My bibliography   4 citations
12. Steven Ericsson-Zenith (forthcoming). Explaining Experience In Nature: The Foundations Of Logic And Apprehension. Institute for Advanced Science & Engineering.
At its core this book is concerned with logic and computation with respect to the mathematical characterization of sentient biophysical structure and its behavior. -/- Three related theories are presented: The first of these provides an explanation of how sentient individuals come to be in the world. The second describes how these individuals operate. And the third proposes a method for reasoning about the behavior of individuals in groups. -/- These theories are based upon a new explanation of experience in (...)
Remove from this list
Translate

Export citation

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

Export citation

My bibliography   1 citation
14. 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.

Export citation

My bibliography   3 citations
15. Paul Livingston (2010). Wittgenstein, Turing, and the "Finitude" of Language. Linguistic and Philosophical Investigations 9:215-47.

Export citation

My bibliography
16. W. Matthew (2006). Parker. Theoretical Computer Science 351 (1):2-13.
There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...)
Remove from this list
Translate

Export citation

My bibliography
17. 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 (...)

Export citation

My bibliography
18. 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 (...)

Export citation

My bibliography   2 citations
19. Gualtiero Piccinini (2010). Computation in Physical Systems. Stanford Encyclopedia of Philosophy.
Remove from this list
Translate

Export citation

My bibliography   4 citations
20. 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 (...)

Export citation

My bibliography   3 citations
21. I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...)