The Church-Turing Thesis

Why are we so many? Or, in other words, Why is our species so successful? The ultimate cause of our success as species is that we, Homo sapiens, are the first and the only Turing complete species. Turing completeness is the capacity of some hardware to compute by software whatever hardware can compute. -/- To reach the answer, I propose to see evolution and computing from the problem solving point of view. Then, solving more problems is evolutionarily better, computing is (...) for solving problems, and software is much cheaper than hardware, resulting that Turing completeness is evolutionarily disruptive. This conclusion, together with the fact that we are the only Turing complete species, is the reason that explains why we are so many. -/- Most of our unique cognitive characteristics as humans can be derived from being Turing complete, as for example our complete language and our problem solving creativity. (shrink)

Although Fuzzy logic and Fuzzy Mathematics is a widespread subject and there is a vast literature about it, yet the use of Fuzzy issues like Fuzzy sets and Fuzzy numbers was relatively rare in time concept. This could be seen in the Fuzzy time series. In addition, some attempts are done in fuzzing Turing Machines but seemingly there is no need to fuzzy time. Throughout this article, we try to change this picture and show why it is helpful to consider (...) the instants of time as Fuzzy numbers. In physics, though there are revolutionary ideas on the time concept like B theories in contrast to A theory also about central concepts like space, momentum… it is a long time that these concepts are changed, but time is considered classically in all well-known and established physics theories. Seemingly, we stick to the classical time concept in all fields of science and we have a vast inertia to change it. Our goal in this article is to provide some bases why it is rational and reasonable to change and modify this picture. Here, the central point is the modified version of “Unexpected Hanging” paradox as it is described in "Is classical Mathematics appropriate for theory of Computation".This modified version leads us to a contradiction and based on that it is presented there why some problems in Theory of Computation are not solved yet. To resolve the difficulties arising there, we have two choices. Either “choosing” a new type of Logic like “Para-consistent Logic” to tolerate contradiction or changing and improving the time concept and consequently to modify the “Turing Computational Model”. Throughout this paper, we select the second way for benefiting from saving some aspects of Classical Logic. In chapter 2, by applying quantum Mechanics and Schrodinger equation we compute the associated fuzzy number to time. These, provides a new interpretation of Quantum Mechanics.More exactly what we see here is "Particle-Fuzzy time" interpretation of quantum Mechanics, in contrast to some other interpretations of Quantum Mechanics like " Wave-Particle" interpretation. At the end, we propound a question about the possible solution of a paradox in Physics, the contradiction between General Relativity and Quantum Mechanics. (shrink)

An abstract machine having a tape head that can be advanced in 0 to 0x7FFFFFFF increments an unlimited number of times specifies a model of computation that has access to unlimited memory. The technical name for memory addressing based on displacement from the current memory address is relative addressing.

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)

A German translation with 2017 postscript of Floyd, Juliet. 2012. "Wittgenstein's Diagonal Argument: A Variation on Cantor and Turing." In Epistemology versus Ontology, Logic, Epistemology: Essays in Honor of Per Martin-Löf, edited by P. Dybjer, S. Lindström, E. Palmgren and G. Sundholm, 25-44. Dordrecht: Springer Science+Business Media. An analysis of philosophical aspects of Turing's diagonal argument in his (136) "On computable numbers, with an application to the Entscheidungsproblem" in relation to Wittgenstein's writings on Turing and Cantor.

This is a review of The Turing Guide (2017), written by Jack Copeland, Jonathan Bowen, Mark Sprevak, Robin Wilson, and others. The review includes a new sociological approach to the problem of computability in physics.

Я даю подробный обзор "Внешние границы разума" Носон Янофски с единой точки зрения Витгенштейна и эволюционной психологии. Я указываю, что трудности с такими вопросами, как парадокс в языке и математике, неполнота, несоответствие, вычислительность, мозг и вселенная, как компьютеры и т.д., все это возникает из-за неспособности внимательно посмотреть на наше использование языка в соответствующем контексте и, следовательно, неспособность отделить вопросы научного факта от вопросов о том, как работает язык. Я обсуждаю взгляды Витгенштейна на неполноту, последовательность и несоответствие и нерешающость и работу (...) Вольперта на пределы вычислений. Подводя итог: Вселенная согласно Бруклин---Хорошая Наука, не так хорошая философия. Те, кто желает всеобъемлющего до современных рамок для человеческого поведения из современных двух systEms зрения могут проконсультироваться с моей книгой"Логическая структура философии, психологии, Минd иязык в Людвиг Витгенштейн и Джон Сирл" второй ред (2019). Те, кто заинтересован в более моих сочинений могут увидеть "Говоря обезьян - Философия, психология, наука, религия и политика на обреченной планете - Статьи и обзоры 2006-2019 3-й ed (2019) и suicidal утопических заблуждений в 21-мst веке 4-й ed (2019) th и другие. (shrink)

私は計算と宇宙の限界に関する最近の議論をコンピュータとして読み、ポリマス物理学者と意思決定理論家デビッド・ウォルパートの驚くべき仕事に関するいくつかのコメントを見つけることを望んでいますが、単一の引用 を見つけていないので、私はこの非常に簡単な要約を提示します。ウォルパートは、計算を行うデバイスから独立し、物理学の法則から独立している推論(計算)の限界に関する驚くべき不可能または不完全な定理(199 2年から2008年のarxiv.org参照)を証明したので、コンピュータ、物理学、人間の行動に適用されます。彼らは、カントールの対角化、嘘つきのパラドックス、ワールドラインを利用して、チューリングマシ ン理論の究極の定理である可能性のあるものを提供し、不可能、不完全性、計算の限界、そしてコンピュータとしての宇宙に関する洞察を提供し、すべての可能な宇宙とすべての存在またはメカニズムを生み出し、とりわけ 非量子機械不確実性原理と単一主義の証明を生み出します。チャイティン、ソロモノフ、コモルガロフ、ヴィトゲンシュタインの古典的な作品と、どのプログラム(したがってデバイスも)が所有するよりも複雑なシーケン ス(またはデバイス)を生成できないという考えには明らかなつながりがあります。この作品の体は、物理的な宇宙よりも複雑な存在はあり得ないので無テズムを意味すると言うかもしれませんし、ヴィトゲンチニアンの観 点から見ると、「より複雑な」は無意味です(満足の条件はありません、すなわち、真実のメーカーやテスト)。「神」(つまり、無限の時間/空間とエネルギーを持つ「デバイス」)でさえ、与えられた「数」が「ランダ ム」であるかどうかを判断したり、与えられた「公式」、定理または「文章」または「デバイス」(これらはすべて複雑な言語ゲームである)が特定の「システム」の一部であることを示す特定の方法を見つけることができ ません。 現代の2つのシス・エムスの見解から人間の行動のための包括的な最新の枠組みを望む人は、私の著書「ルートヴィヒ・ヴィトゲンシュタインとジョン・サールの第2回(2019)における哲学、心理学、ミンと言語の論 理的構造」を参照することができます。私の著作の多くにご興味がある人は、21世紀4日(2019年)の「話す猿--哲学、心理学、科学、宗教、政治」を見ることができます。 .

ノソン・ヤノフスキーの「理性の外側の限界」を、ウィトゲンシュタインと進化心理学の統一的な視点から詳しくレビューします。私は、言語や数学のパラドックス、不完全さ、デデシッド性、コンピュータとしての脳、宇 宙などの問題の難しさは、すべて適切な文脈での言語の使用を注意深く見なさなかったことから生じるため、科学的事実の問題を言語の仕組みの問題から切り離すことができなかったことを示しています。私は、不完全さ、 パラタンシ、不整合性に関するヴィトゲンシュタインの見解と、計算の限界に関するウォルパートの仕事について議論します。要約すると:ブルックリンによると宇宙---良い科学、それほど良い哲学ではありません。 現代の2つのシス・エムスの見解から人間の行動のための包括的な最新の枠組みを望む人は、私の著書「ルートヴィヒ・ヴィトゲンシュタインとジョン・サールの第2回(2019)における哲学、心理学、ミンと言語の論 理的構造」を参照することができます。私の著作の多くにご興味がある人は、運命の惑星における「話す猿--哲学、心理学、科学、宗教、政治―記事とレビュー2006-2019 第3回(2019)」と21世紀4日(2019年)の自殺ユートピア妄想st Century 4th ed (2019)などを見ることができます。 .

J’ai lu de nombreuses discussions récentes sur les limites du calcul et de l’univers en tant qu’ordinateur, dans l’espoir de trouver quelques commentaires sur le travail étonnant du physicien polymathe et théoricien de la décision David Wolpert, mais n’ont pas trouvé une seule citation et je présente donc ce résumé très bref. Wolpert s’est avéré quelques théoricaux d’impossibilité ou d’incomplétude renversants (1992 à 2008-voir arxiv dot org) sur les limites de l’inférence (computation) qui sont si généraux qu’ils sont indépendants de (...) l’appareil faisant le calcul, et même indépendamment des lois de la physique, ainsi ils s’appliquent à travers les ordinateurs, la physique, et le comportement humain. Ils utilisent la diagonalisation de Cantor, le paradoxe menteur et les worldlines (lignes du monde) pour fournir ce qui peut être le théorème ultime dans Turing Machine Theory, et apparemment fournir des aperçus de l’impossibilité, l’incomplétude, les limites du calcul, et l’univers comme ordinateur, dans tous les univers possibles et tous les êtres ou mécanismes possibles, générant, entre autres, un principe d’incertitude mécanique non quantique et une preuve de monothéisme. Il existe des connexions évidentes à l’œuvre classique de Chaitin, Solomonoff, Komolgarov et Wittgenstein et à l’idée qu’aucun programme (et donc aucun dispositif) ne peut générer une séquence (ou un dispositif) avec une plus grande complexité qu’il ne possède. On pourrait dire que cet ensemble de travaux implique l’athéisme puisqu’il ne peut y avoir d’entité plus complexe que l’univers physique et du point de vue wittgensteinien, « plus complexe » n’a aucun sens (n’a pas de conditions de satisfaction, c’est-à-dire véridique ou test). Même un « Dieu » (c’est-à-dire un « dispositif » avec un temps/ espace et une énergie illimité) ne peut pas déterminer si un « nombre » donné est « aléatoire», ni trouver un certain moyen de montrer qu’une « formule » donnée, un « théorème » ou une « phrase » ou un « dispositif » (tous ces jeux de langage complexes) fait partie d’un « système » particulier. Ceux qui souhaitent un cadre complet à jour pour le comportement humain de la vue moderne de deux systemes peuvent consulter mon livre 'The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle' 2nd ed (2019). Ceux qui s’intéressent à plus de mes écrits peuvent voir 'Talking Monkeys --Philosophie, Psychologie, Science, Religion et Politique sur une planète condamnée --Articles et revues 2006-2019 2ème ed (2019) et Suicidal Utopian Delusions in the 21st Century 4th ed (2019) et autres. (shrink)

Ich habe viele kürzliche Diskussionen über die Grenzen der Berechnung und das Universum als Computer gelesen, in der Hoffnung, einige Kommentare über die erstaunliche Arbeit des Polymath Physikers und Entscheidungstheoretikers David Wolpert zu finden, aber habe kein einziges Zitat gefunden und so präsentiere ich diese sehr kurze Zusammenfassung. Wolpert bewies einige verblüffende Unmöglichkeit oder Unvollständigkeit Theoreme (1992 bis 2008-siehe arxiv dot org) über die Grenzen der Schlussfolgerung (Berechnung), die so allgemein sind, dass sie unabhängig von dem Gerät, das die Berechnung, (...) und sogar unabhängig von den Gesetzen der Physik, so dass sie für Computer, Physik und menschliches Verhalten gelten. Sie nutzen Cantors Diagonalisierung, das Lügner-Paradoxon und die Weltlinien, um das vielleicht ultimative Theorem in turing Machine Theory zu liefern, und geben scheinbar Einblicke in Unmöglichkeit, Unvollständigkeit, die Grenzen der Berechnung und das Universum als Computer, in alle möglichen Universen und alle Wesen oder Mechanismen, was unter anderem ein nicht quantenmechanisches Unsicherheitsprinzip und einen Beweis für Monotheismus erzeugt. Es gibt offensichtliche Verbindungen zum klassischen Werk von Chaitin, Solomonoff, Komolgarov und Wittgenstein und zu der Vorstellung, dass kein Programm (und damit kein Gerät) eine Sequenz (oder ein Gerät) mit größerer Komplexität erzeugen kann, als es besitzt. Man könnte sagen, dass dieses Werk den Atheismus impliziert, da es keine Entität geben kann, die komplexer ist als das physikalische Universum, und aus Wittgensteins Sicht ist "komplexer" bedeutungslos (hat keine Bedingungen der Befriedigung, d.h. Wahrheitsmacher oder Test). Selbst ein "Gott" (das heist ein "Gerät" mit unbegrenzter Zeit/Raum und Energie) kann weder bestimmen, ob eine bestimmte "Zahl" "zufällig"ist, noch einen bestimmten Weg finden, um nachzuweisen, dass eine bestimmte "Formel", "Satz" oder "Satz" oder "Gerät" (alles komplexe Sprachspiele) Teil eines bestimmten "Systems" ist. Wer aus der modernen zweisystems-Sichteinen umfassenden, aktuellen Rahmen für menschliches Verhalten wünscht, kann mein Buch "The Logical Structure of Philosophy, Psychology, Mindand Language in Ludwig Wittgenstein and John Searle' 2nd ed (2019) konsultieren. Diejenigen,die sich für mehr meiner Schriften interessieren, können Talking Monkeys--Philosophie, Psychologie, Wissenschaft, Religion und Politik auf einem verdammten Planeten --Artikel und Rezensionen 2006-2019 2nd ed (2019) und Suicidal Utopian Delusions in the 21st Century 4th ed (2019) und andere sehen. (shrink)

Я читал много недавних дискуссий о границах вычислений и Вселенной, как компьютер, надеясь найти некоторые комментарии по удивительной работы физика полимата и теоретик решений Дэвид Вольперт, но не нашли ни одной цитаты, и поэтому я представляю это очень краткое резюме. Вольперт доказал некоторые потрясающие невозможности или теоремы неполноты (1992 до 2008-см arxiv dot org) на пределы выводов (вычисления), которые настолько общие они не зависят от устройства делать вычисления, и даже независимо от законов физики, поэтому они применяются через компьютеры, физика, и (...) поведение человека. Они используют диагоналализацию Кантора, парадокс лжецов и мирские линии, чтобы обеспечить то, что может быть конечной теорему в теории машины Тьюринга, и, казалось бы, дают представление о невозможности, неполноте, пределы вычислений, и Вселенной, как компьютер, во всех возможных вселенных и всех существ или механизмов, генерации, среди прочего, неквантовной неопределенности механического принципа и доказательство монотеизма. Есть очевидные связи с классической работой Чайтина, Соломона, Комольгарова и Витгенштейна и с понятием, что ни одна программа (и, следовательно, ни одно устройство) не может генерировать последовательность (или устройство) с большей сложностью, чем она обладает. Можно сказать, что этот объем работы подразумевает атеизм, поскольку не может быть ни одной сущности, более сложной, чем физическая вселенная, и с точки зрения Витгенштейна, «более сложный» не имеет смысла (не имеет условий удовлетворения, т.е. истины-мейкера или испытания). Даже "Бог" (т.е. "устройство" с безграничным временем /пространством и энергией) не, может определить, является ли данное "число" "случайным", ни найти определенный способ показать, что данная "формула", "теорема" или "предложение" или "устройство" (все это сложные языковые игры) является частью конкретной "системы". Те, кто желает всеобъемлющего до современных рамок для человеческого поведения из современных двух systEms зрения могут проконсультироваться с моей книгой"Логическая структура философии, психологии, Минd иязык в Людвиг Витгенштейн и Джон Сирл" второй ред (2019). Те, кто заинтересован в более моих работ могут увидеть "Говоря обезьян - -Философия, Психология, Наука, Религия и Политика на обреченной планете - Статьи и обзоры 2006-2019 2-й эд (2019) и суицидальные утопические заблуждения в 21-мst веке 4-й ed (2019) th и другие. (shrink)

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

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...) other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

I give a detailed review of 'The Outer Limits of Reason' by Noson Yanofsky from a unified perspective of Wittgenstein and evolutionary psychology. I indicate that the difficulty with such issues as paradox in language and math, incompleteness, undecidability, computability, the brain and the universe as computers etc., all arise from the failure to look carefully at our use of language in the appropriate context and hence the failure to separate issues of scientific fact from issues of how language works. (...) I discuss Wittgenstein's views on incompleteness, paraconsistency and undecidability and the work of Wolpert on the limits to computation. To sum it up: The Universe According to Brooklyn---Good Science, Not So Good Philosophy. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 3rd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

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 dot 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. There are obvious connections to the classic work of Chaitin, Solomonoff, Komolgarov and Wittgenstein and to the notion that no program (and thus no device) can generate a sequence (or device) with greater complexity than it possesses. One might say this body of work implies atheism since there cannot be any entity more complex than the physical universe and from the Wittgensteinian viewpoint, ‘more complex’ is meaningless (has no conditions of satisfaction, i.e., truth-maker or test). Even a ‘God’ (i.e., a ‘device’with limitless time/space and energy) cannot determine whether a given ‘number’ is ‘random’, nor find a certain way to show that a given ‘formula’, ‘theorem’ or ‘sentence’ or ‘device’ (all these being complex language games) is part of a particular ‘system’. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 2nd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

Eu li muitas discussões recentes sobre os limites da computação e do universo como computador, na esperança de encontrar alguns comentários sobre o trabalho surpreendente do físico polimatemático e teórico da decisão David Wolpert, mas não encontrei uma única citação e assim que eu apresento este muito breve Resumo. Wolpert provou alguma impossibilidade impressionante ou teoremas da incompletude (1992 a 2008-Veja arxiv dot org) nos limites à inferência (computação) que são tão gerais que são independentes do dispositivo que faz a (...) computação, e mesmo independente das leis da física, para que eles se apliquem em computadores, física e comportamento humano. Eles fazem uso da diagonalização de cantor, o paradoxo mentiroso e worldlines (linhas do mundo) para fornecer o que pode ser o teorema final na teoria da máquina de Turing, e, aparentemente, fornecer insights sobre a impossibilidade, incompletude, os limites da computação, e do universo como computador, em todos os universos possíveis e todos os seres ou mecanismos, gerando, entre outras coisas, um princípio de incerteza mecânica não quântica e uma prova de monoteísmo. Há umas conexões óbvias ao trabalho clássico de Chaitin, Solomonoff, Komolgarov e Wittgenstein e à noção que nenhum programa (e assim nenhum dispositivo) pode gerar uma seqüência (ou dispositivo) com maior complexidade do que possui. Pode-se dizer que este corpo de trabalho implica ateísmo, uma vez que não pode haver qualquer entidade mais complexa do que o universo físico e do ponto de vista Wittgensteiniano, ' mais complexo ' é sem sentido (não tem condições de satisfação, ou seja, criador de verdade ou teste). Mesmo um ' Deus ' (ou seja, um ' dispositivo ' com tempo ilimitado/espaço e energia) não pode determinar se um determinado ' número ' é ' aleatório ', nem encontrar uma determinada maneira de mostrar que uma determinada ' fórmula ', ' teorema ' ou ' sentença ' ou ' Device ' (todos estes sendo linguagem complexa jogos) faz parte de um determinado «sistema». Aqueles que desejam um quadro até à data detalhado para o comportamento humano da opinião moderna dos dois sistemas consultar meu livros Falando Macacos 3ª Ed (2019), A Estrutura Lógica da Filosofia, Psicologia, Mente e Linguagem em Ludwig Wittgenstein e John Searle 2a Ed (2019), Suicídio Pela Democracia,4aEd(2019), Entendendo as Conexões entre Ciência, Filosofia, Psicologia, Religião, Política e Economia Artigos e Análises 2006-2019 (2019), Ilusões Utópicas Suicidas no 21St século 5a Ed (2019), A Estrutura Lógica do Comportamento Humano (2019), e A Estrutura Lógica da Consciência (2019) y outras. (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)

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...) never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)

This volume celebrates the various facets of Alan Turing (1912–1954), the British mathematician and computing pioneer, widely considered as the father of computer science. It is aimed at the general reader, with additional notes and references for those who wish to explore the life and work of Turing more deeply. -/- The book is divided into eight parts, covering different aspects of Turing’s life and work. -/- Part I presents various biographical aspects of Turing, some from a personal point of (...) view. -/- Part II presents Turing’s universal machine (now known as a Turing machine), which provides a theoretical framework for reasoning about computation. His 1936 paper on this subject is widely seen as providing the starting point for the field of theoretical computer science. -/- Part III presents Turing’s working on codebreaking during World War II. While the War was a disastrous interlude for many, for Turing it provided a nationally important outlet for his creative genius. It is not an overstatement to say that without Turing, the War would probably have lasted longer, and may even have been lost by the Allies. The sensitive nature of Turning’s wartime work meant that much of this has been revealed only relatively recently. -/- Part IV presents Turing’s post-War work on computing, both at the National Physical Laboratory and at the University of Manchester. He made contributions to both hardware design, through the ACE computer at the NPL, and software, especially at Manchester. Part V covers Turing’s contribution to machine intelligence (now known as Artificial Intelligence or AI). Although Turing did not coin the term, he can be considered a founder of this field which is still active today, authoring a seminal paper in 1950. -/- Part VI covers morphogenesis, Turing’s last major scientific contribution, on the generation of seemingly random patterns in biology and on the mathematics behind such patterns. Interest in this area has increased rapidly in recent times in the field of bioinformatics, with Turing’s 1952 paper on this subject being frequently cited. -/- Part VII presents some of Turing’s mathematical influences and achievements. Turing was remarkably free of external influences, with few co-authors – Max Newman was an exception and acted as a mathematical mentor in both Cambridge and Manchester. -/- Part VIII considers Turing in a wider context, including his influence and legacy to science and in the public consciousness. -/- Reflecting Turing’s wide influence, the book includes contributions by authors from a wide variety of backgrounds. Contemporaries provide reminiscences, while there are perspectives by philosophers, mathematicians, computer scientists, historians of science, and museum curators. Some of the contributors gave presentations at Turing Centenary meetings in 2012 in Bletchley Park, King’s College Cambridge, and Oxford University, and several of the chapters in this volume are based on those presentations – some through transcription of the original talks, especially for Turing’s contemporaries, now aged in their 90s. Sadly, some contributors died before the publication of this book, hence its dedication to them. -/- For those interested in personal recollections, Chapters 2, 3, 11, 12, 16, 17, and 36 will be of interest. For philosophical aspects of Turing’s work, see Chapters 6, 7, 26–31, and 41. Mathematical perspectives can be found in Chapters 35 and 37–39. Historical perspectives can be found in Chapters 4, 8, 9, 10, 13–15, 18, 19, 21–25, 34, and 40. With respect to Turing’s body of work, the treatment in Parts II–VI is broadly chronological. We have attempted to be comprehensive with respect to all the important aspects of Turing’s achievements, and the book can be read cover to cover, or the chapters can be tackled individually if desired. There are cross-references between chapters where appropriate, and some chapters will inevitably overlap. -/- We hope that you enjoy this volume as part of your library and that you will dip into it whenever you wish to enter the multifaceted world of Alan Turing. (shrink)

A review of Computability: Turing, Gödel, Church, and Beyond by Copeland, Posy and Shagrir.

We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the 'distance' (in terms of physical resources) from a physical state to another, and (3) the size of the set of time--complexity functions that are compatible with the physical (...) resources required to reach a physical state from another. (shrink)

There exists a growing literature on the so-called physical Church-Turing thesis in a relativistic spacetime setting. The physical Church-Turing thesis is the conjecture that no computing device that is physically realizable can exceed the computational barriers of a Turing machine. By suggesting a concrete implementation of a beyond-Turing computer in a spacetime setting, Istvan Nemeti and Gyula David have shown how an appreciation of the physical Church-Turing thesis necessitates the confluence of mathematical, computational, physical, and indeed cosmological ideas. In this (...) essay, I will honour Istvan's seventieth birthday, as well as his longstanding interest in, and his seminal contributions to, this field going back to as early as 1987 by modestly proposing how the concrete implementation in Nemeti and D\'avid might be complemented by a quantum-information-theoretic communication protocol between the computing device and the logician who sets the beyond-Turing computer a task such as determining the consistency of Zermelo-Fraenkel set theory. This suggests that even the foundations of quantum theory and, ultimately, quantum gravity may play an important role in determining the validity of the physical Church-Turing thesis. (shrink)

Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum computer might (...) implement the idea of "infinite calculation" is the main subject. (shrink)

Traditionally, many writers, following Kleene (1952), thought of the Church-Turing thesis as unprovable by its nature but having various strong arguments in its favor, including Turing’s analysis of human computation. More recently, the beauty, power, and obvious fundamental importance of this analysis, what Turing (1936) calls “argument I,” has led some writers to give an almost exclusive emphasis on this argument as the unique justification for the Church-Turing thesis. In this chapter I advocate an alternative justification, essentially presupposed by Turing (...) himself in what he calls “argument II.” The idea is that computation is a special form of mathematical deduction. Assuming the steps of the deduction can be stated in a first order language, the Church-Turing thesis follows as a special case of Gödel’s completeness theorem (first order algorithm theorem). I propose this idea as an alternative foundation for the Church-Turing thesis, both for human and machine computation. Clearly the relevant assumptions are justified for computations presently known. Other issues, such as the significance of Gödel’s 1931 Theorem IX for the Entscheidungsproblem, are discussed along the way. (shrink)

There is much discussion about whether the human mind is a computer, whether the human brain could be emulated on a computer, and whether at all physical entities are computers (pancomputationalism). These discussions, and others, require criteria for what is digital. I propose that a state is digital if and only if it is a token of a type that serves a particular function - typically a representational function for the system. This proposal is made on a syntactic level, assuming (...) three levels of description (physical, syntactic, semantic). It suggests that being digital is a matter of discovery or rather a matter of how we wish to describe the world, if a functional description can be assumed. Given the criterion provided and the necessary empirical research, we should be in a position to decide on a given system (e.g. the human brain) whether it is a digital system and can thus be reproduced in a different digital system (since digital systems allow multiple realization). (shrink)

I want to suggest that the major influence of classical arguments for embodiment like "The Embodied Mind" by Varela, Thomson & Rosch (1991) has been a changing of positions rather than a refutation: Cognitivism has found ways to retreat and regroup at positions that have better fortification, especially when it concerns theses about artificial intelligence or artificial cognitive systems. For example: a) Agent-based cognitivism' that understands humans as taking in representations of the world, doing rule-based processing and then acting on (...) them (sense-plan-act) is often limited to conscious decision processes; and b) Purely syntactic cognition is compatible with embodiment, or supplemented by embodiment (e.g. for 'grounding'). While the empirical thesis of embodied cognition ('embodied cognitive science') is true and the practical engineering thesis ('morphological computation', 'cheap design') is often true, the conceptual thesis ('embodiment is necessary for cognition') is likely false - syntax is often enough for cognition, unless grounding is really necessary. I conclude that it has become more sensible to integrate embodiment with traditional approaches rather than "fight for embodiment" or "against cognitivism". (shrink)

La thèse de Church-Turing stipule que toute fonction calculable est calculable par une machine de Turing. En distinguant, à la suite de nombreux auteurs, une forme algorithmique de la thèse de Church-Turing portant sur les fonctions calculables par un algorithme d’une forme empirique de cette même thèse, portant sur les fonctions calculables par une machine, il devient possible de poser une nouvelle question : les limites empiriques du calcul sont-elles identiques aux limites des algorithmes ? Ou existe-t-il un moyen empirique (...) d’effectuer un calcul qu’aucun algorithme ne permet d’effectuer ? Je montrerai ici la pertinence philosophique de cette question. Elle interroge la capacité de processus symboliques comme les calculs à simuler certains processus empiriques. Elle permet également d’étudier le statut épistémologique des calculs réalisés par des machines. S’il existait une fonction calculable par une machine sans être calculable par un algorithme, il existerait un problème mathématique qui serait soluble par un dispositif empirique, sans être soluble par aucune méthode mathématique a priori. (shrink)

Cet article se veut une critique de la thèse défendue par [Cleland 1993], laquelle soutient que la thèse de Church doit être rejetée puisque les limites du calcul dépendent de la structure physique du monde. Dans un premier temps, nous offrons un (très) bref aperçu de la thèse de Church puis nous présentons l argument de Cleland. Par la suite, nous proposons une analyse critique de son argument, ce qui nous amènera à faire quelques distinctions conceptuelles par rapport aux notions (...) qui concernent la calculabilité. Finalement, nous montrons que les limites du calcul ne sont pas physiques mais bien logiques. En résumé, notre argument est que les limites du calcul sont déterminées en partie par le fait qu’une procédure effective doit pouvoir être décrite de manière finie. (shrink)

In this paper I argue that whether or not a computer can be built that passes the Turing test is a central question in the philosophy of mind. Then I show that the possibility of building such a computer depends on open questions in the philosophy of computer science: the physical Church-Turing thesis and the extended Church-Turing thesis. I use the link between the issues identified in philosophy of mind and philosophy of computer science to respond to a prominent argument (...) against the possibility of building a machine that passes the Turing test. Finally, I respond to objections against the proposed link between questions in the philosophy of mind and philosophy of computer science. (shrink)

This paper investigates the view that digital hypercomputing is a good reason for rejection or re-interpretation of the Church-Turing thesis. After suggestion that such re-interpretation is historically problematic and often involves attack on a straw man (the ‘maximality thesis’), it discusses proposals for digital hypercomputing with Zeno-machines , i.e. computing machines that compute an infinite number of computing steps in finite time, thus performing supertasks. It argues that effective computing with Zeno-machines falls into a dilemma: either they are specified such (...) that they do not have output states, or they are specified such that they do have output states, but involve contradiction. Repairs though non-effective methods or special rules for semi-decidable problems are sought, but not found. The paper concludes that hypercomputing supertasks are impossible in the actual world and thus no reason for rejection of the Church-Turing thesis in its traditional interpretation. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

Olszewski claims that the Church-Turing thesis can be used in an argument against platonism in philosophy of mathematics. The key step of his argument employs an example of a supposedly effectively computable but not Turing-computable function. I argue that the process he describes is not an effective computation, and that the argument relies on the illegitimate conflation of effective computability with there being a way to find out . ‘Ah, but,’ you say, ‘what’s the use of its being right twice (...) a day, if I can’t tell when the time comes?’ Why, suppose the clock points to eight o’clock, don’t you see that the clock is right at eight o’clock? Consequently, when eight o’clock comes round your clock is right. Lewis Carroll. (shrink)

The Turing machine is one of the simple abstract computational devices that can be used to investigate the limits of computability. In this paper, they are considered from several points of view that emphasize the importance and the relativity of mathematical languages used to describe the Turing machines. A deep investigation is performed on the interrelations between mechanical computations and their mathematical descriptions emerging when a human (the researcher) starts to describe a Turing machine (the object of the study) by (...) different mathematical languages (the instruments of investigation). Together with traditional mathematical languages using such concepts as ‘enumerable sets’ and ‘continuum’ a new computational methodology allowing one to measure the number of elements of different infinite sets is used in this paper. It is shown how mathematical languages used to describe the machines limit our possibilities to observe them. In particular, notions of observable deterministic and non-deterministic Turing machines are introduced and conditions ensuring that the latter can be simulated by the former are established. (shrink)

This paper develops my (BJPS 2009) criticisms of the philosophical significance of a certain sort of infinitary computational process, a hyperloop. I start by considering whether hyperloops suggest that "effectively computable" is vague (in some sense). I then consider and criticise two arguments by Hogarth, who maintains that hyperloops undermine the very idea of effective computability. I conclude that hyperloops, on their own, cannot threaten the notion of an effective procedure.

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

We argue from the Church-Turing thesis (Kleene Mathematical logic. New York: Wiley 1967) that a program can be considered as equivalent to a formal language similar to predicate calculus where predicates can be taken as functions. We can relate such a calculus to Wittgenstein’s first major work, the Tractatus, and use the Tractatus and its theses as a model of the formal classical definition of a computer program. However, Wittgenstein found flaws in his initial great work and he explored these (...) flaws in a new thesis described in his second great work; the Philosophical Investigations. The question we address is “can computer science make the same leap?” We are proposing, because of the flaws identified by Wittgenstein, that computers will never have the possibility of natural communication with people unless they become active participants of human society. The essential difference between formal models used in computing and human communication is that formal models are based upon rational sets whereas people are not so restricted. We introduce irrational sets as a concept that requires the use of an abductive inference system. However, formal models are still considered central to our means of using hypotheses through deduction to make predictions about the world. These formal models are required to continually be updated in response to peoples’ changes in their way of seeing the world. We propose that one mechanism used to keep track of these changes is the Peircian abductive loop. (shrink)

There are various equivalent formulations of the Church-Turing thesis. A common one is that every effective computation can be carried out by a Turing machine. The Church-Turing thesis is often misunderstood, particularly in recent writing in the philosophy of mind.

This paper deals with the question: What are the criteria that an adequate theory of computation has to meet? 1. Smith's answer: it has to meet the empirical criterion (i.e. doing justice to computational practice), the conceptual criterion (i.e. explaining all the underlying concepts) and the cognitive criterion (i.e. providing solid grounds for computationalism). 2. Piccinini's answer: it has to meet the objectivity criterion (i.e. identifying computation as a matter of fact), the explanation criterion (i.e. explaining the computer's behaviour), the (...) right things compute criterion, the miscomputation criterion (i.e. accounting for malfunctions), the taxonomy criterion (i.e. distinguishing between different classes of computers) and the empirical criterion. 3. Von Neumann's answer: it has to meet the precision and reliability of computers criterion, the single error criterion (i.e. addressing the impacts of errors) and the distinction between analogue and digital computers criterion. 4. “Everything” computes answer: it has to meet the implementation theory criterion by properly explaining the notion of implementation. -/- According to computationalists, minds are computational. Before we can judge the plausibility of any particular computationalist theory, we need to understand what notion of computation this theory employs. Although there are extant accounts of computation, any of which may, in principle, serve as a basis for computationalism, it isn’t clear that they’re all equivalent or even adequate as accounts of computation proper. By examining plausible alternatives to Smith’s adequacy criteria, our goal here is to resist his claim that no adequate account of computation proper is possible. (shrink)

The classical view of computing positions computation as a closed-box transformation of inputs (rational numbers or finite strings) to outputs. According to the interactive view of computing, computation is an ongoing interactive process rather than a function-based transformation of an input to an output. Specifically, communication with the outside world happens during the computation, not before or after it. This approach radically changes our understanding of what is computation and how it is modeled. The acceptance of interaction as a new (...) paradigm is hindered by the Strong Church–Turing Thesis (SCT), the widespread belief that Turing Machines (TMs) capture all computation, so models of computation more expressive than TMs are impossible. In this paper, we show that SCT reinterprets the original Church–Turing Thesis (CTT) in a way that Turing never intended; its commonly assumed equivalence to the original is a myth. We identify and analyze the historical reasons for the widespread belief in SCT. Only by accepting that it is false can we begin to adopt interaction as an alternative paradigm of computation. We present Persistent Turing Machines (PTMs), that extend TMs to capture sequential interaction. PTMs allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of TMs and of the CTT. The paradigm shift to interaction provides an alternative understanding of the nature of computing that better reflects the services provided by today’s computing technology. (shrink)