There are many complex characters in this paper; if you find them difficult to distinguish, you are advised to increase the viewing size.

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

A class of many-sorted polyadic set algebras is introduced. These generalise structure and model in a way that is relevant in regards to the Entscheidungsproblem and to automated reasoning.A downward Löwenheim-Skolem property is shown in that each satisfiable finite conjunction of purely relational first-order prenex sentences has a finite generalised model. This property does, together with a construction related to doubling the size of a finite structure, provide several strict generalisations of the strategy of finite model search for disproving.

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a (...) Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers. (shrink)

This article provides a detailed analysis of the transfer of a key cluster of ideas from mathematical logic to computing. We demonstrate the impact of certain of Turing’s logico-philosophical concepts from the mid-1930s on the emergence of the modern electronic computer—and so, in consequence, Turing’s impact on the direction of modern philosophy, via the computational turn. We explain why both Turing and von Neumann saw the problem of developing the electronic computer as a problem in logic, and we describe their (...) joint journey from logic to electronic computation. While much has been written about Turing’s and von Neumann’s individual contributions to the development of the computer, this article investigates less well-known terrain: their interactions and mutual influences. Along the way we argue against ‘logic skeptics’ and ‘Turing skeptics’, who claim that neither logic nor Turing played any significant role in the creation of the modern computer. (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)

This volume presents an historical and philosophical revisiting of the foundational character of Turing's conceptual contributions and assesses the impact of the work of Alan Turing on the history and philosophy of science. Written by experts from a variety of disciplines, the book draws out the continuing significance of Turing's work. The centennial of Turing's birth in 2012 led to the highly celebrated "Alan Turing Year", which stimulated a world-wide cooperative, interdisciplinary revisiting of his life and work. Turing is widely (...) regarded as one of the most important scientists of the twentieth century: He is the father of artificial intelligence, resolver of Hilbert's famous Entscheidungsproblem, and a code breaker who helped solve the Enigma code. His work revolutionized the very architecture of science by way of the results he obtained in logic, probability and recursion theory, morphogenesis, the foundations of cognitive psychology, mathematics, and cryptography. Many of Turing's breakthroughs were stimulated by his deep reflections on fundamental philosophical issues. Hence it is fitting that there be a volume dedicated to the philosophical impact of his work. One important strand of Turing's work is his analysis of the concept of computability, which has unquestionably come to play a central conceptual role in nearly every branch of knowledge and engineering. (shrink)

The “information age” is often thought in terms of the digital revolution that begins with Turing’s 1937 paper, “On computable numbers, with an application to the Entscheidungsproblem.” However, this can only be partially correct. There are two aspects to Turing’s work: one dealing with questions of computation that leads to computer science and another concerned with building computing machines that leads to computer engineering. Here, we emphasize the latter because it shows us a Turing connected with mechanisms of information (...) flow rather than solely with the mathematical and logical problems of computability for which he is better known. Our reasons for doing so will become clear in what follows. In fact, the 1937 paper just mentioned provides a general schematic for building a computing machine; this mechanical connection puts Turing on an historical continuum with others who discovered mechanisms to cope with information. Of those involved in this quest in the 19th Century, two people in particular, Edison and Bell, had explicit visions of an information age that would follow from their work. Because they were explicitly aware of what they were doing and partly brought it about long before 1937, they deserve substantial credit for the information age they set out to inaugurate. Regarding one purely mechanical and non-electronic technology, Edison noted ten uses for the phonograph, including not only the replication of sound, but also “connection with the telephone, so as to make that instrument an auxiliary in the transmission of permanent and invaluable records, instead of being the recipient of momentary and fleeting communication”. Even though the telephone was only two years old when Edison wrote of a network made up of mechanical hard storage systems and people connected by wire, the network vision was already clearly in his head. (shrink)

This essay accounts for the notion of _Lebensform_ by assigning it a _logical _role in Wittgenstein’s later philosophy. Wittgenstein’s additions of the notion to his manuscripts of the _PI_ occurred during the initial drafting of the book 1936-7, after he abandoned his effort to revise _The Brown Book_. It is argued that this constituted a substantive step forward in his attitude toward the notion of simplicity as it figures within the notion of logical analysis. Next, a reconstruction of his later (...) remarks on _Lebensformen_ is offered which factors in his reading of Alan Turing’s “On computable numbers, with an application to the _Entscheidungsproblem_“, as well as his discussions with Turing 1937-1939. An interpretation of the five occurrences of _Lebensform_ in the PI is then given in terms of a logical “regression” to _Lebensform_ as a fundamental notion. This regression characterizes Wittgenstein’s mature answer to the question, “What is the nature of the logical?”. (shrink)

In his Tractatus Logico-Philosophicus, Wittgenstein conveyed the idea that ethics cannot be located in an object or self-standing subject matter of propositional discourse, true or false. At the same time, he took his work to have an eminently ethical purpose, and his attitude was not that of the emotivist. The trajectory of this conception of the normativity of philosophy as it developed in his subsequent thought is traced. It is explained that and how the notion of a ‘form of life’ (...) (Lebensform) emerged only in his later thought, in 1937, earmarking a significant step forward in his philosophical method. We argue that the concept of Lebensform represents a way of domesticating logic itself, the very idea of a claim or reason, supplementing the idea of a ‘language game’, which it deepens. Lebensform is contrasted with the phenomenologists’ Lebenswelt through a reading of the notions of ‘I’, ‘world’ and ‘self’ as they were treated in the Tractatus, The Blue and Brown Books and Philosophical Investigations. Finally, the notion of Lebensform is shown to have replaced the notion of culture (Kultur) in Philosophical Investigations. Wittgenstein’s spring 1937 ‘domestication’ of the nature of logic is shown to have been fully consonant with the idea that he was influenced by his reading Alan Turing’s 1936/1937 paper, ‘On computable numbers, with an application to the Entscheidungsproblem’. (shrink)

Turing’s famous 1936 paper “On computable numbers, with an application to the Entscheidungsproblem” defines a computable real number and uses Cantor’s diagonal argument to exhibit an uncomputable real. Roughly speaking, a computable real is one that one can calculate digit by digit, that there is an algorithm for approximating as closely as one may wish. All the reals one normally encounters in analysis are computable, like π, √2 and e. But they are much scarcer than the uncomputable reals because, (...) as Turing points out, the computable reals are countable, whilst the uncomputable reals have the power of the continuum. Furthermore, any countable set of reals has measure zero, so the computable reals have measure zero. In other words, if one picks a real at random in the unit interval with uniform probability distribution, the probability of obtaining an uncomputable real is unity. One may obtain a computable real, but that is in- finitely improbable. But how about individual examples of uncomputable reals? We will show two: H and the halting probability Ω, both contained in the unit interval. Their construction was anticipated in.. (shrink)

In the first section of the paper I present Alan Turing’s notion of effective memory, as it appears in his 1936 paper ‘On Computable Numbers, With an Application to The Entscheidungsproblem’. This notion stands in surprising contrast with the way memory is usually thought of in the context of contemporary computer science. Turing’s view (in 1936) is that for a computing machine to remember a previously scanned string of symbols is not to store an internal symbolic image of this (...) string. Rather, memory consists in the fact that the past scanning of the string affects the behavior of the computer in the face of potential future inputs. In the second, central section of the paper I begin exploring how this view of Turing’s bears upon contemporary discussions in the philosophy of mind. In particular, I argue that Turing’s approach can be used to lend support to dispositional conceptions of the propositional attitudes, like the one recently presented by Matthews (2007), and that his effective memory manifests some of the characteristics of Millikan’s (1996) pushmepullyou mental states. (shrink)

This essay discusses Peirce’s appeal to logical machines as an argument against psychologism. It also contends that some of Peirce’s anti-psychologistic remarks on logic contain interesting premonitions arising from his perception of the asymmetry of proof complexity in monadic and relational logical calculi that were only given full formulation and explication in the early twentieth century through Church’s Theorem and Hilbert’s broad-ranging Entscheidungsproblem.

This essay discusses Peirce’s appeal to logical machines as an argument against psychologism. It also contends that some of Peirce’s anti-psychologistic remarks on logic contain interesting premonitions arising from his perception of the asymmetry of proof complexity in monadic and relational logical calculi that were only given full formulation and explication in the early twentieth century through Church’s Theorem and Hilbert’s broad-ranging Entscheidungsproblem.

This paper explores the question of whether or not the law is a computable number in the sense described by Alan Turing in his 1937 paper ‘On computable numbers with an application to the Entscheidungsproblem.’ Drawing upon the legal, social, and political context of Alan Turing’s own involvement with the law following his arrest in 1952 for the criminal offence of gross indecency, the article explores the parameters of computability within the law and analyses the applicability of Turing’s computability (...) thesis within the context of legal decision-making. (shrink)

Wie sollen sich autonome Fahrzeuge verhalten, wenn ein Unfall nicht mehr abwendbar ist? Die Komplexität spezifischer moralischer Dilemmata, die in diesem Kontext auftreten können, lässt bewährte ethische Denktraditionen an ihre Grenzen stoßen. Dieser Aufsatz versteht sich als Versuch, neue Lösungsperspektiven mithilfe einer risikoethischen Sichtweise auf die Problematik zu eröffnen und auf diese Weise deren Relevanz für die Programmierung von ethischen Unfallalgorithmen aufzuzeigen. Im Zentrum steht dabei die Frage, welche Implikationen sich aus einer Auffassung von Dilemma-Situationen als risikoethische Verteilungsprobleme im Hinblick (...) auf die Zulässigkeit von entsprechenden Risikoübertragungen ergeben. Dabei wird zunächst eine risikoethische Interpretation des zugrundeliegenden Entscheidungsproblems skizziert, welches durch seine dilemmatische Struktur eine besondere Risikokonstellation begründet. Ausgehend von den Positionen von Sven Ove Hansson und Julian Nida-Rümelin wird für einen deontologisch-risikoethischen Ansatz argumentiert, der auf Individualrechten einerseits und einer interpersonell gerechten Verteilung der entstehenden Schadensrisiken anderseits basiert. Diese beiden Kriterien werden für den Anwendungskontext des autonomen Fahrens konkretisiert. Zum einen wird in Bezug auf das erste Kriterium argumentiert, dass individuelle Rechte genau dann als angemessen gewahrt gelten können, wenn die resultierenden Risikoübertragungen auf die Einzelnen in ihrer absoluten Höhe jeweils zumutbar sind. Zum anderen werden Schwierigkeiten skizziert, die sich hinsichtlich der konkreten Umsetzung des zweiten Kriteriums der Verteilungsgerechtigkeit ergeben. In diesem Zusammenhang werden beispielsweise ethische Herausforderungen in Bezug auf einen möglichen Vorteilsausgleich, das Prinzip der Schadensminimierung sowie individuell unterschiedliche Ausgangsbedingungen der persönlichen Schadensreduktion kritisch in den Blick genommen. (shrink)

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

An investigation of the concept of “surveyability” as traced through the thought of Hilbert, Wittgenstein, and Turing. The communicability and reproducibility of proof, with certainty, are seen as earmarked by the “surveyability” of symbols, sequences, and structures of proof in all these thinkers. Hilbert initiated the idea within his metamathematics, Wittgenstein took up a kind of game formalism in the 1920s and early 1930s in response. Turing carried Hilbert’s conception of the “surveyability” of proof in metamathematics through into his analysis (...) of what a formal system (what a step in a computation) is in “On computable numbers, with an application to the Entscheidungsproblem” (1936). Wittgenstein’s 1939 investigations of the significance of surveyability to the concept of “proof “in Principia Mathematica were influenced, both by Turing’s remarkable everyday analysis of the Hilbertian idea, and by conversations with Turing. Although Turing does not use the word “surveyability” explicitly, it is clear that the Hilbertian idea plays a recurrent role in his work, refracted through his engagement with Wittgenstein’s idea of a “language-game”. This is evinced in some of his later writings, where the “reform” of mathematical notation for the sake of human surveyability (1944/45) may be seen to draw out the Hilbertian idea. For Turing, as for Wittgenstein, the need for “surveyability” earmarks the evolving culture of humans located in an evolving social and scientific world, just as it had for Hilbert. (shrink)