J. R. Lucas serves warning that he stands ready to refute any sufficiently specific accusation that he is a machine. let any mechanist say, to his face, that he is some particular machine M; Lucas will respond by producing forthwith a suitable Gödel sentence ϕM. Having produced ϕM, he will then argue that — given certain credible premises about himself — he could not have done so if the accusation that he was M had been true. let the mechanist try (...) again; Lucas will counter him again in the same way. It is not possible to accuse Lucas truly of being a machine. (shrink)

The logician Kurt Godel in 1951 established a disjunctive thesis about the scope and limits of mathematical knowledge: either the mathematical mind is equivalent to a Turing machine (i.e., a computer), or there are absolutely undecidable mathematical problems. In the second half of the twentieth century, attempts have been made to arrive at a stronger conclusion. In particular, arguments have been produced by the philosopher J.R. Lucas and by the physicist and mathematician Roger Penrose that intend to show that the (...) mathematical mind is more powerful than any computer. These arguments, and counterarguments to them, have not convinced the logical and philosophical community. The reason for this is an insufficiency if rigour in the debate. The contributions in this volume move the debate forward by formulating rigorous frameworks and formally spelling out and evaluating arguments that bear on Godel's disjunction in these frameworks. The contributions in this volume have been written by world leading experts in the field. (shrink)

_'Nagel and Newman accomplish the wondrous task of clarifying the argumentative outline of Kurt Godel's celebrated logic bomb.'_ _– The Guardian_ In 1931 the mathematical logician Kurt Godel published a revolutionary paper that challenged certain basic assumptions underpinning mathematics and logic. A colleague of physicist Albert Einstein, his theorem proved that mathematics was partly based on propositions not provable within the mathematical system. The importance of Godel's Proof rests upon its radical implications and has echoed throughout many fields, from maths (...) to science to philosophy, computer design, artificial intelligence, even religion and psychology. While others such as Douglas Hofstadter and Roger Penrose have published bestsellers based on Godel’s theorem, this is the first book to present a readable explanation to both scholars and non-specialists alike. A gripping combination of science and accessibility, _Godel’s Proof_ by Nagel and Newman is for both mathematicians and the idly curious, offering those with a taste for logic and philosophy the chance to satisfy their intellectual curiosity. _Kurt Godel_ Born in Brunn, he was a colleague of physicist Albert Einstein and professor at the Institute for Advanced Study in Princeton, N.J. (shrink)

For many decades, the proponents of `artificial intelligence' have maintained that computers will soon be able to do everything that a human can do. In his bestselling work of popular science, Sir Roger Penrose takes us on a fascinating roller-coaster ride through the basic principles of physics, cosmology, mathematics, and philosophy to show that human thinking can never be emulated by a machine.

The articles in this volume represent a part of the philosophical literature on higher-order logic and the Skolem paradox. They ask the question what is second-order logic? and examine various interpretations of the Lowenheim-Skolem theorem.

In this paper Lucas comes back to Gödelian argument against Mecanism to clarify some points. First of all, he explains his use of Gödel’s theorem instead of Turing’s theorem, showing how Gödel’ theorem, but not Turing’s theorem, raises questions concerning truth and reasoning that bear on the nature of mind and how Turing’s theorem suggests that there is something that cannot be done by any computers but not that it can be done by human minds. He considers moreover how Gödel’s (...) theorem can be interpreted as a sophisticated form of the Cretan paradox, posed by Epimenides, able to escape the viciously self-referential nature of the Cretan paradox, and how it can be used against Mechanism as a schema of disproof. Finally, Lucas suggests some answers to the most recurrent criticisms against his argument: criticisms about the implicit idealisation in the way he set up the context between mind and machine; questions concerning modality and finitude, issues of transfinite arithmetic; questions concerning the need of formalizing rational inference and some questions about consistency. (shrink)

Hao Wang was one of the few confidants of the great mathematician and logician Kurt Gödel. _A Logical Journey_ is a continuation of Wang's _Reflections on Gödel_ and also elaborates on discussions contained in _From Mathematics to Philosophy_. A decade in preparation, it contains important and unfamiliar insights into Gödel's views on a wide range of issues, from Platonism and the nature of logic, to minds and machines, the existence of God, and positivism and phenomenology. The impact of Gödel's theorem (...) on twentieth-century thought is on par with that of Einstein's theory of relativity, Heisenberg's uncertainty principle, or Keynesian economics. These previously unpublished intimate and informal conversations, however, bring to light and amplify Gödel's other major contributions to logic and philosophy. They reveal that there is much more in Gödel's philosophy of mathematics than is commonly believed, and more in his philosophy than his philosophy of mathematics. Wang writes that "it is even possible that his quite informal and loosely structured conversations with me, which I am freely using in this book, will turn out to be the fullest existing expression of the diverse components of his inadequately articulated general philosophy." The first two chapters are devoted to Gödel's life and mental development. In the chapters that follow, Wang illustrates the quest for overarching solutions and grand unifications of knowledge and action in Gödel's written speculations on God and an afterlife. He gives the background and a chronological summary of the conversations, considers Gödel's comments on philosophies and philosophers, and his attempt to demonstrate the superiority of the mind's power over brains and machines. Three chapters are tied together by what Wang perceives to be Gödel's governing ideal of philosophy: an exact theory in which mathematics and Newtonian physics serve as a model for philosophy or metaphysics. Finally, in an epilog Wang sketches his own approach to philosophy in contrast to his interpretation of Gödel's outlook. (shrink)

Gödel appears to have believed strongly that the human mind cannot be explained in terms of any kind of computational physics, but he remained cautious in formulating this belief as a rigorous consequence of his incompleteness theorems. In this chapter, I discuss a modification of standard Gödel-type logical arguments, these appearing to strengthen Gödel’s conclusions, and attempt to provide a persuasive case in support of his standpoint that the actions of the mind must transcend computation. It appears that Gödel did (...) not consider the possibility that the laws of physics might themselves involve noncomputational procedures; accordingly, he found himself driven to the conclusion that mentality must lie beyond the actions of the physical brain. My own arguments, on the other hand, are from the scientific standpoint that the mind is a product of the brain’s physical activity. Accordingly, there must be something in the physical actions of the world that itself transcends computation. We do not appear to find such noncomputational action in the known laws of physics, however, so we must seek it in currently undiscovered laws going beyond presently accepted physical theory. I argue that the only plausibly relevant gap in current understanding lies in a fundamental incompleteness in quantum theory, which reveals itself only with significant mass displacements between quantum states (“Schrödinger’s cats”). I contend that the need for new physics enters when gravitational effects just begin to play a role. In a scheme developed jointly with Stuart Hameroff, this has direct relevance within neuronal microtubules, and I describe this (still speculative) scheme in the following. (shrink)

The application of Gödel’s theorem to the problem of minds and machines is difficult. Paul Benacerraf makes the entirely valid ‘Duhemian’ point that the argument is not, and cannot be, a purely mathematical one, but needs some philosophical premisses to be able to yield any philosophical conclusions. Moreover, the philosophical premisses are of very different kinds. Some are concerned with what is essential to being a machine—these are typically intricate, but definite, easily formalised by the mathematician, but unintelligible to the (...) layman: others attempt to capture what is essential to being a mind, a person or a self—these are typically intuitive, but vague; resistant to exact definition by the logician, but, none the less, widely used and well understood. Gödel’s theorem itself, like many other truths, can be taken either way: it can be taken as a formal proof sequence yielding certain syntactical results about a certain class of formal systems, but it can also be taken as giving us a certain type or style of argument, which we can understand, and, once having got the hang of it, adapt and apply in innumerable different circumstances. In my dispute with the mechanist, I take Gödel’s argument both ways: I first take it as an argument which the mechanist, even according to his own mechanist principles, must accept as scoring some point against his favourite machine; and then I hope that the mechanist, as a man, will see that he can do better and that this sort of argument will always apply against any form of mechanism he espouses. (shrink)

This is a critical analysis of the first part of Go¨del’s 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems. Go¨del’s discussion is framed in terms of a distinction between objective mathematics and subjective mathematics, according to which the former consists of the truths of mathematics in an absolute sense, and the latter consists of all humanly demonstrable truths. The question is whether these coincide; if they do, no formal axiomatic system (or Turing machine) can comprehend the mathematizing (...) potentialities of human thought, and, if not, there are absolutely unsolvable mathematical problems of diophantine form. (shrink)

An excellent introduction to mathematical logic, this book provides readers with a sound knowledge of the most important approaches to the subject, stressing the use of logical methods in attacking nontrivial problems. It covers the logic of classes, of propositions, of propositional functions, and the general syntax of language, with a brief introduction that also illustrates applications to so-called undecidability and incompleteness theorems. Other topics include the simple proof of the completeness of the theory of combinations, Church's theorem on the (...) recursive unsolvability of the decision problem for the restricted function calculus, and the demonstrable properties of a formal system as a criterion for its acceptability. 1950 ed. (shrink)

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by (...) Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

A survey of more philosophical applications of Gödel's incompleteness results.

After a brief and informal explanation of the Gödel’s theorem as a version of the Epimenides’ paradox applied to Elementary Number Theory formulated in first-order logic, Lucas shows some of the most relevant consequences of this theorem, such as the impossibility to define truth in terms of provability and so the failure of Verificationist and Intuitionist arguments. He shows moreover how Gödel’s theorem proves that first-order arithmetic admits non-standard models, that Hilbert’s programme is untenable and that second-order logic is not (...) mechanical. There are furthermore some more general consequences: the difference between being reasonable and following a rule and the possibility that one man’s insight differs from another’s without being wrong. Finally some consequences concerning moral and political philosophy can arise from Gödel’s theorem, because it suggests that – instead of some fundamental principle from which all else follows deductively – we can seek for different arguments in different situations. (shrink)

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that (...) initiated by Turing in his “ordinal logics” and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach. (shrink)

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This volume, the sixteenth publication in the Lecture Notes in Logic series, gives a sustained presentation of a particular view of the topic of Gödelian extensions of theories. It presents the basic material in predicate logic, set theory and recursion (...) theory, leading to a proof of Gödel's incompleteness theorems. The inexhaustibility of mathematics is treated based on the concept of transfinite progressions of theories as conceived by Turing and Feferman. All concepts and results are introduced as needed, making the presentation self-contained and thorough. Philosophers, mathematicians and others will find the book helpful in acquiring a basic grasp of the philosophical and logical results and issues. (shrink)

Sections 3.16 and 3.23 of Roger Penrose's Shadows of the mind (Oxford, Oxford University Press, 1994) contain a subtle and intriguing new argument against mechanism, the thesis that the human mind can be accurately modeled by a Turing machine. The argument, based on the incompleteness theorem, is designed to meet standard objections to the original Lucas-Penrose formulations. The new argument, however, seems to invoke an unrestricted truth predicate (and an unrestricted knowability predicate). If so, its premises are inconsistent. The usual (...) ways of restricting the predicates either invalidate Penrose's reasoning or require presuppositions that the mechanist can reject. (shrink)

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging (...) connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine,M, and claims that the output ofMconsists of all and only the arithmetic truths that a human, or the totality of human mathematicians, will ever or can ever know. We assume that the output ofMis consistent. (shrink)

Ernest Nagel Lecture, Columbia University, Sept. 27, 2007.

Presenting a look at the human mind's capacity while criticizing artificial intelligence, the author makes suggestions about classical and quantum physics and ..

It is commonly agreed that the well-known Lucas-Penrose arguments and even Penrose's 'new argument' in [Penrose, R. (1994): Shadows of the Mind, Oxford University Press] are inconclusive. It is, perhaps, less clear exactly why at least the latter is inconclusive. This note continues the discussion in [Lindström, P. (2001): Penrose's new argument, J. Philos. Logic 30, 241-250; Shapiro, S.(2003): Mechanism, truth, and Penrose's new argument, J. Philos. Logic 32, 19-42] and elsewhere of this question.

First published in 1974. Despite the tendency of contemporary analytic philosophy to put logic and mathematics at a central position, the author argues it failed to appreciate or account for their rich content. Through discussions of such mathematical concepts as number, the continuum, set, proof and mechanical procedure, the author provides an introduction to the philosophy of mathematics and an internal criticism of the then current academic philosophy. The material presented is also an illustration of a new, more general method (...) of approach called substantial factualism which the author asserts allows for the development of a more comprehensive philosophical position by not trivialising or distorting substantial facts of human knowledge. (shrink)

In this article, Lucas maintains the falseness of Mechanism - the attempt to explain minds as machines - by means of Incompleteness Theorem of Gödel. Gödel’s theorem shows that in any system consistent and adequate for simple arithmetic there are formulae which cannot be proved in the system but that human minds can recognize as true; Lucas points out in his turn that Gödel’s theorem applies to machines because a machine is the concrete instantiation of a formal system: therefore, for (...) every machine consistent and able of doing simple arithmetic, there is a formula that it can’t produce as true but that we can see to be true, and so human minds and machines have to be different. Lucas considers as well in this article some possible objections to his argument: for any Gödelian formula we could, for instance, construct a machine able to produce it or we could put the Gödelian formulae that we had proved as axioms of a further machine. However - as Lucas underlines - for every of such machines we could again formulate another Gödelian formula, the Gödelian formula of these machines, that they are not able to proof but that we can recognize as true. More general arguments, such as the possibility to escape Gödelian argument by suggesting that Gödel’s theorem applies to consistent systems while we could be inconsistent ones, are moreover refuted by Lucas by maintaining that our inconsistency corresponds to occasional malfunctioning of a machine and not to his normal inconsistency; indeed, a inconsistent machine is characterized by producing any statement, on the contrary human being are selective and not disposed to assert anything. (shrink)

"Among the many expositions of Gödel's incompleteness theorems written for non-specialists, this book stands apart. With exceptional clarity, Franzén gives careful, non-technical explanations both of what those theorems say and, more importantly, what they do not. No other book aims, as his does, to address in detail the misunderstandings and abuses of the incompleteness theorems that are so rife in popular discussions of their significance. As an antidote to the many spurious appeals to incompleteness in theological, anti-mechanist and post-modernist debates, (...) it is a valuable addition to the literature." --- John W. Dawson, author of Logical Dilemmas: The Life and Work of Kurt Gödel. (shrink)

In Infinity and the Mind, Rudy Rucker leads an excursion to that stretch of the universe he calls the "Mindscape," where he explores infinity in all its forms: potential and actual, mathematical and physical, theological and mundane. Here Rucker acquaints us with Gödel's rotating universe, in which it is theoretically possible to travel into the past, and explains an interpretation of quantum mechanics in which billions of parallel worlds are produced every microsecond. It is in the realm of infinity, he (...) maintains, that mathematics, science, and logic merge with the fantastic. By closely examining the paradoxes that arise from this merging, we can learn a great deal about the human mind, its powers, and its limitations. Using cartoons, puzzles, and quotations to enliven his text, Rucker guides us through such topics as the paradoxes of set theory, the possibilities of physical infinities, and the results of Gödel's incompleteness theorems. His personal encounters with Gödel the mathematician and philosopher provide a rare glimpse at genius and reveal what very few mathematicians have dared to admit: the transcendent implications of Platonic realism. (shrink)

It has been argued, by Penrose and others, that Gödel's proof of his first incompleteness theorem shows that human mathematics cannot be captured by a formal system F: the Gödel sentence G(F) of F can be proved by a (human) mathematician but is not provable in F. To this argment it has been objected that the mathematician can prove G(F) only if (s)he can prove that F is consistent, which is unlikely if F is complicated. Penrose has invented a new (...) argument intended to avoid this objection. In the paper I try to show that Penrose's new argument is inconclusive. (shrink)

This book grew out of a graduate student paper [261] in which I set down some criticisms of J. R. Lucas' attempt to refute mechanism by means of G6del's theorem. I had made several such abortive attempts myself and had become familiar with their pitfalls, and especially with the double edged nature of incompleteness arguments. My original idea was to model the refutation of mechanism on the almost universally accepted G6delian refutation of Hilbert's formalism, but I kept getting stuck on (...) questions of mathematical philosophy which I found myself having to beg. A thorough study of the foundational works of Hilbert and Bernays finally convinced me that I had all too naively and uncritically bought this refutation of formalism. I did indeed discover points of surprisingly close contact between formalism and mechanism, but also that it was possible to under mine certain strong arguments against these positions precisely by invok ing G6del's and related work. I also began to realize that the Church Turing thesis itself is the principal bastion protecting mechanism, and that G6del's work was perhaps the best thing that ever happened to both mechanism and formalism. I pushed these lines of argument in my dis sertation with the patient help of my readers, Raymond Nelson and Howard Stein. I would especially like to thank the latter for many valuable criticisms of my dissertation as well as some helpful suggestions for reor ganizing it in the direction of the present book. (shrink)

A young scientist and mathematician explores the mystery and complexity of human thought processes from an interdisciplinary point of view.

PROFESSOR LEWIS 1 and Professor Coder 2 criticize my use of Gödel's theorem to refute Mechanism. 3 Their criticisms are valuable. In order to meet them I need to show more clearly both what the tactic of my argument is at one crucial point and the general aim of the whole manoeuvre.