Christopher G. Timpson provides the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. He argues for an ontologically deflationary account of the nature of quantum information, which is grounded in a revisionary analysis of the concepts of information.

There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument (...) for CTT by analyzing the processes carried out by a human computer. I then contend that if the Gandy–Sieg account is correct, then the notion of effective computability has changed after 1936. Today computer scientists view effective computability in terms of finite machine computation. My contention is supported by the current formulations of CTT, which always refer to machine computation, and by the current argumentation for CTT, which is different from the main arguments advanced by Turing and Church. I finally turn to discuss Robin Gandy's characterization of machine computation. I suggest that there is an ambiguity regarding the types of machines Gandy was postulating. I offer three interpretations, which differ in their scope and limitations, and conclude that none provides the basis for claiming that Gandy characterized finite machine computation. (shrink)

The article discusses the limitations of psycho-physical parallellism and the implications of a pscycho-physical interaction paradigm considering the notion Downward Causation. The focus is on the notion of levels in nature and their interrelations, and it argues that the notion of rule-based systems should be considered a subcategory of rule-generating systems partly based on redundancy functions rather than rules.

We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that θ does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new (...) characterization of effectively simple sets and show that simple sets are not btt-cuppable. (shrink)

This paper is divided in five sections. Section 11.1 sketches the history of the distinction between speech act with negative content and negated speech act, and gives a general dynamic interpretation for negated speech act. “Downdate semantics” for AGM contraction is introduced in Section 11.2. Relying on semantically interpreted contraction, Section 11.3 develops the dynamic semantics for constative and directive speech acts, and their external negations. The expressive completeness for the formal variants of natural language utterances, none of which is (...) a retraction, has been proved in Section 11.4. The last section gives a laconic answer to the question posed in the title of the paper. (shrink)

This book explores the interplay between logic and science, describing new trends, new issues and potential research developments.

1. Logic, determinism and free will. The determinism-free will debate is perhaps as old as philosophy itself and has been engaged in from a great variety of points of view including those of scientific, theological and logical character; my concern here is to limit attention to two arguments from logic. To begin with, there is an argument in support of determinism that dates back to Aristotle, if not farther. It rests on acceptance of the Law of Excluded Middle, according to (...) which every proposition is either true or false, no matter whether the proposition is about the past, present or future. In particular, the argument goes, whatever one does or does not do in the future is determined in the present by the truth or falsity of the corresponding proposition. Surely no such argument could really establish determinism, but one is hard pressed to explain where it goes wrong. One now classic dismantling of it has been given by Gilbert Ryle, in the chapter ‘What was to be’ of his fine book, Dilemmas (Ryle 1954). We leave it to the interested reader to pursue that and the subsequent literature. (shrink)

(1991). Gödel, Turing, chaitin and the question of emergence as a meta‐principle of modern physics. some arguments against reductionism. World Futures: Vol. 32, Creative Evolution in Nature, Mind, and Society, pp. 185-195.

This paper explains how mathematical computation can be constructed from weaker recursive patterns typical of natural languages. A thought experiment is used to describe the formalization of computational rules, or arithmetical axioms, using only orally-based natural language capabilities, and motivated by two accomplishments of ancient Indian mathematics and linguistics. One accomplishment is the expression of positional value using versified Sanskrit number words in addition to orthodox inscribed numerals. The second is Pāṇini’s invention, around the fifth century BCE, of a formal (...) grammar for spoken Sanskrit, expressed in oral verse extending ordinary Sanskrit, and using recursive methods rediscovered in the twentieth century. The Sanskrit positional number compounds and Pāṇini’s formal system are construed as linguistic grammaticalizations relying on tacit cognitive models of symbolic form. The thought experiment shows that universal computation can be constructed from natural language structure and skills, and shows why intentional capabilities needed for language use play a role in computation across all media. The evolution of writing and positional number systems in Mesopotamia is used to transfer the thought experiment of “oral arithmetic” to inscribed computation. The thought experiment and historical evidence combine to show how and why mathematical computation is a cognitive technology extending generic symbolic skills associated with language structure, usage, and change. (shrink)

Computationalism has been the mainstream view of cognition for decades. There are periodic reports of its demise, but they are greatly exaggerated. This essay surveys some recent literature on computationalism. It concludes that computationalism is a family of theories about the mechanisms of cognition. The main relevant evidence for testing it comes from neuroscience, though psychology and AI are relevant too. Computationalism comes in many versions, which continue to guide competing research programs in philosophy of mind as well as psychology (...) and neuroscience. Although our understanding of computationalism has deepened in recent years, much work in this area remains to be done. (shrink)

We highlight the limitations of formal methods by exhibiting two results in recursive function theory: that there is no effective means of finding a program that satisfies a given formal specification; or checking that a program meets a specification. We also exhibit a ‘simple’ MAS which has all the power of a Turing machine. We then argue that any ‘pure design’ methodology will face insurmountable difficulties in today’s open and complex MAS. Rather we suggest a methodology based on the classic (...) experimental method – that is ‘scientific foundations’ for the construction and control of complex MAS. (shrink)

Quantum Information Theory and the Foundations of Quantum Mechanics is a conceptual analysis of one of the most prominent and exciting new areas of physics, providing the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. -/- Beginning from a careful, revisionary, analysis of the concepts of information in the everyday and classical information-theory settings, Christopher G. Timpson argues for an ontologically deflationary account of the nature of quantum information. (...) Against what many have supposed, quantum information can be clearly defined (it is not a primitive or vague notion) but it is not part of the material contents of the world. Timpson's account sheds light on the nature of nonlocality and information flow in the presence of entanglement and, in particular, dissolves puzzles surrounding the remarkable process of quantum teleportation. In addition it permits a clear view of what the ontological and methodological lessons provided by quantum information theory are; lessons which bear on the gripping question of what role a concept like information has to play in fundamental physics. Topics discussed include the slogan 'Information is Physical', the prospects for an informational immaterialism (the view that information rather than matter might fundamentally constitute the world), and the status of the Church-Turing hypothesis in light of quantum computation. -/- With a clear grasp of the concept of information in hand, Timpson turns his attention to the pressing question of whether advances in quantum information theory pave the way for the resolution of the traditional conceptual problems of quantum mechanics: the deep problems which loom over measurement, nonlocality and the general nature of quantum ontology. He marks out a number of common pitfalls to be avoided before analysing in detail some concrete proposals, including the radical quantum Bayesian programme of Caves, Fuchs, and Schack. One central moral which is drawn is that, for all the interest that the quantum information-inspired approaches hold, no cheap resolutions to the traditional problems of quantum mechanics are to be had. (shrink)

What counts as a computation and how it relates to cognitive function are important questions for scientists interested in understanding how the mind thinks. This paper argues that pragmatic aspects of explanation ultimately determine how we answer those questions by examining what is needed to make rigorous the notion of computation used in the (cognitive) sciences. It (1) outlines the connection between the Church-Turing Thesis and computational theories of physical systems, (2) differentiates merely satisfying a computational function from true computation, (...) and finally (3) relates how we determine a true computation to the functional methodology in cognitive science. All of the discussion will be directed toward showing that the only way to connect formal notions of computation to empirical theory will be in virtue of the pragmatic aspects of explanation. (shrink)

Traditional approaches to modeling cognitive systems are computational, based on utilizing the standard tools and concepts of the theory of computation. More recently, a number of philosophers have argued that cognition is too subtle or complex for these tools to handle. These philosophers propose an alternative based on dynamical systems theory. Proponents of this view characterize dynamical systems as (i) utilizing continuous rather than discrete mathematics, and, as a result, (ii) being computationally more powerful than traditional computational automata. Indeed, the (...) logical possibility of such super-powerful systems has been demonstrated in the form of analog artificial neural networks. In this paper I consider three arguments against the nomological possibility of these automata. While the first two arguments fail, the third succeeds. In particular, the presence of noise reduces the computational power of analog networks to that of traditional computational automata, and noise is a pervasive feature of information processing in biological systems. Consequently, as an empirical thesis, the proposed dynamical alternative is under-motivated: What is required is an account of how continuously valued systems could be realized in physical systems despite the ubiquity of noise. (shrink)

This paper explores Church's Thesis and related claims madeby Turing. Church's Thesis concerns computable numerical functions, whileTuring's claims concern both procedures for manipulating uninterpreted marksand machines that generate the results that these procedures would yield. Itis argued that Turing's claims are true, and that they support (the truth of)Church's Thesis. It is further argued that the truth of Turing's and Church'sTheses has no interesting consequences for human cognition or cognitiveabilities. The Theses don't even mean that computers can do as much (...) as peoplecan when it comes to carrying out effective procedures. For carrying out aprocedure is a purposive, intentional activity. No actual machine does, orcan do, as much. (shrink)

In this article it is argued that the relation between the socalled Gutenberg galaxis of print culture and the Turing galaxis of digital media is not one of opposition and substitution, but rather one of co-evolution and integration. Or more precisely: that the Gutenberg galaxis on the one hand can be inscribed into the Turing galaxis, which on the other hand is textual in character since it is based on linear and serially processed representations manifested in a binary alphabet. In (...) continuation of this text and hypertext is described as notions of related but different sorts of complex systems and it is argued that both texts and hypertexts are best thought of as sequentially organised. The first part of the paper contains a description of the basic properties of computers and digital representation answering the question: what are the properties common to all kinds of use of computers – whether used for one purpose or another? The second part is concerned with the relationship between printed and electronic text. The third part addresses the idea of hypertext as systems which exploits modal shifts between node-mode and link-mode as a significant part of the semantics of the system. (shrink)

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

Alonzo Church (1903–1995) was a renowned mathematical logician, philosophical logician, philosopher, teacher and editor. He was one of the founders of the discipline of mathematical logic as it developed after Cantor, Frege and Russell. He was also one of the principal founders of the Association for Symbolic Logic and the Journal of Symbolic Logic. The list of his students, mathematical and philosophical, is striking as it contains the names of renowned logicians and philosophers. In this article, we focus primarily on (...) Church’s philosophical contributions. (For an account of his life and academic history see the Introduction to The Collected Works of Alonzo Church (2019).) However, we also discuss his mathematical results when it is desirable to do so in order to pursue a philosophical issue. (shrink)

Physicalism is the default position in science and in the philosophy of mind, but it should not be, I argue, because of two errors. By its epistemological error, physicalism gives physics priority over the evidence of first person experience. Only what I experience in first person is certain, so observation is prior to any theory. Physics itself is based on observation, avoiding the epistemological error, and then physics can progress, even changing its own ontology. However, physicalism imposes the ontology of (...) physics on every science, and in physics everything is causal. By its ontological error, physicalism tries to explain causally what is intentional. And it happens that causality and intentionality are mutually exclusive, showing that the ontology of physics is insufficient wherever intentions are present. This ontological insufficiency prevents that physicalism can repeat the success of physics with any science where intentions play a rôle, and thus it is blocking the advance of both the social sciences and the philosophy of mind. To overcome this obstacle, I propose to go back to the essentials: we should consider again the transcendental problem raised by Descartes and its solutions by Hume and Kant. On top of this subjectivist solution, we should take advantage of Darwin and Turing, and we should extend our ontology beyond causality to include intentionality, and here my proposal is problem solving. Then you could join our Post-Kantian subjectivism and say with me: The world is not a huge machine, as physicalism proposes, but an enigmatic problem. (shrink)

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

The book provides a historical and systematic exposition of the semantic theory of truth formulated by Alfred Tarski in the 1930s. This theory became famous very soon and inspired logicians and philosophers. It has two different, but interconnected aspects: formal-logical and philosophical. The book deals with both, but it is intended mostly as a philosophical monograph. It explains Tarski’s motivation and presents discussions about his ideas as well as points out various applications of the semantic theory of truth to philosophical (...) problems. (shrink)

SUMMARY Major theories of philosophical psychology and philosophy of mind are examined on the basis of the fundamental questions of ontology, metaphysics, epistemology, semantics and logic. The result is the choice between language of eliminative reductionism and dualism, neither of which answers properly the relation between mind and body. In the search for a non–dualistic and non–reductive language, Wittgenstein’s notion of language–games as the representative links between language and the world is considered together with Peirce’s semeiosis of cognition. The result (...) is a redefined notion of cognition as the goal–oriented ability to instantiate strategies from the rules of the language–games. Cognition is considered within the four-dimensional languagegames: rules/strategies, primitive/complete language-games, family-resemblances/forms of life, and non-temporal continuum as the language-games’ modality. Cognition is seen as a continuum process of non–individualized elements that unites perception, volition, emotion, will and thought against the commonly accepted understandings of cognition in exclusive terms of perception and thinking. The alternative to the mind/body problem is the continuity of cognition where rules and strategies, syntax and semantics, are considered inseparable within language–games. This continuity of cognition is explained in terms of virtual (univocal) identity, replacing the old philosophical paradigm of the mind/body problem. -/- SOMMARIO Le teorie maggiori della psicologia filosofica e filosofia della mente sono esaminate a partire dalle questioni fondamentali di ontologia, metafisica, epistemologia, semantica e logica. Il risultato è la scelta tra un linguaggio riduzionista eliminativo e un dualismo che però non confronta in modo adeguato la relazione tra mente e corpo. Nella ricerca per un linguaggio non-dualistico e non-riduttivo, viene considerata la nozione del gioco linguistico di Wittgenstein come un legame rappresentativo tra il linguaggio e il mondo insieme con la semiosi cognitiva di Peirce. Il risultato è la nozione ridefinita della cognizione come abilità goal-orientata di creare le strategie dalle regole dei giochi linguistici. La cognizione è considerata entro le quattro dimensioni dei giochi linguistici: regole/strategie, giochi linguistici primitivi/completi, somiglianze di famiglia/forme di vita, e la continuità atemporale come la modalità dei giochi linguistici. La cognizione diventa un processo continuo degli elementi non-individualizzati che tende ad unificare la percezione, volizione, emozione, la volontà e il pensiero contro un concetto generalmente accettato di vedere la cognizione nei termini esclusivamente di percezione e di pensiero. L’alternativa al problema della mente/corpo è la continuità della cognizione, dove le regole e le strategie, la sintassi e la semantica, sono considerate inseparabili nei giochi linguistici. Questa continuità della cognizione è spiegata nei termini dell’identità virtuale (univoca) sostituendo un paradigma filosofico previo del problema della mente/corpo. (shrink)

Esta enciclopédia abrange, de uma forma introdutória mas desejavelmente rigorosa, uma diversidade de conceitos, temas, problemas, argumentos e teorias localizados numa área relativamente recente de estudos, os quais tem sido habitual qualificar como «estudos lógico-filosóficos». De uma forma apropriadamente genérica, e apesar de o território teórico abrangido ser extenso e de contornos por vezes difusos, podemos dizer que na área se investiga um conjunto de questões fundamentais acerca da natureza da linguagem, da mente, da cognição e do raciocínio humanos, bem (...) como questões acerca das conexões destes com a realidade não mental e extralinguística. A razão daquela qualificação é a seguinte: por um lado, a investigação em questão é qualificada como filosófica em virtude do elevado grau de generalidade e abstracção das questões examinadas (entre outras coisas); por outro, a investigação é qualificada como lógica em virtude de ser uma investigação logicamente disciplinada, no sentido de nela se fazer um uso intenso de conceitos, técnicas e métodos provenientes da disciplina de lógica. O agregado de tópicos que constitui a área de estudos lógico-filosóficos é já visível, pelo menos em parte, no Tractatus Logico-Philosophicus de Ludwig Wittgenstein, uma obra publicada em 1921. E uma boa maneira de ter uma ideia sinóptica do território disciplinar abrangido por esta enciclopédia, ou pelo menos de uma porção substancial dele, é extrair do Tractatus uma lista dos tópicos mais salientes aí discutidos; a lista incluirá certamente tópicos do seguinte género, muitos dos quais se podem encontrar ao longo desta enciclopédia: factos e estados de coisas; objectos; representação; crenças e estados mentais; pensamentos; a proposição; nomes próprios; valores de verdade e bivalência; quantificação; funções de verdade; verdade lógica; identidade; tautologia; o raciocínio matemático; a natureza da inferência; o cepticismo e o solipsismo; a indução; as constantes lógicas; a negação; a forma lógica; as leis da ciência; o número. (shrink)

We show how removing faith-based beliefs in current philosophies of classical and constructive mathematics admits formal, evidence-based, definitions of constructive mathematics; of a constructively well-defined logic of a formal mathematical language; and of a constructively well-defined model of such a language. -/- We argue that, from an evidence-based perspective, classical approaches which follow Hilbert's formal definitions of quantification can be labelled `theistic'; whilst constructive approaches based on Brouwer's philosophy of Intuitionism can be labelled `atheistic'. -/- We then adopt what may (...) be labelled a finitary, evidence-based, `agnostic' perspective and argue that Brouwerian atheism is merely a restricted perspective within the finitary agnostic perspective, whilst Hilbertian theism contradicts the finitary agnostic perspective. -/- We then consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary, evidence-based, definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways. -/- We show that the two definitions correspond to two distinctly different---not necessarily evidence-based but complementary---assignments of satisfaction and truth to the compound formulas of PA over N. -/- We further show that the PA axioms are true over N, and that the PA rules of inference preserve truth over N, under both the complementary interpretations; and conclude some unsuspected constructive consequences of such complementarity for the foundations of mathematics, logic, philosophy, and the physical sciences. -/- . (shrink)

There are many branches of philosophy called “the philosophy of X,” where X = disciplines ranging from history to physics. The philosophy of artificial intelligence has a long history, and there are many courses and texts with that title. Surprisingly, the philosophy of computer science is not nearly as well-developed. This article proposes topics that might constitute the philosophy of computer science and describes a course covering those topics, along with suggested readings and assignments.

It is commonly believed that there is no equivalent of the Church–Turing thesis for computation over the reals. In particular, computational models on this domain do not exhibit the convergence of formalisms that supports this thesis in the case of integer computation. In the light of recent philosophical developments on the different meanings of the Church–Turing thesis, and recent technical results on analog computation, I will show that this current belief confounds two distinct issues, namely the extension of the notion (...) of effective computation to the reals on the one hand, and the simulation of analog computers by Turing machines on the other hand. I will argue that it is possible in both cases to defend an equivalent of the Church–Turing thesis over the reals. Along the way, we will learn some methodological caveats on the comparison of different computational models, and how to make it meaningful. (shrink)

Noam Chomsky and other linguists and psychologists have suggested that human linguistic behavior is somehow governed by a mental representation of a transformational grammar. Challenges to this controversial claim have often been met by invoking an explicitly computational perspective: It makes perfect sense to suppose that a grammar could be represented in the memory of a computational device and that this grammar could govern the device's use of a language. This paper urges, however, that the claim that humans are such (...) a device is unsupported and that it seems unlikely that linguists and psychologists really want to claim any such thing. Evidence for the linguists' original claim is drawn from three main sources: the explanation of language comprehension and other linguistic abilities; evidence for formal properties of the rules of the grammar; and the explanation of language acquisition. It is argued in this paper that none of these sources provides support for the view that the grammar governs language processing in something like the way a program governs the operation of a programmed machine. The computational approach, on the contrary, suggests ways in which linguistic abilities can be explained without the attribution of any explicit representation of rules governing linguistic behavior. (shrink)

The identification of an informal concept of ‘effective calculability’ with a rigorous mathematical notion like ‘recursiveness’ or ‘Turing computability’ is still viewed as problematic, and I think rightly so. I analyze three different and conflicting perspectives Gödel articulated in the three decades from 1934 to 1964. The significant shifts in Gödel's position underline the difficulties of the methodological issues surrounding the Church-Turing Thesis.

We sketch the historical and conceptual context of Turing's analysis of algorithmic or mechanical computation. We then discuss two responses to that analysis, by Gödel and by Gandy, both of which raise, though in very different ways. The possibility of computation procedures that cannot be reduced to the basic procedures into which Turing decomposed computation. Along the way, we touch on some of Cleland's views.

This paper concerns Alan Turing’s ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for (...) Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the “mathematical
objection” to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it
should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human
mathematicians presumably do. (shrink)

Throughout what is now the more than 50-year history of the computer many theories have been advanced regarding the contribution this machine would make to changes both in the structure of society and in ways of thinking. Like other theories regarding the future, these should also be taken with a pinch of salt. The history of the development of computer technology contains many predictions which have failed to come true and many applications that have not been foreseen. While we must (...) reserve judgment as to the question of the impact on the structure of society and human thought, there is no reason to wait for history when it comes to the question: what are the properties that could give the computer such far-reaching importance? The present book is intended as an answer to this question. The fact that this is a theoretical analysis is due to the nature of the subject. No other possibilities are available because such a description of the properties of the computer must be valid for any kind of application. An additional demand is that the description should be capable of providing an account of the properties which permit and limit these possible applications, just as it must make it possible to characterize a computer as distinct from a) other machines whether clocks, steam engines, thermostats, or mechanical and automatic calculating machines, b) other symbolic media whether printed, mechanical, or electronic and c) other symbolic languages whether ordinary languages, spoken or written or formal languages. This triple limitation, however, (with regard to other machines, symbolic media and symbolic languages) raises a theoretical question as it implies a meeting between concepts of mechanical-deterministic systems, which stem from mathematical physics, and concepts of symbolic systems which stem from the description of symbolic activities common to the humanities. The relationship between science and the humanities has traditionally been seen from a dualistic perspective, as a relationship between two clearly separate subject areas, each studied on its own set of premises and using its own methods. In the present case, however, this perspective cannot be maintained since there is both a common subject area and a new - and specific - kind of interaction between physical and symbolic processes. (shrink)

The alleged proof of the non-mechanical, or non-computational, character of the human mind based on Gödel’s incompleteness theorem is revisited. Its history is reviewed. The proof, also known as the Lucas argument and the Penrose argument, is refuted. It is claimed, following Gödel himself and other leading logicians, that antimechanism is not implied by Gödel’s theorems alone. The present paper sets out this refutation in its strongest form, demonstrating general theorems implying the inconsistency of Lucas’s arithmetic and the semantic inadequacy (...) of Penrose’s arithmetic. On the other hand, the limitations to our capacity for mechanizing or programming the mind are also indicated, together with two other corollaries of Gödel’s theorems: that we cannot prove that we are consistent, and that we cannot fully describe our notion of a natural number. (shrink)

On the basis of a wide range of historical examples various features of axioms are discussed in relation to their use in mathematical practice. A very general framework for this discussion is provided, and it is argued that axioms can play many roles in mathematics and that viewing them as self-evident truths does not do justice to the ways in which mathematicians employ axioms. Possible origins of axioms and criteria for choosing axioms are also examined. The distinctions introduced aim at (...) clarifying discussions in philosophy of mathematics and contributing towards a more refined view of mathematical practice. (shrink)

This paper is dedicated to Alonzo Church, who died in August 1995 after a long life devoted to logic. To Church we owe lambda calculus, the thesis bearing his name and the solution to the Entscheidungsproblem.His well-known book Introduction to Mathematical LogicI, defined the subject matter of mathematical logic, the approach to be taken and the basic topics addressed. Church was the creator of the Journal of Symbolic Logicthe best-known journal of the area, which he edited for several decades This (...) paper is in three sections. The first is written in journalistic style:the story of the life of AlonzoChurch is told, including some of the many anecdotes I have collected from different sources. The secondpart is devoted to his work, but is far from being exhaustive. The last part is more original; in it I attempto show that Church’s great discovery was lambda calculus and that his remaining contributions weremainly inspired afterthoughts in the sense that most of his contributions as well as some of his pupils derivefrom that initial achievement. Included are Kleene’s Recursion Theory and the completeness proof ofHenkin. I have added an appendix in which is presented the typed lambda calculus and a proof of theundecidability of first-order logic. (shrink)

The paper is devoted to the discussion of some philosophical and historical problems connected with the theorem on the undefinability of the notion of truth. In particular the problem of the priority of proving this theorem will be considered. It is claimed that Tarski obtained this theorem independently though he made clear his indebtedness to Gödel’s methods. On the other hand, Gödel was aware of the formal undefinability of truth in 1931, but he did not publish this result. Reasons for (...) that are also considered. (shrink)

The Institute Vienna Circle held a conference in Vienna in 2003, Cambridge and Vienna a?

Almost everything Turing wrote is now accessible on-line in some form, much of it in the Turing Digital Archive, which makes available scanned versions of the physical papers held in the archive at King's College, Cambridge University. See..

Turing and Church formulated two different formal accounts of computability that turned out to be extensionally equivalent. Since the accounts refer to different properties they cannot both be adequate conceptual analyses of the concept of computability. This insight has led to a discussion concerning which account is adequate. Some authors have suggested that this philosophical debate—which shows few signs of converging on one view—can be circumvented by regarding Church’s and Turing’s theses as explications. This move opens up the possibility that (...) both accounts could be adequate, albeit in their own different ways. In this paper, I focus on the question of whether Church’s thesis can be seen as an explication in the precise Carnapian sense. Most importantly, I address an additional constraint that Carnap puts on the explicative power of axiomatic systems—an axiomatisation explicates when it is clear which mathematical entities form the theory’s intended model—and that implicitly applies to axiomatisations of recursion theory used in Church’s account of computability. To overcome this difficulty, I propose two possible clarifications of the pre-systematic concept of “computability” that can both be captured in recursion theory, and I show how both clarifications avoid an objection arising from Carnap’s constraint. (shrink)

This paper challenges two orthodox theses: (a) that computational processes must be algorithmic; and (b) that all computed functions must be Turing-computable. Section 2 advances the claim that the works in computability theory, including Turing's analysis of the effective computable functions, do not substantiate the two theses. It is then shown (Section 3) that we can describe a system that computes a number-theoretic function which is not Turing-computable. The argument against the first thesis proceeds in two stages. It is first (...) shown (Section 4) that whether a process is algorithmic depends on the way we describe the process. It is then argued (Section 5) that systems compute even if their processes are not described as algorithmic. The paper concludes with a suggestion for a semantic approach to computation. (shrink)

Each science has its own domain of investigation, but one and the same science can be formalized in different languages with different universes of discourse. The concept of the domain of a science and the concept of the universe of discourse of a formalization of a science are distinct, although they often coincide in extension. In order to analyse the presuppositions and implications of choices of domain and universe, this article discusses the treatment of omega arguments in three very different (...) formalizations of arithmetic. In Peano's formalization the domain is a restricted class of individuals, while the universe of discourse is the unrestricted class of all individuals. In Gödel's formalization the domain is a restricted class of individuals as in Peano's formalization, but the universe of discourse coincides with the domain. In Whitehead-Russell's formalization the domain is a class of logical notions in Tarski's sense, that are necessarily not individuals, whereas the universe of discourse is the unrestricted class of individuals as in Peano's formalization. The present approach emphasizes the viewpoint that the universe of discourse of a given discourse is important in determining which propositions are expressed by which sentences. (shrink)

Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ (...) -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity. (shrink)