Theory of Computation

This paper describes a method for the analysis of the evolutionary path of a complex, dynamic, and contingent social phenomenon in an empirical setting. Given empirical evidence of a surprising or anomalous fact, which contradicts the prediction of the wide-acknowledged theory, the goal is to formulate a plausible explanation based on the context of occurrence, taking a holistic and historical point of view. The procedure begins by translating theoretical propositions into grammar rules to describe patterns of either individual action or (...) interaction that may occur within the hypothesized social system. The result is a category of social process in which the objects are types of decision-making events carried by a stable community of actors over time, and the relationships between them are state transitions revealed in the sequences of event outcomes. Therefore, structural comparison between pairs of representative instances result in an extension of the category of social processes, relying on the configurations of contextual conditions that enable the occurrence of the new event outcome in specific empirical settings. (shrink)

This review essay analyzes the book by Giuseppe Primiero, On the foundations of computing. Oxford: Oxford University Press (ISBN 978-0-19-883564-6/hbk; 978-0-19-883565-3/pbk). xix, 296 p. (2020). It gives a critical view from the perspective of physical computing as a foundation of computing and argues that the neglected pillar of material computation (Stepney) should be brought centerstage and computing recognized as the fourth great domain of science (Denning).

It is well known that the set of algebraic numbers (let us call it A) is countable. In this paper, instead of the usage of the classical terminology of cardinals proposed by Cantor, a recently introduced methodology using ①-based infinite numbers is applied to measure the set A (where the number ① is called grossone). Our interest to this methodology is explained by the fact that in certain cases where cardinals allow one to say only whether a set is countable (...) or it has the cardinality of the continuum, the ①-based methodology can provide a more accurate measurement of infinite sets. In this article, lower and upper estimates of the number of elements of A are obtained. Both estimates are expressed in ①-based numbers. (shrink)

This chapter responds to Michael Tamir and Elay Shech’s chapter “Understanding from Deep Learning Models in Context.”.

The novel concept of a simulating halt decider enables halt decider H to to correctly determine the halt status of the conventional “impossible” input D that does the opposite of whatever H decides. This works equally well for Turing machines and “C” functions. The algorithm is demonstrated using “C” functions because all of the details can be shown at this high level of abstraction. ---------------------------------------------------------------------------------------------------- ---- Simulating halt decider H correctly determines that D correctly simulated by H would remain stuck in (...) recursive simulation never reaching its own final state. D cannot do the opposite of the return value from H because this return value is unreachable by every correctly simulated D. This same result is shown to be derived in the Peter Linz Turing machine based proof. (shrink)

Some philosophical considerations over Yann LeCun’s position paper “A Path Towards Autonomous Machine Intelligence”.

Simple idealized models seem to provide more understanding than opaque, complex, and hyper-realistic models. However, an increasing number of scientists are going in the opposite direction by utilizing opaque machine learning models to make predictions and draw inferences, suggesting that scientists are opting for models that have less potential for understanding. Are scientists trading understanding for some other epistemic or pragmatic good when they choose a machine learning model? Or are the assumptions behind why minimal models provide understanding misguided? In (...) this paper, using the case of deep neural networks, I argue that it is not the complexity or black box nature of a model that limits how much understanding the model provides. Instead, it is a lack of scientific and empirical evidence supporting the link that connects a model to the target phenomenon that primarily prohibits understanding. (shrink)

The halting theorem counter-examples present infinitely nested simulation (non-halting) behavior to every simulating halt decider. Whenever the pure simulation of the input to simulating halt decider H(x,y) never stops running unless H aborts its simulation H correctly aborts this simulation and returns 0 for not halting.

The emerging contemporary natural philosophy provides a common ground for the integrative view of the natural, the artificial, and the human-social knowledge and practices. Learning process is central for acquiring, maintaining, and managing knowledge, both theoretical and practical. This paper explores the relationships between the present advances in understanding of learning in the sciences of the artificial, natural sciences, and philosophy. The question is, what at this stage of the development the inspiration from nature, specifically its computational models such as (...) info-computation through morphological computing, can contribute to machine learning and artificial intelligence, and how much on the other hand models and experiments in machine learning and robotics can motivate, justify, and inform research in computational cognitive science, neurosciences, and computing nature. We propose that one contribution can be understanding of the mechanisms of ‘learning to learn’, as a step towards deep learning with symbolic layer of computation/information processing in a framework linking connectionism with symbolism. As all natural systems possessing intelligence are cognitive systems, we describe the evolutionary arguments for the necessity of learning to learn for a system to reach humanlevel intelligence through evolution and development. The paper thus presents a contribution to the epistemology of the contemporary philosophy of nature. (shrink)

At first sight the Theory of Computation i) relies on a kind of mathematics based on the notion of potential infinity; ii) its theoretical organization is irreducible to an axiomatic one; rather it is organized in order to solve a problem: “What is a computation?”; iii) it makes essential use of doubly negated propositions of non-classical logic, in particular in the word expressions of the Church-Turing’s thesis; iv) its arguments include ad absurdum proofs. Under such aspects, it is like many (...) other scientific theories, in particular the first theories of both mechanical machines and heat machines. A more accurate examination of Theory of Computation shows a difference from the above mentioned theories in its essentially including an odd notion, “thesis”, to which no theorem corresponds. On the other hand, arguments of each of the other theories conclude a doubly negative predicate which then, by applying the inverse translation of the ‘negative one’, is translated into the corresponding affirmative predicate. By also taking into account three criticisms to the current Theory of Computation a rational re-formulation of it is sketched out; to Turing-Church thesis of the usual theory corresponds a similar proposition, yet connecting physical total computation functions with constructive mathematical total computation functions. -/- . (shrink)

A definition of quantum computer is supposed: as a countable set of Turing machines on the ground of: quantum parallelism, reversibility, entanglement. Qubit is the set of all the i–th binary location cells transforming in parallel by unitary matrices. The Church thesis is suggested in the form relevat to quantum computer. The notion of the non–finite (but not infinite) potency of a set is introduced .

This paper is concerned with learners who aim to learn patterns in infinite binary sequences: shown longer and longer initial segments of a binary sequence, they either attempt to predict whether the next bit will be a 0 or will be a 1 or they issue forecast probabilities for these events. Several variants of this problem are considered. In each case, a no-free-lunch result of the following form is established: the problem of learning is a formidably difficult one, in that (...) no matter what method is pursued, failure is incomparably more common that success; and difficult choices must be faced in choosing a method of learning, since no approach dominates all others in its range of success. In the simplest case, the comparison of the set of situations in which a method fails and the set of situations in which it succeeds is a matter of cardinality (countable vs. uncountable); in other cases, it is a topological matter (meagre vs. co-meagre) or a hybrid computational-topological matter (effectively meagre vs. effectively co-meagre). (shrink)

When does it make sense to act randomly? A persuasive argument from Bayesian decision theory legitimizes randomization essentially only in tie-breaking situations. Rational behaviour in humans, non-human animals, and artificial agents, however, often seems indeterminate, even random. Moreover, rationales for randomized acts have been offered in a number of disciplines, including game theory, experimental design, and machine learning. A common way of accommodating some of these observations is by appeal to a decision-maker’s bounded computational resources. Making this suggestion both precise (...) and compelling is surprisingly difficult. Toward this end, I propose two fundamental rationales for randomization, drawing upon diverse ideas and results from the wider theory of computation. The first unifies common intuitions in favour of randomization from the aforementioned disciplines. The second introduces a deep connection between randomization and memory: access to a randomizing device is provably helpful for an agent burdened with a finite memory. Aside from fit with ordinary intuitions about rational action, the two rationales also make sense of empirical observations in the biological world. Indeed, random behaviour emerges more or less where it should, according to the proposal. (shrink)

In questo contributo descriviamo un sistema di creatività computazionale in grado di generare automaticamente nuovi concetti utilizzando una logica descrittiva non monotòna che integra tre ingredienti principali: una logica descrittiva della tipicalità, una estensione probabilistica basata sulla semantica distribuita nota come DISPONTE, e una euristica di ispirazione cognitiva per la combinazione di più concetti. Una delle applicazioni principali del sistema riguarda il campo della creatività computazionale e, più specificatamente, il suo utilizzo come sistema di supporto alla creatività in ambito mediale. (...) In particolare, tale sistema è in grado di: generare nuove storie (a partire da una rappresentazione narrativa di storie pre-esistenti), generare nuovi personaggi (ad es. il nuovo “cattivo” di una serie tv o di un cartone animato) e, in generale, può essere utilizzato per proporre nuove soluzioni e format narrativi da esplorare nell’ambito dell’industria creativa. (shrink)

In this survey, a recent computational methodology paying a special attention to the separation of mathematical objects from numeral systems involved in their representation is described. It has been introduced with the intention to allow one to work with infinities and infinitesimals numerically in a unique computational framework in all the situations requiring these notions. The methodology does not contradict Cantor’s and non-standard analysis views and is based on the Euclid’s Common Notion no. 5 “The whole is greater than the (...) part” applied to all quantities (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite). The methodology uses a computational device called the Infinity Computer (patented in USA and EU) working numerically (recall that traditional theories work with infinities and infinitesimals only symbolically) with infinite and infinitesimal numbers that can be written in a positional numeral system with an infinite radix. It is argued that numeral systems involved in computations limit our capabilities to compute and lead to ambiguities in theoretical assertions, as well. The introduced methodology gives the possibility to use the same numeral system for measuring infinite sets, working with divergent series, probability, fractals, optimization problems, numerical differentiation, ODEs, etc. (recall that traditionally different numerals lemniscate; Aleph zero, etc. are used in different situations related to infinity). Numerous numerical examples and theoretical illustrations are given. The accuracy of the achieved results is continuously compared with those obtained by traditional tools used to work with infinities and infinitesimals. In particular, it is shown that the new approach allows one to observe mathematical objects involved in the Hypotheses of Continuum and the Riemann zeta function with a higher accuracy than it is done by traditional tools. It is stressed that the hardness of both problems is not related to their nature but is a consequence of the weakness of traditional numeral systems used to study them. It is shown that the introduced methodology and numeral system change our perception of the mathematical objects studied in the two problems. (shrink)

Physical Computation is the summation of Piccinini’s work on computation and mechanistic explanation over the past decade. It draws together material from papers published during that time, but also provides additional clarifications and restructuring that make this the definitive presentation of his mechanistic account of physical computation. This review will first give a brief summary of the account that Piccinini defends, followed by a chapter-by-chapter overview of the book, before finally discussing one aspect of the account in more critical detail.

This volume offers very selected papers from the 2014 conference of the “International Association for Computing and Philosophy” (IACAP) - a conference tradition of 28 years. - - - Table of Contents - 0 Vincent C. Müller: - Editorial - 1) Philosophy of computing - 1 Çem Bozsahin: - What is a computational constraint? - 2 Joe Dewhurst: - Computing Mechanisms and Autopoietic Systems - 3 Vincenzo Fano, Pierluigi Graziani, Roberto Macrelli and Gino Tarozzi: - Are Gandy Machines really local? (...) - 4 Doukas Kapantais: - A refutation of the Church-Turing thesis according to some interpretation of what the thesis says - 5 Paul Schweizer: - In What Sense Does the Brain Compute? - 2) Philosophy of computer science & discovery - 6 Mark Addis, Peter Sozou, Peter C R Lane and Fernand Gobet: - Computational Scientific Discovery and Cognitive Science Theories - 7 Nicola Angius and Petros Stefaneas: - Discovering Empirical Theories of Modular Software Systems. An Algebraic Approach. - 8 Selmer Bringsjord, John Licato, Daniel Arista, Naveen Sundar Govindarajulu and Paul Bello: - Introducing the Doxastically Centered Approach to Formalizing Relevance Bonds in Conditionals - 9 Orly Stettiner: - From Silico to Vitro: - Computational Models of Complex Biological Systems Reveal Real-world Emergent Phenomena - 3) Philosophy of cognition & intelligence - 10 Douglas Campbell: - Why We Shouldn’t Reason Classically, and the Implications for Artificial Intelligence - 11 Stefano Franchi: - Cognition as Higher Order Regulation - 12 Marcello Guarini: - Eliminativisms, Languages of Thought, & the Philosophy of Computational Cognitive Modeling - 13 Marcin Miłkowski: - A Mechanistic Account of Computational Explanation in Cognitive Science and Computational Neuroscience - 14 Alex Tillas: - Internal supervision & clustering: - A new lesson from ‘old’ findings? - 4) Computing & society - 15 Vasileios Galanos: - Floridi/Flusser: - Parallel Lives in Hyper/Posthistory - 16 Paul Bello: - Machine Ethics and Modal Psychology - 17 Marty J. Wolf and Nir Fresco: - My Liver Is Broken, Can You Print Me a New One? - 18 Marty J. Wolf, Frances Grodzinsky and Keith W. Miller: - Robots, Ethics and Software – FOSS vs. Proprietary Licenses. (shrink)

The contribution of the body to cognition and control in natural and artificial agents is increasingly described as “off-loading computation from the brain to the body”, where the body is said to perform “morphological computation”. Our investigation of four characteristic cases of morphological computation in animals and robots shows that the ‘off-loading’ perspective is misleading. Actually, the contribution of body morphology to cognition and control is rarely computational, in any useful sense of the word. We thus distinguish (1) morphology that (...) facilitates control, (2) morphology that facilitates perception and the rare cases of (3) morphological computation proper, such as ‘reservoir computing.’ where the body is actually used for computation. This result contributes to the understanding of the relation between embodiment and computation: The question for robot design and cognitive science is not whether computation is offloaded to the body, but to what extent the body facilitates cognition and control – how it contributes to the overall ‘orchestration’ of intelligent behaviour. (shrink)

Chapin reviewed this 1972 ZEITSCHRIFT paper that proves the completeness theorem for the logic of variable-binding-term operators created by Corcoran and his student John Herring in the 1971 LOGIQUE ET ANALYSE paper in which the theorem was conjectured. This leveraging proof extends completeness of ordinary first-order logic to the extension with vbtos. Newton da Costa independently proved the same theorem about the same time using a Henkin-type proof. This 1972 paper builds on the 1971 “Notes on a Semantic Analysis of (...) Variable Binding Term Operators” (Co-author John Herring), Logique et Analyse 55, 646–57. MR0307874 (46 #6989). A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. Kalish-Montague 1964 proposed using vbtos to formalize definite descriptions “the x: x+x=2”, set abstracts {x: F}, minimization in recursive function theory “the least x: x+x>2”, etc. However, they gave no semantics for vbtos. Hatcher 1968 gave a semantics but one that has flaws described in the 1971 paper and admitted by Hatcher. In 1971 we give a correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture, proved in this paper with Hatcher’s help, was proved independently about the same time by Newton da Costa. (shrink)

Review of: "Computation, Information, Cognition: The Nexus and the Liminal", Ed. Susan Stuart & Gordana Dodig Crnkovic, Newcastle: Cambridge Scholars Publishing, September 2007, xxiv+340pp, ISBN: 9781847180902, Hardback: £39.99, $79.99 ---- Are you a computer? Is your cat a computer? A single biological cell in your stomach, perhaps? And your desk? You do not think so? Well, the authors of this book suggest that you think again. They propose a computational turn, a turn towards computational explanation and towards the explanation of (...) computation itself. The explanation of computation is the core of the present volume, but the computational turn to regard a wide variety of systems as computational is a potentially very wide-ranging project. (shrink)

Cognition is commonly taken to be computational manipulation of representations. These representations are assumed to be digital, but it is not usually specified what that means and what relevance it has for the theory. I propose a specification for being a digital state in a digital system, especially a digital computational system. The specification shows that identification of digital states requires functional directedness, either for someone or for the system of which it is a part. In the case or digital (...) representations, to be a token of a representational type, where the function of the type is to represent. [An earlier version of this paper was discussed in the web-conference "Interdisciplines" https://web.archive.org/web/20100221125700/http://www.interdisciplines.org/adaptation/papers/7 ]. (shrink)

The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second recursion theorem, I prove (...) that it is mathematically possible for us to be in a simulation that is being run on a computer \textit{by us}. In such a case, there would be two identical instances of us; the question of which of those is ``really us'' is meaningless. I also show how Rice's theorem provides some interesting impossibility results concerning simulation and self-simulation; briefly describe the philosophical implications of fully homomorphic encryption for (self-)simulation; briefly investigate the graphical structure of universes simulating universes simulating universes, among other issues. I end by describing some of the possible avenues for future research that this preliminary investigation reveals. (shrink)

The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined even if it is not sufficiently formal and precise to belong to mathematics proper (in a narrow sense)—and even if (as many have asserted) for that reason the Church–Turing thesis is unprovable. It is proved logically that the class of effective procedures is not decidable, i.e., that no effective procedure is possible for ascertaining whether a given procedure is effective. This (...) undecidability result is proved directly from the notion itself of an effective procedure, without reliance on any (partly) mathematical lemma, conjecture, or thesis invoking recursiveness or Turing-computability. In fact, there is no reliance on anything very mathematical. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of an effective procedure. Though the result that effectiveness is undecidable is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure invariably terminates with the correct verdict. (shrink)

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)

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.

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)

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

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

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

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)

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)

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.

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)

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)

This paper aims to contribute to the analysis of the nature of mathematical modality and hyperintensionality, and to the applications of the latter to absolute decidability. Rather than countenancing the interpretational type of mathematical modality as a primitive, I argue that the interpretational type of mathematical modality is a species of epistemic modality. I argue, then, that the framework of two-dimensional semantics ought to be applied to the mathematical setting. The framework permits of a formally precise account of the priority (...) and relation between epistemic mathematical modality and metaphysical mathematical modality. The discrepancy between the modal systems governing the parameters in the two-dimensional intensional setting provides an explanation of the difference between the metaphysical possibility of absolute decidability and our knowledge thereof. I also advance a topic-sensitive epistemic two-dimensional truthmaker semantics, if hyperintensional approaches are to be preferred to possible worlds semantics. I examine the relation between two-dimensional hyperintensional states and epistemic set theory, providing two-dimensional hyperintensional formalizations of the modal logic of ZFC, large cardinal axioms, $\Omega$-logic, and the Epistemic Church-Turing Thesis. (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)

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)

In this paper, the issues of computability and constructivity in the mathematics of physics are discussed. The sorts of questions to be addressed are those which might be expressed, roughly, as: Are the mathematical foundations of our current theories unavoidably non-constructive: or, Are the laws of physics computable?

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.

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)

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)