# Noncomputable Processes

Edited by Corey Maley (University of Kansas)
Assistant editors: Giuseppe Primiero, Bert Baumgaertner
 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 2002 and Davis 1958.
Related categories
Siblings:

32 found
Order:
1. 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 (...)

Export citation

Bookmark
2. Explaining Experience In Nature: The Foundations Of Logic And Apprehension.Steven Ericsson-Zenith - forthcoming - 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

Export citation

Bookmark
3. White Hole Observation: An Experimental Result.Yang I. Pachankis - 2022 - International Journal of Innovative Science and Research Technology 7 (2):779-790.
The article presents the empirical confirmation to the black hole and white hole juxtapose theory. The author based the experiment on the multi- mission multi-spectral space telescope data conducted remotely with the NASA Data Challenge and Harvard- Smithsonian Micro-Observatory. Since the loss of the original manuscript, the author reformulated the mathematics during the research. The observation developed a resonance observation technique that observed the white hole to the moon’s direction with the sun. The data reduction of the white hole and (...)
Remove from this list   Direct download (2 more)

Export citation

Bookmark   3 citations
4. Reading the Cold War Through Outer Space: The Past and Future of Outer Space.Yang Immanuel Pachankis - 2022 - International Journal of Scientific and Engineering Research 13 (6):826-829.
The article takes a history based technical analysis on the governing activities by outer space laws. It outlined the spirit of the outer space law and treaty by the scientific development of the earth’s orbits & solar objects’ orbits. It focuses on the contamination of outer space by human activities in large scale structure with concluding scientific evidence. It analyzed geopolitical conflicts in terms of satellite technologies. They are analyzed based on the utility-science dichotomy, and the subject(s) that ultimately benefit (...)

Export citation

Bookmark
5. Equivalence of the Frame and Halting Problems.Eric Dietrich & Chris Fields - 2020 - Algorithms 13 (175):1-9.
The open-domain Frame Problem is the problem of determining what features of an open task environment need to be updated following an action. Here we prove that the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable. We discuss two other open-domain problems closely related to the Frame Problem, the system identification problem and the symbol-grounding problem, and show that they are similarly undecidable. We then reformulate the Frame Problem as a quantum decision problem, and show (...)

Export citation

Bookmark
6. 'Godel's Way'에서 세 명의 저명한 과학자들은 부정성, 불완전성, 임의성, 계산성 및 파라불일치와 같은 문제에 대해 논의합니다. 나는 완전히 다른 해결책을 가지고 두 가지 기본 문제가 있다는 비트 겐슈타인의 관점에서 이러한 문제에 접근. 과학적 또는 경험적 문제가 있다, 관찰 하 고 철학적 문제 언어를 어떻게 이해할 수 있는 (수학 및 논리에 특정 질문을 포함) 에 대 한 조사 해야 하는 세계에 대 한 사실,우리가 실제로 특정 컨텍스트에서 단어를 사용 하는 방법을 보고 하 여 결정 될 필요가. 우리가 어떤 언어 게임을 하고 (...)

Export citation

Bookmark
7. मैं कंप्यूटर के रूप में गणना और ब्रह्मांड की सीमा के कई हाल ही में चर्चा पढ़ लिया है, polymath भौतिक विज्ञानी और निर्णय सिद्धांतकार डेविड Wolpert के अद्भुत काम पर कुछ टिप्पणी खोजने की उम्मीद है, लेकिन एक भी प्रशस्ति पत्र नहीं मिला है और इसलिए मैं यह बहुत संक्षिप्त मौजूद सारांश. Wolpert कुछ आश्चर्यजनक असंभव या अधूरापन प्रमेयों साबित कर दिया (1992 से 2008-देखें arxiv dot org) अनुमान के लिए सीमा पर (कम्प्यूटेशन) कि इतने सामान्य वे गणना कर (...)

Export citation

Bookmark
8. 나는 컴퓨터로 계산과 우주의 한계에 대한 많은 최근의 토론을 읽었습니다, polymath 물리학자 및 결정 이론가 데이비드 울퍼트의 놀라운 작품에 대한 몇 가지 의견을 찾을 수 있기를 바라고 있지만 하나의 인용을 발견하지 않은 그래서 나는이 매우 간단한 요약을 제시. Wolpert는 계산을 수행하는 장치와 는 별개이며 물리학법칙과는 무관하므로 컴퓨터, 물리학 및 인간의 행동에 적용되므로 추론(계산)에 대한 제한에 대해 놀라운 불가능또는 불완전성 정리(1992년에서 2008년 참조 arxiv dot org)를 입증했습니다. 그들은 캔터의 대각선화, 거짓말쟁이 역설 및 세계관을 사용하여 튜링 머신 이론의 궁극적 인 정리가 될 (...)

Export citation

Bookmark
9. He leído muchas discusiones recientes sobre los límites de la computación y el universo como computadora, con la esperanza de encontrar algunos comentarios sobre el increíble trabajo del físico polimatemático y teórico de la decisión David Wolpert pero no han encontrado una sola citación y así que presento esta muy breve Resumen. Wolpert demostró algunos teoremas sorprendentes de imposibilidad o incompletos (1992 a 2008-ver arxiv dot org) en los límites de la inferencia (computación) que son tan generales que son independientes (...)

Export citation

Bookmark
10. Doy una revisión detallada de ' los límites externos de la razón ' por Noson Yanofsky desde una perspectiva unificada de Wittgenstein y la psicología evolutiva. Yo indiqué que la dificultad con cuestiones como la paradoja en el lenguaje y las matemáticas, la incompletitud, la indeterminación, la computabilidad, el cerebro y el universo como ordenadores, etc., surgen de la falta de mirada cuidadosa a nuestro uso del lenguaje en el adecuado contexto y, por tanto, el Error al separar los problemas (...)

Export citation

Bookmark
11. Physical Perspectives on Computation, Computational Perspectives on Physics.Michael E. Cuffaro & Samuel C. Fletcher (eds.) - 2018 - Cambridge University Press.
Although computation and the science of physical systems would appear to be unrelated, there are a number of ways in which computational and physical concepts can be brought together in ways that illuminate both. This volume examines fundamental questions which connect scholars from both disciplines: is the universe a computer? Can a universal computing machine simulate every physical process? What is the source of the computational power of quantum computers? Are computational approaches to solving physical problems and paradoxes always fruitful? (...)
Remove from this list   Direct download (2 more)

Export citation

Bookmark   6 citations
12. Rational Analysis, Intractability, and the Prospects of ‘as If’-Explanations.Iris van Rooij, Cory D. Wright, Johan Kwisthout & Todd Wareham - 2018 - Synthese 195 (2):491-510.
Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...)
Remove from this list   Direct download (3 more)

Export citation

Bookmark   5 citations
13. Wittgenstein, Turing, and the "Finitude" of Language.Paul Livingston - 2010 - Linguistic and Philosophical Investigations 9:215-47.
Remove from this list   Direct download (2 more)

Export citation

Bookmark
14. Computation in Physical Systems.Gualtiero Piccinini - 2010 - Stanford Encyclopedia of Philosophy.

Export citation

Bookmark   43 citations
15. Computing the Uncomputable; or, The Discrete Charm of Second-Order Simulacra.Matthew W. Parker - 2009 - 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 validation, (...)
Remove from this list   Direct download (9 more)

Export citation

Bookmark   2 citations
16. Physical Computation: How General Are Gandy’s Principles for Mechanisms?B. Jack Copeland & Oron Shagrir - 2007 - 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 (13 more)

Export citation

Bookmark   11 citations
17. Quantum Hypercomputation—Hype or Computation?Amit Hagar & Alex Korolev - 2007 - 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 (10 more)

Export citation

Bookmark   9 citations
18. Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - 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)

Export citation

Bookmark   19 citations
19. Quantum Hypercomputability?Amit Hagar & Alexandre Korolev - 2006 - 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 (11 more)

Export citation

Bookmark   5 citations
20. Three Concepts of Decidability for General Subsets of Uncountable Spaces.Matthew W. Parker - 2003 - 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   Direct download (2 more)

Export citation

Bookmark   3 citations
21. Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System.Matthew W. Parker - 2003 - 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 (11 more)

Export citation

Bookmark   3 citations
22. Supermachines and Superminds.Eric Steinhart - 2003 - 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 (11 more)

Export citation

Bookmark   3 citations
23. On Effective Procedures.Carol E. Cleland - 2002 - 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 (14 more)

Export citation

Bookmark   14 citations
24. Accelerating Turing Machines.B. Jack Copeland - 2002 - 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 (14 more)

Export citation

Bookmark   23 citations
25. 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.
Remove from this list   Direct download (14 more)

Export citation

Bookmark   50 citations
26. Proving Church's Thesis.Robert Black - 2000 - 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 (8 more)

Export citation

Bookmark   11 citations
27. Beyond the Universal Turing Machine.Jack Copeland - 1999 - 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 (6 more)

Export citation

Bookmark   18 citations
28. Super Turing-Machines.Jack Copeland - 1998 - 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 (2 more)

Export citation

Bookmark   12 citations
29. Strong Determinism Vs. Computability.Cristian Calude, Douglas Campbell, Karl Svozil & Doru Ştefănescu - 1995 - 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

Bookmark   1 citation
30. Computation, Among Other Things, is Beneath Us.Selmer Bringsjord - 1994 - 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 (4 more)

Export citation

Bookmark   9 citations
31. Artificial Intelligence: The Case Against.Rainer Born (ed.) - 1987 - St Martin's Press.
The purpose of this book, originally published in 1987, was to contribute to the advance of artificial intelligence by clarifying and removing the major sources of philosophical confusion at the time which continued to preoccupy scientists and thereby impede research. Unlike the vast majority of philosophical critiques of AI, however, each of the authors in this volume has made a serious attempt to come to terms with the scientific theories that have been developed, rather than attacking superficial 'straw men' which (...)