In “Minds, Machines, and Gödel”, J. R. Lucas claims that Goedel's incompleteness theorem constitutes a proof “that Mechanism is false, that is, that minds cannot be explained as machines”. He claims further that “if the proof of the falsity of mechanism is valid, it is of the greatest consequence for the whole of philosophy”. It seems to me that both of these claims are exaggerated. It is true that no minds can be explained as machines. But it is not true (...) that Goedel's theorem proves this. At most, Goedel's theorem proves that not all minds can be explained as machines. Since this is so, Goedel's theorem cannot be expected to throw much light on why minds are different from machines. Lucas overestimates the importance of Goedel's theorem for the topic of mechanism, I believe, because he presumes falsely that being unable to follow any but mechanical procedures in mathematics makes something a machine. (shrink)

Lucas and Penrose have contended that, by displaying how any characterisation of arithmetical proof programmable into a machine allows of diagonalisation, generating a humanly recognisable proof which eludes that characterisation, Gödel's incompleteness theorem rules out any purely mechanical model of the human intellect. The main criticisms of this argument have been that the proof generated by diagonalisation (i) will not be humanly recognisable unless humans can grasp the specification of the object-system (Benacerraf); and (ii) counts as a proof only on (...) the (unproven) hypothesis that the object system is consistent (Putnam). The present paper argues that criticism (ii) may be met head-on by an intuitionistic proponent of the anti-mechanist argument; and that criticism (i) is simply mistaken. However the paper concludes by questioning the sufficiency of the situation for an interesting anti-mechanist conclusion. (shrink)

We propose that the sudden emergence of metazoans during the Cambrian was due to the appearance of a complex genome architecture that was capable of computing. In turn, this made defining recursive functions possible. The underlying molecular changes that occurred in tandem were driven by the increased probability of maintaining duplicated DNA fragments in the metazoan genome. In our model, an increase in telomeric units, in conjunction with a telomerase-negative state and consequent telomere shortening, generated a reference point equivalent to (...) a non-reversible counting mechanism. (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)

This paper reassesses the criticism of the Lucas-Penrose anti-mechanist argument, based on Gödel’s incompleteness theorems, as formulated by Krajewski : this argument only works with the additional extra-formal assumption that “the human mind is consistent”. Krajewski argues that this assumption cannot be formalized, and therefore that the anti-mechanist argument – which requires the formalization of the whole reasoning process – fails to establish that the human mind is not mechanistic. A similar situation occurs with a corollary to the argument, (...) that the human mind allegedly outperforms machines, because although there is no exhaustive formal definition of natural numbers, mathematicians can successfully work with natural numbers. Again, the corollary requires an extra-formal assumption: “PA is complete” or “the set of all natural numbers exists”. I agree that extra-formal assumptions are necessary in order to validate the anti-mechanist argument and its corollary, and that those assumptions are problematic. However, I argue that formalization is possible and the problem is instead the circularity of reasoning that they cause. The human mind does not prove its own consistency, and outperforms the machine, simply by making the assumption “I am consistent”. Starting from the analysis of circularity, I propose a way of thinking about the interplay between informal and formal in mathematics. (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)

This book uses the friendly format of the computing language Prolog to teach a full formal predicate logic. With Prolog, the scope and limits of both logic and computing can be explored and experimented. Students learning formal logic in a Prolog format can begin using their already developed informal abilities in logic to program in Prolog and conversely learn enough formal logic to examine Prolog and computing in general so major fundamental theorems can be demonstrated. Cases such as Church's Thesis, (...) Church's Theorem, Turing's Halting Problem, and Godel's Incompleteness Theorem provide the author with the means to assess some of the philosophical implications of logic and computing. Henry designed the book for undergraduate students, but it is also useful for philosophers and theologians who wish to see how computer programming serves as a probe into philosophical matters. Contents: The Formalization of Logic; Propositional Logic; Predicate Logic; Prolog: Programming in Logic; Logic Machines; The Scope and Limits of Logic and Logic Machines; Philosophical Reflections; Appendix; Bibliography; Index. (shrink)

We argue that Löb's Theorem implies a limitation on mechanism. Specifically, we argue, via an application of a generalized version of Löb's Theorem, that any particular device known by an observer to be mechanical cannot be used as an epistemic authority (of a particular type) by that observer: either the belief-set of such an authority is not mechanizable or, if it is, there is no identifiable formal system of which the observer can know (or truly believe) it to be the (...) theorem-set. This gives, we believe, an important and hitherto unnoticed connection between mechanism and the use of authorities by human-like epistemic agents. (shrink)

SummaryJ.R. Lucas has argued that it follows from Godel's Theorem that the mind cannot be a machine or represented by any formal system. Although this notorious argument against the mechanism thesis has received considerable attention in the literature, it has not been decisively rebutted, even though mechanism is generally thought to be the only plausible view of the mind. In this paper I offer an analysis of Lucas's argument which shows that it derives its persuasiveness from a subtle confusion. In (...) particular, I examine Benacerraf's reconstruction of Lucas's argument, thereby permitting a precise re‐statement of my own analysis and reinforcement of my conclusions regarding Lucas's mistake. This examination of Benacerraf's reconstruction permits us to evaluate certain radical and highly paradoxical conclusions concerning empirical psychology which Benacerraf draws, and this, in turn, permits us to consider certain suggestive implications for the mind which may, after all, follow from Godel's Theorem.RésuméJ.R. Lucas a dérivé du théorème de Gödel la conclusion que ľesprit ne peut pas être une machine ou être représenté par un systeme formel. Bien que cet argument célèbre contre la thése du mécanisme ait éveillé un interêt considérable dans la littérature, il ňa pas été réfuté de façon décisive, même si ľopinion générate prévaut que le mécanisme est la seule conception possible de ľesprit. Dans cet article, je propose une analyse du raisonnement de Lucas qui montre que sa force persuasive provient ?on;une subtile confusion. En particulier, j'examine la reconstruction, par Benacerraf, de la démonstration de Lucas, ce qui me pérmet de préciser ma propre analyse et de confirmer mes conclusions quant àľerreur de Lucas. Cet examen de la reconstruction de Benacerraf nous fournit ľoccasion de discuter certaines conclusions radicales et hautement paradoxals qu'il en tire concernant la psychologie expérimentale et nous conduit à certaines implications suggestives concernant ľesprit et qui pourraient finalement decouler du théorème de Gödel.ZusammenfassungJ.R. Lucas hat argumentiert, aus Gödels Theorem mUsse folgen, dass der menschliche Geist keine Maschine sein oder durch ein formales System dargestellt werden kann. Obschon dieses bekannte Argument gegen die mechanistische These in der Literatur beträchtliche Beachtung gefunden hat, ist es bisher noch nie eigentlich widerlegt worden, obgleich eine mechanistische Betrachtungsweise allgemein als die einzig plausible gilt. In dieser Arbeit biete ich eine Analyse von Lucas Argument an, die zeigen soil, dass seine Überzeugungskraft auf einer subtilen Konfusion beruht. Im besonderen untersuche ich Benacerrafs Rekonstruktion des Arguments, was rnirerlaubt, meine eigene Analyse in genauer Weise zu formulieren und meine Schlussfolgerung bezüglich des von Lucas gemachten Fehlers zu erharten. Diese Untersuchung von Benacerrafs Rekonstruktion ermöglicht es, gewisse radikale und im höchsten Grad paradoxe Schlüsse, die Benacerraf hinsichtlich der empirischen Psychologie zieht, zu beurteilen. Das wiederum erlaubt uns, gewisse den Geist betreffende Implikationen zu erörtern, die tatsächlich aus Gödels Theorem folgen kUnnten. (shrink)

The aim of this paper is to argue about the impossibility of constructing a complete formal theory or a complete Turing machines' algorithm that represent the human capacity of recognizing mathematical truths. More specifically, based on a direct argument from Gödel's First Incompleteness Theorem, we discuss the impossibility of constructing a complete formal theory or a complete Turing machines' algorithm to the human capacity of recognition of first-order arithmetical truths and so of mathematical truths in general.

Gödel's Theorem is often used in arguments against machine intelligence, suggesting humans are not bound by the rules of any formal system. However, Gödelian arguments can be used to support AI, provided we extend our notion of computation to include devices incorporating random number generators. A complete description scheme can be given for integer functions, by which nonalgorithmic functions are shown to be partly random. Not being restricted to algorithms can be accounted for by the availability of an arbitrary random (...) function. Humans, then, might not be rule-bound, but Gödelian arguments also suggest how the relevant sort of nonalgorithmicity may be trivially made available to machines. (shrink)

In Philosophy for April 1961 Mr J. R. Lucas argues that Gödel's theorem proves that Mechanism is false. I wish to dispute this view, not because I maintain that Mechanism is true, but because I do not believe that this issue is to be settled by what looks rather like a kind of logical conjuring-trick. In my discussion I take for granted Lucas's account of Gödel's procedure, which I am not competent to criticise.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We first discuss Michael Dummett’s philosophy of mathematics and Robert Brandom’s philosophy of language to demonstrate that inferentialism entails the falsity of Church’s Thesis and, as a consequence, the Computational Theory of Mind. This amounts to an entirely novel critique of mechanism in the philosophy of mind, one we show to have tremendous advantages over the traditional Lucas-Penrose argument.

Storrs McCall continues the tradition of Lucas and Penrose in an attempt to refute mechanism by appealing to Gödel’s incompleteness theorem. That is, McCall argues that Gödel’s theorem “reveals a sharp dividing line between human and machine thinking”. According to McCall, “[h]uman beings are familiar with the distinction between truth and theoremhood, but Turing machines cannot look beyond their own output”. However, although McCall’s argumentation is slightly more sophisticated than the earlier Gödelian anti-mechanist arguments, in the end (...) it fails badly, as it is at odds with the logical facts. (shrink)

It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with (...) Gödel’s results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines. (shrink)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that (...) all physical systems can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

Van Lambalgen's Theorem plays an important role in algorithmic randomness, especially when studying relative randomness. In this paper we extend van Lambalgen's Theorem by considering the join of infinitely many reals which are random relative to each other. In addition, we study computability of the reals in the range of Omega operators. It is known that $\Omega^{\phi'}$ is high. We extend this result to that $\Omega^{\phi^{(n)}}$ is $\textrm{high}_n$ . We also prove that there exists A such that, for each n (...) , the real $\Omega^A_M$ is $\textrm{high}_n$ for some universal Turing machine M by using the extended van Lambalgen's Theorem. (shrink)

Alan Turing anticipated many areas of current research incomputer and cognitive science. This article outlines his contributionsto Artificial Intelligence, connectionism, hypercomputation, andArtificial Life, and also describes Turing's pioneering role in thedevelopment of electronic stored-program digital computers. It locatesthe origins of Artificial Intelligence in postwar Britain. It examinesthe intellectual connections between the work of Turing and ofWittgenstein in respect of their views on cognition, on machineintelligence, and on the relation between provability and truth. Wecriticise widespread and influential misunderstandings (...) of theChurch–Turing thesis and of the halting theorem. We also explore theidea of hypercomputation, outlining a number of notional machines thatcompute the uncomputable. (shrink)

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

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)

We propose here an extension of Rice's Theorem to first-order logic, proven by totally elementary means. If P is any property defined over the collection of all first-order theories and P is non-trivial over the set of finitely axiomatizable theories , then P is undecidable. This not only means that the problem of deciding properties of first-order theories is as hard as the problem of deciding properties about languages accepted by Turing machines, but also offers a general setting for (...) proving several undecidability results in first-order theories. (shrink)

soft servants of durable material: they live without pretension in complicated relays and electrical circuits. Speed, docility are their strength. One asks: “What is 2 × 2?”—“Are you a machine?” They answer or refuse to answer, depending on what you demand. There are, however, other machines as well, more abstract automatons, bolder and more inaccessible, which eat their tape in mathematical formulae. They imitate in language. In infinite loops, farther and farther back in their retreat towards more subtle algorithms, more (...) recursive functions. They are logical and describe themselves. As when a man with a hand-mirror pressed against his nose in front of a mirror sees in infinite rows the same image multiplied in a shrinking, darkening corridor of glass. It is a Gödel theorem as good as any. He sees infinity, but what he does not see is his face. (From Göran Printz-Påhlson´s poem “The Turing Machine” published in Säg minns du skeppet Refanut? Samlade dikter 1950–1983 (1984) Bonniers, Stockholm). (shrink)

I live just off of Bell Road outside of Newburgh, Indiana, a small town of 3,000 people. A mile down the street Bell Road intersects with Telephone Road not as a modern reminder of a technology belonging to bygone days, but as testimony that this technology, now more than a century and a quarter old, is still with us. In an age that prides itself on its digital devices and in which the computer now equals the telephone as a medium (...) of communication, it is easy to forget the debt we owe to an era that industrialized the flow of information, that the light bulb, to pick a singular example, which is useful for upgrading visual information we might otherwise overlook, nonetheless remains the most prevalent of all modern day information technologies. Edison’s light bulb, of course, belongs to a different order of informational devices than the computer, but not so the telephone, not entirely anyway. Alan Turing, best known for his work on the Theory of Computation (1937), the Turing Machine (also 1937) and the Turing Test (1950), is often credited with being the father of computer science and the father of artificial intelligence. Less well-known to the casual reader but equally important is his work in computer engineering. The following lecture on the Automatic Computing Engine, or ACE, shows Turing in this different light, as a mechanist concerned with getting the greatest computational power from minimal hardware resources. Yet Turing’s work on mechanisms is often eclipsed by his thoughts on computability and his other theoretical interests. This is unfortunate for several reasons, one being that it obscures our picture of the historical trajectory of information technology, a second that it emphasizes a false dichotomy between “hardware” and “software” to which Turing himself did not ascribe but which has, nonetheless, confused researchers who study the nature of mind and intelligence for generations.. (shrink)

Mahadevan (2018, AAAI Conference. https://people.cs.umass.edu/~mahadeva/papers/aaai2018-imagination.pdf) proposes that we are at the cusp of imagination science, one of whose primary concerns will be the design of imagination machines. Programs have been written that are capable of generating jokes (Kim Binsted’s JAPE), producing line-drawings that have been exhibited at such galleries as the Tate (Harold Cohen’s AARON), composing music in several styles reminiscent of such greats as Vivaldi and Mozart (David Cope’s Emmy), proving geometry theorems (Herb Gelernter’s IBM program), and inducing quantitative (...) laws from empirical data (Pat Langley, Gary Bradshaw, Jan Zytkow, and Herbert Simon’s BACON). In recent years, Dartmouth has been hosting Turing Tests in creativity in three categories: short stories, sonnets, and dance music DJ sets. In this post, I will provide a brief and non-exhaustive survey of some plausible responses to these imagination machines and the related prospects for our understanding of the imagination. (shrink)

Penrose proved that a computational or formalizable theory of the brainís cognitive functioning is impossible, but suggested that a physical non-computational and non-formalizable one may be viable. Arguments as to why Penroseís program is unrealizable are presented. The main argument is that a non-formalizable theory should be verbal. However, verbal paradoxes based on Cantorís diagonal processes show the impossibility of a consistent verbal theory of the brain comprising its arithmetical cognition. It is suggested that comprehensive theories of the human brain (...) and of physical experience are Kantian rather than Platonic ideas. This suggestion is likewise based on arguments related to diagonal processes. (shrink)

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)

In the paper some applications of Gödel's incompleteness theorems to discussions of problems of computer science are presented. In particular the problem of relations between the mind and machine (arguments by J.J.C. Smart and J.R. Lucas) is discussed. Next Gödel's opinion on this issue is studied. Finally some interpretations of Gödel's incompleteness theorems from the point of view of the information theory are presented.

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)

The paper discusses some of the poorly explored links between the conceptual systems of logic in Kurt Gödel, the theory of automata in Alan Turing, and the theory of self-reproducing automata in John von Neumann. Traditional controversies are left aside (especially the opposition of Gödel and Turing in the view of mind) and attention is focused on the similarities between all three authors. In individual chapters, the text deals with: the form of differentiation of syntax and semantics in (...) formal system in Gödel, Turing and von Neumann; von Neumann’s variant of Gödel’s theorem and von Neumann’s and Gödel’s conception of Turing machine; and finally the same basis of the view of the relation between mind and automaton in all three authors. (shrink)

This paper reveals two fallacies in Turing's undecidability proof of first-order logic (FOL), namely, (i) an 'extensional fallacy': from the fact that a sentence is an instance of a provable FOL formula, it is inferred that a meaningful sentence is proven, and (ii) a 'fallacy of substitution': from the fact that a sentence is an instance of a provable FOL formula, it is inferred that a true sentence is proven. The first fallacy erroneously suggests that Turing's proof of (...) the non-existence of a circle-free machine that decides whether an arbitrary machine is circular proves a significant proposition. The second fallacy suggests that FOL is undecidable. (shrink)

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.

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n L(F ). The proof resembles Berry’s..

The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be good measure of (...) the strength of the theory. I exhibit certain strong counterexamples and establish conclusively that the received view is false. Moreover, I show that the limiting constants provided by the theorem do not in any way reflect the power of formalized theories, but that the values of these constants are actually determined by the chosen coding of Turing machines, and are thus quite accidental. (shrink)

This paper presents, from a historical and logical-philosophical perspective, the Gödelian arguments of two Oxford scholars, John Lucas and Roger Penrose. Both have been based on Gödel's Theorem to refute mechanism, computationalism and the possibility of creating an AI capable of simulating or duplicating the human mind. In the conclusions, the growing application of empirical methods in mathematics is mentioned and a possible path that would support Lucas and Penrose's arguments is speculated.

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize (...) the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory. (shrink)

Gödel's theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines. So also has it seemed to many other people: almost every mathematical logician I have put the matter to has confessed to similar thoughts, but has felt reluctant to commit himself definitely until he could see the whole argument set out, with all objections fully stated and properly met.1 This I attempt to do.

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)

The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. (...) class='Hi'>Turing admits that non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind. (shrink)

1936 was a watershed year for computability. Debates among Gödel, Church and others over the correct analysis of the intuitive concept “human effectively computable”, an analysis at the heart of the Incompleteness Theorems, the Entscheidungsproblem, the question of what a finite computation is, and most urgently—for Gödel—the generality of the Incompleteness Theorems, were definitively set to rest with the appearance, in that year, of the Turing Machine. The question I explore here is, do the mathematical facts exhaust what is (...) to be said about the thinking behind the “confluence of ideas in 1936”? I will argue for a cultural role in Gödel’s, and, by extension, the larger logical community’s absorption of Turing’s 1936 model. As scaffolding I employ a conceptual framework due to the critic Leo Marx of the technological sublime; I also make use of the distinction within the technological sublime due to Caroline Jones, between its iconic and performative modes—a distinction operating within the conceptual art of the 1960s, but serving the history of computability equally well. (shrink)

Let$\left\langle {{W_n}:n \in \omega } \right\rangle$be a canonical enumeration of recursively enumerable sets, and supposeTis a recursively enumerable extension of PA (Peano Arithmetic) in the same language. Woodin (2011) showed that there exists an index$e \in \omega$(that depends onT) with the property that if${\cal M}$is a countable model ofTand for some${\cal M}$-finite sets,${\cal M}$satisfies${W_e} \subseteq s$, then${\cal M}$has an end extension${\cal N}$that satisfiesT+We=s.Here we generalize Woodin’s theorem to all recursively enumerable extensionsTof the fragment${{\rm{I}\rm{\Sigma }}_1}$of PA, and remove the countability restriction (...) on${\cal M}$whenTextends PA. We also derive model-theoretic consequences of a classic fixed-point construction of Kripke (1962) and compare them with Woodin’s theorem. (shrink)

The thesis of the paper is that semiotic processes are intrinsic to computation and computational systems. An explanation of computation that does not take this semiotic dimension into account is incomplete. Semiosis is essential to computation and therefore requires a rigorous definition. To prove this thesis, the author analyzes two concepts of computation: the Turing machine and the mechanistic conception of physical computation. The paper is organized in two parts. The first part (Sects. 2 and 3) develops a re-interpretation (...) of the Turing machine starting from Peirce’s semiotics. The author shows how this reinterpretation allows overcoming the dualism between a purist and a realist version of the Turing machine. The second part of the paper (Sect. 4) shows how a mechanistic explanation of physical computation such as the one developed by Piccinini is incomplete without considering semiotic relations. The paper intends to be a contribution to the philosophical debate on computation. (shrink)