Noncomputable Processes

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 (...) independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility,incompleteness, the limits of computation,and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things,a non-quantum mechanical uncertainty principle and a proof of monotheism. (shrink)

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 (...) nature, the construction of senses, and motile behavior. This new approach is developed from first principles to enable a rigorous and systematic explanation of the variety of associated intelligent behaviors. -/- Alongside this development is a further account that focuses upon the nature of our work. It discusses the existential aspects of scientific inquiry, its epistemology and logic. It seeks to clarify the nature of the mathematical characterization and computation of natural behaviors, dealing with questions in the foundations of logic. It explores methodological issues related to reduction and the refinement of ideas from intuition to formal logical structure. -/- In support of this inquiry we work toward the development of a calculus for biophysical construction and its dynamics. If successful this mechanics mathematically characterizes sensory and motile behavior. -/- Upon this foundation we propose a model of apprehension and explore how its products are processed by the organism. Finally, we develop a probabilistic theory that enables us to reason about inaccessible factors in group behavior. -/- The mechanics we propose suggests the design and physical realization of a new model of computation; one in which structure and the concurrency of action are a first-order consideration. -/- We identify opportunities for experimental verification of the theory and we suggest a proof of our results in practice by the identification of this mechanism, allowing the construction of machines that experience. (shrink)

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 (...) that it is undecidable by any finite quantum computer. (shrink)

나는 컴퓨터로 계산과 우주의 한계에 대한 많은 최근의 토론을 읽었습니다, polymath 물리학자 및 결정 이론가 데이비드 울퍼트의 놀라운 작품에 대한 몇 가지 의견을 찾을 수 있기를 바라고 있지만 하나의 인용을 발견하지 않은 그래서 나는이 매우 간단한 요약을 제시. Wolpert는 계산을 수행하는 장치와 는 별개이며 물리학법칙과는 무관하므로 컴퓨터, 물리학 및 인간의 행동에 적용되므로 추론(계산)에 대한 제한에 대해 놀라운 불가능또는 불완전성 정리(1992년에서 2008년 참조 arxiv dot org)를 입증했습니다. 그들은 캔터의 대각선화, 거짓말쟁이 역설 및 세계관을 사용하여 튜링 머신 이론의 궁극적 인 정리가 될 (...) 수있는 것을 제공하고, 겉보기에 불가능, 불완전성, 계산의 한계, 그리고 컴퓨터로서의 우주, 가능한 모든 우주와 모든 존재 또는 메커니즘에서, 생성, 비 양자 기계적 불확실성 및 증거. 차이틴, 솔로모노프, 코몰가로프, 비트겐슈타인의 고전 적 작품과 어떤 프로그램 (따라서 어떤 장치)이 소유보다 더 큰 복잡성시퀀스 (또는 장치)를 생성 할 수 없다는 개념에 명백한 연결이 있습니다. 이 작품의 몸은 물리적 우주보다 더 복잡한 어떤 실체가 있을 수 없고 비트겐슈타인의 관점에서 볼 때 '더 복잡한'은 의미가 없다고 말할 수 있습니다(즉, 진리를 제작자나 시험하는 조건은 없습니다). 심지어 '신'(즉, 무한한 시간과 에너지를 가진 '장치')은 주어진 '숫자'가 '무작위'인지 여부를 결정할 수없으며, 주어진 '수식', '정리' 또는 '문장' 또는 '장치'(이 모든 것이 복잡한 언어 게임)가 특정 '시스템'의 일부임을 보여줄 수 있는 특정 방법을 찾을 수 없습니다. 현대 의 두 systems보기에서인간의 행동에 대한 포괄적 인 최신 프레임 워크를 원하는 사람들은 내 책을 참조 할 수 있습니다'철학의 논리적 구조, 심리학, 민d와 루드비히 비트겐슈타인과 존 Searle의언어' 2nd ed (2019). 내 글의 더 많은 관심있는 사람들은 '이야기 원숭이를 볼 수 있습니다-철학, 심리학, 과학, 종교와 운명 행성에 정치 - 기사 및 리뷰 2006-2019 2nd 에드 (2019) 및 21st 세기 4번째 에드 (2019) 및 기타. (shrink)

'Godel's Way'에서 세 명의 저명한 과학자들은 부정성, 불완전성, 임의성, 계산성 및 파라불일치와 같은 문제에 대해 논의합니다. 나는 완전히 다른 해결책을 가지고 두 가지 기본 문제가 있다는 비트 겐슈타인의 관점에서 이러한 문제에 접근. 과학적 또는 경험적 문제가 있다, 관찰 하 고 철학적 문제 언어를 어떻게 이해할 수 있는 (수학 및 논리에 특정 질문을 포함) 에 대 한 조사 해야 하는 세계에 대 한 사실,우리가 실제로 특정 컨텍스트에서 단어를 사용 하는 방법을 보고 하 여 결정 될 필요가. 우리가 어떤 언어 게임을 하고 (...) 있는지 명확히 알 면, 이 주제는 다른 언어와 마찬가지로 평범한 과학적이고 수학적 질문으로 보입니다. 비트겐슈타인의 통찰력은 거의 동등하지 않았고 결코 능가하지 않았으며, 그가 블루와 브라운 북을 지시했을 때 80 년 전과 마찬가지로 오늘날과 관련이 있습니다. 완성된 책이 아닌 일련의 노트가 실패했음에도 불구하고, 이것은 반세기 이상 물리학, 수학, 철학의 출혈 가장자리에서 일해온 이 세 명의 유명한 학자들의 작품의 독특한 원천입니다. 다 코스타와 도리아는 울퍼트에 의해 인용된다 (그들은 보편적 인 계산에 쓴 이후 울퍼트와 야노프스키의 '이성의 외부 한계'에 대한 내 리뷰에, 대한 내 리뷰) 그리고 그의 많은 업적 중, 다 코스타는 파라 불일치의 선구자입니다. 현대 의 두 systems보기에서인간의 행동에 대한 포괄적 인 최신 프레임 워크를 원하는 사람들은 내 책을 참조 할 수 있습니다'철학의 논리적 구조, 심리학, 민d와 루드비히 비트겐슈타인과 존 Searle의언어' 2nd ed (2019). 내 글의 더 많은 관심있는 사람들은 '이야기 원숭이를 볼 수 있습니다-철학, 심리학, 과학, 종교와 운명 행성에 정치 - 기사 및 리뷰 2006-2019 3 rd 에드 (2019) 및 21st 세기 4번째 에드 (2019) 및 기타에서 자살 유토피아 망상. (shrink)

मैं कंप्यूटर के रूप में गणना और ब्रह्मांड की सीमा के कई हाल ही में चर्चा पढ़ लिया है, polymath भौतिक विज्ञानी और निर्णय सिद्धांतकार डेविड Wolpert के अद्भुत काम पर कुछ टिप्पणी खोजने की उम्मीद है, लेकिन एक भी प्रशस्ति पत्र नहीं मिला है और इसलिए मैं यह बहुत संक्षिप्त मौजूद सारांश. Wolpert कुछ आश्चर्यजनक असंभव या अधूरापन प्रमेयों साबित कर दिया (1992 से 2008-देखें arxiv dot org) अनुमान के लिए सीमा पर (कम्प्यूटेशन) कि इतने सामान्य वे गणना कर (...) डिवाइस से स्वतंत्र हैं, और यहां तक कि भौतिकी के नियमों से स्वतंत्र, इसलिए वे कंप्यूटर, भौतिक विज्ञान और मानव व्यवहार में लागू होते हैं. वे कैंटर विकर्णीकरण का उपयोग करते हैं, झूठा विरोधाभास और worldlines प्रदान करने के लिए क्या ट्यूरिंग मशीन थ्योरी में अंतिम प्रमेय हो सकता है, और प्रतीत होता है असंभव, अधूरापन, गणना की सीमा में अंतर्दृष्टि प्रदान करते हैं, और ब्रह्मांड के रूप में कंप्यूटर, सभी संभव ब्रह्मांडों और सभी प्राणियों या तंत्र में, उत्पादन, अन्य बातों के अलावा, एक गैर क्वांटम यांत्रिक अनिश्चितता सिद्धांत और एकेश्वरवाद का सबूत. वहाँ Chaitin, Solomonoff, Komolgarov और Wittgenstein के क्लासिक काम करने के लिए स्पष्ट कनेक्शन कर रहे हैं और धारणा है कि कोई कार्यक्रम (और इस तरह कोई डिवाइस) एक दृश्य उत्पन्न कर सकते हैं (या डिवाइस) अधिक से अधिक जटिलता के साथ यह पास से. कोई कह सकता है कि काम के इस शरीर का अर्थ नास्तिकता है क्योंकि भौतिक ब्रह्मांड से और विटगेनस्टीनियन दृष्टिकोण से कोई भी इकाई अधिक जटिल नहीं हो सकती है, 'अधिक जटिल' अर्थहीन है (संतोष की कोई शर्त नहीं है, अर्थात, सत्य-निर्माता या परीक्षण)। यहां तक कि एक 'भगवान' (यानी, असीम समय/स्थान और ऊर्जा के साथ एक 'डिवाइस' निर्धारित नहीं कर सकता है कि क्या एक दिया 'संख्या' 'यादृच्छिक' है, और न ही एक निश्चित तरीका है दिखाने के लिए कि एक दिया 'सूत्र', 'प्रमेय' या 'वाक्य' या 'डिवाइस' (इन सभी जटिल भाषा जा रहा है) खेल) एक विशेष 'प्रणाली' का हिस्सा है. आधुनिक दो systems दृश्यसे मानव व्यवहार के लिए एक व्यापक अप करने के लिए तारीख रूपरेखा इच्छुक लोगों को मेरी पुस्तक 'दर्शन, मनोविज्ञान, मिनडी और लुडविगमें भाषा की तार्किक संरचना से परामर्श कर सकते हैं Wittgenstein और जॉन Searle '2 एड (2019). मेरे लेखन के अधिक में रुचि रखने वालों को देख सकते हैं 'बात कर रहेबंदर- दर्शन, मनोविज्ञान, विज्ञान, धर्म और राजनीति पर एक बर्बाद ग्रह --लेख और समीक्षा 2006-2019 2 ed (2019) और आत्मघाती यूटोपियान भ्रम 21st मेंसदी 4वें एड (2019) . (shrink)

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 (...) del dispositivo que hace el cómputo, e incluso independiente de las leyes de la física, por lo que se aplican a través de computadoras, física y comportamiento humano. Hacen uso de la Diagonalización de cantor, la paradoja mentirosa y las líneas del mundo para proporcionar lo que puede ser el teorema definitivo en la teoría de la máquina de Turing, y aparentemente proporcionan información sobre la imposibilidad, la incompleta, los límites de la computación, y el universo como computadora, en todos los universos posibles y todos los seres o mecanismos, generando, entre otras cosas, un principio de incertidumbre mecánica no cuántica y una prueba de monoteísmo. Hay conexiones obvias al trabajo clásico de Chaitin, Solomonoff, Komolgarov y Wittgenstein y a la noción de que ningún programa (y por lo tanto ningún dispositivo) puede generar una secuencia (o dispositivo) con mayor complejidad de la que posee. Uno podría decir que este cuerpo de trabajo implica el ateísmo, ya que no puede haber ninguna entidad más compleja que el universo físico y desde el punto de vista de Wittgensteinian, ' más complejo ' carece de sentido (no tiene condiciones de satisfacción, es decir, creador de la verdad o prueba). Incluso un ' Dios ' (es decir, un ' device' con tiempo/espacio ilimitado y energía) no puede determinar si un ' número ' dado es ' aleatorio ', ni encontrar una cierta manera de demostrar que una determinada "fórmula", "teorema" o "frase" o "dispositivo" (todos estos son juegos de lenguaje complejos) es parte de un "sistema" en particular. Aquellos que deseen un marco completo hasta la fecha para el comportamiento humano de la moderna Dos Sistemas Punto de Vista puede consultar mi libro 'La estructura lógica de la filosofía, la psicología, la mente y lenguaje En Ludwig Wittgenstein y John Searle ' 2Nd Ed (2019). Los interesados en más de mis escritos pueden ver 'Monos parlantes--filosofía, psicología, ciencia, religión y política en un planeta condenado--artículos y reseñas 2006-2017' 3Rd Ed (2019) y otras. (shrink)

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 (...) de hecho científico de las cuestiones de cómo funciona el lenguaje. Discuto las opiniones de Wittgenstein sobre la incompletitud, la paracoherencia y la indecisión y el trabajo de Wolpert en los límites de la computación. Resumiendo: el universo según Brooklyn---buena ciencia, no tan buena filosofía. Aquellos que deseen un marco completo hasta la fecha para el comportamiento humano de la moderna dos sistemas punto de vista puede consultar mi libros Talking Monkeys 3ª ed (2019), Estructura Logica de Filosofia, Psicología, Mente y Lenguaje en Ludwig Wittgenstein y John Searle 2ª ed (2019), Suicidio pela Democracia 4ª ed (2019), La Estructura Logica del Comportamiento Humano (2019), The Logical Structure de la Conciencia (2019, Entender las Conexiones entre Ciencia, Filosofía, Psicología, Religión, Política y Economía (2019), Delirios Utópicos Suicidas en el siglo 21 5ª ed (2019), Observaciones sobre Imposibilidad, Incompletitud, Paraconsistencia, Indecidibilidad, Aleatoriedad, Computabilidad, Paradoja e Incertidumbre en Chaitin, Wittgenstein, Hofstadter, Wolpert, Doria, da Costa, Godel, Searle, Rodych Berto, Floyd, Moyal-Sharrock y Yanofsky y otros. (shrink)

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? (...) Contributors from multiple perspectives reflecting the diversity of thought regarding these interconnections address many of the most important developments and debates within this exciting area of research. Both a reference to the state of the art and a valuable and accessible entry to interdisciplinary work, the volume will interest researchers and students working in physics, computer science, and philosophy of science and mathematics. (shrink)

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 (...) of intractability is solved by recourse to ‘as if’ explanations critically depends, inter alia, on the semantics of the ‘as if’ connective. We examine the five most sensible explications in the literature, and conclude that none of them circumvents the problem. As a result, rational ‘as if’ explanations must obey the minimal computational constraint of tractability. (shrink)

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, (...) while highly desirable, is overvalued. Simulations also provide valuable insights that we cannot yet (if ever) prove. (shrink)

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 (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

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.

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 (...) entities with numbers. I argue that, in providing this correlation, we must demand that the correlation itself be computable. Otherwise, the Turing machine will compute uncomputable functions. But if we presuppose the intuitive notion of a computable relation between syntactic entities and numbers, then our analysis of computability is circular. (shrink)

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.

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 (...) and Ott's (1996) claim of uncomputable behavior in a system with riddled basins of attraction. Furthermore, it clarifies speculations that the stability of the solar system (and similar systems) may be undecidable, for the invariant tori established by KAM theory form sets that are not d-. (shrink)

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. (...) Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [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]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

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 (...) have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

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 (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (shrink)

A survey of the field of hypercomputation, including discussion of a variety of objections.

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 (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

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.

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.

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 (...) tape. A small, fixed program that is 'hard-wired' into the head enables the head to read and execute the instructions of whatever program is on the tape. The machine's atomic operations are very simple—for example, 'move left one square', 'move right one square', 'identify the symbol currently beneath the head', 'write 1 on the square that is beneath the head', and 'write 0 on the square that is beneath the head'. Complexity of operation is achieved by the chaining together of large numbers of these simple atoms. Any universal Turing machine can be programmed to carry out any calculation that can be performed by a human mathematician working with paper and pencil in accordance with some algorithmic method. This is what is meant by calling these machines 'universal'. (shrink)

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”).

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 (...) is computation (or brains are computers); butall processes are computations (orall physical things are computers); so AI and Cog Sci are positively silly.I refute this argument herein, in part by defining the locutions x is a computer and c is a computation in a way that blocks Searle''s argument but exploits the hard-to-deny link between What''s Computation? and the theory of computation. However, I also provide, at the end of this essay, an argument which, it seems to me, implies not that AI and Cog Sci are silly, but that they''re based on a form of computation that is well beneath human persons. (shrink)

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.