I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer (...) to the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (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 Turingmachines. But as there has been theorisation (...) that all physical systems can be represented by Turingmachines, 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)
Accelerating Turingmachines have attracted much attention in the last decade or so. They have been described as the work-horse of hypercomputation (Potgieter and Rosinger 2010: 853). But do they really compute beyond the Turing limit —e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that (...) in the current literature the term accelerating Turing machine is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turingmachines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical. (shrink)
Accelerating Turingmachines are Turingmachines of a sort able to perform tasks that are commonly regarded as impossible for Turingmachines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turingmachines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of (...) effective procedures and the theoretical limits of computability. Contrary to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)
Infinite time Turingmachines extend the operation of ordinary Turingmachines 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.
Storrs McCall appeals to a particular true but improvable sentence of formal arithmetic to argue, by appeal to its irrefutability, that human minds transcend Turingmachines. Metamathematical oversights in McCall's discussion of the Godel phenomena, however, render invalid his philosophical argument for this transcendentalist conclusion.
Infinite time Turingmachines extend the operation of ordinary Turingmachines 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.
Accelerated Turingmachines are Turingmachines that perform tasks commonly regarded as impossible, such as computing the halting function. The existence of these notional machines has obvious implications concerning the theoretical limits of computability.
The tape is divided into squares, each square bearing a single symbol—'0' or '1', for example. This tape is the machine's general-purpose storage medium: the machine is set in motion with its input inscribed on the tape, output is written onto the tape by the head, and the tape serves as a short-term working memory for the results of intermediate steps of the computation. The program governing the particular computation that the machine is to perform is also stored on the (...) tape. A small, fixed program that is 'hard-wired' into the head enables the head to read and execute the instructions of whatever program is on the tape. The machine's atomic operations are very simple—for example, 'move left one square', 'move right one square', 'identify the symbol currently beneath the head', 'write 1 on the square that is beneath the head', and 'write 0 on the square that is beneath the head'. Complexity of operation is achieved by the chaining together of large numbers of these simple atoms. Any universal Turing machine can be programmed to carry out any calculation that can be performed by a human mathematician working with paper and pencil in accordance with some algorithmic method. This is what is meant by calling these machines 'universal'. (shrink)
In his PhD thesis (1938) Turing introduced what he described as 'a new kind of machine'. He called these 'O-machines'. The present paper employs Turing's concept against a number of currently fashionable positions in the philosophy of mind.
According to the conventional wisdom, Turing (1950) said that computing machines can be intelligent. I don''t believe it. I think that what Turing really said was that computing machines –- computers limited to computing –- can only fake intelligence. If we want computers to become genuinelyintelligent, we will have to give them enough initiative (Turing, 1948, p. 21) to do more than compute. In this paper, I want to try to develop this idea. I want (...) to explain how giving computers more ``initiative'''' can allow them to do more than compute. And I want to say why I believe (and believe that Turing believed) that they will have to go beyond computation before they can become genuinely intelligent. (shrink)
The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other (...) kind of effective procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1). (shrink)
``Neural computing'' is a research field based on perceiving the human brain as an information system. This system reads its input continuously via the different senses, encodes data into various biophysical variables such as membrane potentials or neural firing rates, stores information using different kinds of memories (e.g., short-term memory, long-term memory, associative memory), performs some operations called ``computation'', and outputs onto various channels, including motor control commands, decisions, thoughts, and feelings. We show a natural model of neural computing that (...) gives rise to hyper-computation. Rigorous mathematical analysis is applied, explicating our model's exact computational power and how it changes with the change of parameters. Our analog neural network allows for supra-Turing power while keeping track of computational constraints, and thus embeds a possible answer to the superiority of the biological intelligence within the framework of classical computer science. We further propose it as standard in the field of analog computation, functioning in a role similar to that of the universal Turing machine in digital computation. In particular an analog of the Church-Turing thesis of digital computation is stated where the neural network takes place of the Turing machine. (shrink)
It has been argued that neural networks and other forms of analog computation may transcend the limits of Turing-machine computation; proofs have been offered on both sides, subject to differing assumptions. In this article I argue that the important comparisons between the two models of computation are not so much mathematical as epistemological. The Turing-machine model makes assumptions about information representation and processing that are badly matched to the realities of natural computation (information representation and processing in or (...) inspired by natural systems). This points to the need for new models of computation addressing issues orthogonal to those that have occupied the traditional theory of computation. (shrink)
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.
This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turingmachines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the (...) capability of human or machine, but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems. (shrink)
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.
We propose the notion of partial recursiveness and strong partial recursiveness for fuzzy maps. We prove that a fuzzy map f is partial recursive if and only if it is computable by a Turing fuzzy machine and that f is strongly partial recursive and deterministic if and only if it is computable via a deterministic Turing fuzzy machine. This gives a simple and manageable tool to investigate about the properties of the fuzzy machines.
This is the first of two volumes of essays in commemoration of Alan Turing, whose pioneering work in the theory of artificial intelligence and computer science continues to be widely discussed today. A group of prominent academics from a wide range of disciplines focus on three questions famously raised by Turing: What, if any, are the limits on machine 'thinking'? Could a machine be genuinely intelligent? Might we ourselves be biological machines, whose thought consists essentially in nothing (...) more than the interaction of neurons according to strictly determined rules? The discussion of these fascinating issues is accessible to non-specialists and stimulating for all readers. -/- Also available in paperback is the companion volume: Connectionism, Concepts, and Folk Psychology, edited by Andy Clark and Peter Millican. While Volume 1 concentrates on Turing's main innovations in artificial intelligence, Volume 2 looks more broadly at his intellectual legacy in philosophy and cognitive science. (shrink)
The TuringTest (TT), as originally specified, centres on theability to perform a social role. The TT can be seen as a test of anability to enter into normal human social dynamics. In this light itseems unlikely that such an entity can be wholly designed in anoff-line mode; rather a considerable period of training insitu would be required. The argument that since we can pass the TT,and our cognitive processes might be implemented as a Turing Machine(TM), (...) that consequently a TM that could pass the TT could be built, isattacked on the grounds that not all TMs are constructible in a plannedway. This observation points towards the importance of developmentalprocesses that use random elements (e.g., evolution), but in these casesit becomes problematic to call the result artificial. This hasimplications for the means by which intelligent agents could bedeveloped. (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)
In my book How the Mind Works, I defended the theory that the human mind is a naturally selected system of organs of computation. Jerry Fodor claims that 'the mind doesn't work that way'(in a book with that title) because (1) TuringMachines cannot duplicate humans' ability to perform abduction (inference to the best explanation); (2) though a massively modular system could succeed at abduction, such a system is implausible on other grounds; and (3) evolution adds nothing to (...) our understanding of the mind. In this review I show that these arguments are flawed. First, my claim that the mind is a computational system is different from the claim Fodor attacks (that the mind has the architecture of a Turing Machine); therefore the practical limitations of TuringMachines are irrelevant. Second, Fodor identifies abduction with the cumulative accomplishments of the scientific community over millennia. This is very different from the accomplishments of human common sense, so the supposed gap between human cognition and computational models may be illusory. Third, my claim about biological specialization, as seen in organ systems, is distinct from Fodor's own notion of encapsulated modules, so the limitations of the latter are irrelevant. Fourth, Fodor's arguments dismissing of the relevance of evolution to psychology are unsound. (shrink)
Turing's celebrated 1950 paper proposes a very general methodological criterion for modelling mental function: total functional equivalence and indistinguishability. His criterion gives rise to a hierarchy of Turing Tests, from subtotal ("toy") fragments of our functions (t1), to total symbolic (pen-pal) function (T2 -- the standard Turing Test), to total external sensorimotor (robotic) function (T3), to total internal microfunction (T4), to total indistinguishability in every empirically discernible respect (T5). This is a "reverse-engineering" hierarchy of (decreasing) empirical underdetermination (...) of the theory by the data. Level t1 is clearly too underdetermined, T2 is vulnerable to a counterexample (Searle's Chinese Room Argument), and T4 and T5 are arbitrarily overdetermined. Hence T3 is the appropriate target level for cognitive science. When it is reached, however, there will still remain more unanswerable questions than when Physics reaches its Grand Unified Theory of Everything (GUTE), because of the mind/body problem and the other-minds problem, both of which are inherent in this empirical domain, even though Turing hardly mentions them. (shrink)
Church's thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive. A related thesis asserts that Turing's work yields a conceptual analysis of the intuitive notion of numerical computability. I endorse Church's thesis, but I argue against the related thesis. I argue that purported conceptual analyses based upon Turing's work involve a subtle but persistent circularity. Turingmachines manipulate syntactic entities. To specify which number-theoretic function a Turing machine computes, (...) we must correlate these syntactic entities with numbers. I argue that, in providing this correlation, we must demand that the correlation itself be computable. Otherwise, the Turing machine will compute uncomputable functions. But if we presuppose the intuitive notion of a computable relation between syntactic entities and numbers, then our analysis of computability is circular. (shrink)
We claim that a recent article of P. Cotogno ([2003]) in this journal is based on an incorrect argument concerning the non-computability of diagonal functions. The point is that whilst diagonal functions are not computable by any function of the class over which they diagonalise, there is no ?logical incomputability? in their being computed over a wider class. Hence this ?logical incomputability? regrettably cannot be used in his argument that no hypercomputation can compute the Halting problem. This seems to lead (...) him into a further error in his analysis of the supposed conventional status of the infinite time Turingmachines of Hamkins and Lewis ([2000]). Theorem 1 refutes this directly. The diagonalisation misunderstanding Infinite computation Conclusion. (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)
Some of the papers in this special issue distribute cognition between what is going on inside individual cognizers' heads and their outside worlds; others distribute cognition among different individual cognizers. Turing's criterion for cognition was individual, autonomous input/output capacity. It is not clear that distributed cognition could pass the TuringTest.
After proposing the Turing Test, Alan Turing himself considered a number of objections to the idea that a machine might eventually pass it. One of the objections discussed by Turing was that no machine will ever pass the Turing Test because no machine will ever “have as much diversity of behaviour as a man”. He responded as follows: the “criticism that a machine cannot have much diversity of behaviour is just a way of saying that it (...) cannot have much storage capacity”. I shall argue that the objection cannot be dismissed so easily. The diversity exhibited by human behaviour is characterized by a kind of context-sensitive adaptive plasticity. Most of the time, human beings flexibly and fluently respond to what is relevant in a given situation. Moreover, ordinary human life involves an open-ended flow of shifting contexts to which our behaviour typically adapts in real time. For a machine to “have as much diversity of behaviour as a man” would be for that machine to keep its responses and behaviour relevant within such a flow. Merely giving a machine the capacity to store a huge amount of information and an enormous number of behaviour-generating rules will not achieve this goal. By drawing on arguments presented originally by Descartes, and by making contact with the frame problem in artificial intelligence, I shall argue that the distinctive context-sensitive adaptive plasticity of human behaviour explains why the Turing Test is such a stringent test for the presence of thought, and why it is much harder to pass than Turing himself may have realized. (shrink)
We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.
In the technical literature of computer science, the concept of an effective procedure is closely associated with the notion of an instruction that precisely specifies an action. Turing machine instructions are held up as providing paragons of instructions that "precisely describe" or "well define" the actions they prescribe. Numerical algorithms and computer programs are judged effective just insofar as they are thought to be translatable into Turing machine programs. Nontechnical procedures (e.g., recipes, methods) are summarily dismissed as ineffective (...) on the grounds that their instructions lack the requisite precision. But despite the pivotal role played by the notion of a precisely specified instruction in classifying procedures as effective and ineffective, little attention has been paid to the manner in which instructions "precisely specify" the actions they prescribe. It is the purpose of this paper to remedy this defect. The results are startling. The reputed exemplary precision of Turing machine instructions turns out to be a myth. Indeed, the most precise specifications of action are provided not by the procedures of theoretical computer science and mathematics (algorithms) but rather by the nontechnical procedures of everyday life. I close with a discussion of some of the rumifications of these conclusions for understanding and designing concrete computers and their programming languages. (shrink)
We critically discuss Cleland''s analysis of effective procedures as mundane effective procedures. She argues that Turingmachines cannot carry out mundane procedures, since Turingmachines are abstract entities and therefore cannot generate the causal processes that are generated by mundane procedures. We argue that if Turingmachines cannot enter the physical world, then it is hard to see how Cleland''s mundane procedures can enter the world of numbers. Hence her arguments against versions of the (...) Church-Turing thesis for number theoretic functions miss the mark. (shrink)
Animals, including humans, are usually judged on what they could become, rather than what they are. Many physical and cognitive abilities in the ‘animal kingdom’ are only acquired (to a given degree) when the subject reaches a certain stage of development, which can be accelerated or spoilt depending on how the environment, training or education is. The term ‘potential ability’ usually refers to how quick and likely the process of attaining the ability is. In principle, things should not be different (...) for the ‘machine kingdom’. While machines can be characterised by a set of cognitive abilities, and measuring them is already a big challenge, known as ‘universal psychometrics’, a more informative, and yet more challenging, goal would be to also determine the potential cognitive abilities of a machine. In this paper we investigate the notion of potential cognitive ability for machines, focussing especially on universality and intelligence. We consider several machine characterisations (non-interactive and interactive) and give definitions for each case, considering permanent and temporal potentials. From these definitions, we analyse the relation between some potential abilities, we bring out the dependency on the environment distribution and we suggest some ideas about how potential abilities can be measured. Finally, we also analyse the potential of environments at different levels and briefly discuss whether machines should be designed to be intelligent or potentially intelligent. (shrink)
This is the first of two volumes of essays in commemoration of Alan Turing, whose pioneering work in the theory of artificial intelligence and computer science ...
Turing's celebrated 1950 paper proposes a very general methodological criterion for modelling mental function: total functional equivalence and indistinguishability. His criterion gives rise to a hierarchy of Turing Tests, from subtotal ("toy") fragments of our functions (t1), to total symbolic (pen-pal) function (T2 -- the standard Turing Test), to total external sensorimotor (robotic) function (T3), to total internal microfunction (T4), to total indistinguishability in every empirically discernible respect (T5). This is a "reverse-engineering" hierarchy of (decreasing) empirical underdetermination (...) of the theory by the data. Level t1 is clearly too underdetermined, T2 is vulnerable to a counterexample (Searle's Chinese Room Argument), and T4 and T5 are arbitrarily overdetermined. Hence T3 is the appropriate target level for cognitive science. When it is reached, however, there will still remain more unanswerable questions than when Physics reaches its Grand Unified Theory of Everything (GUTE), because of the mind/body problem and the other-minds problem, both of which are inherent in this empirical domain, even though Turing hardly mentions them. (shrink)
Turing's celebrated 1950 paper proposes a very generalmethodological criterion for modelling mental function: total functionalequivalence and indistinguishability. His criterion gives rise to ahierarchy of Turing Tests, from subtotal (toy) fragments of ourfunctions (t1), to total symbolic (pen-pal) function (T2 – the standardTuring Test), to total external sensorimotor (robotic) function (T3), tototal internal microfunction (T4), to total indistinguishability inevery empirically discernible respect (T5). This is areverse-engineering hierarchy of (decreasing) empiricalunderdetermination of the theory by the data. Level t1 is clearly (...) toounderdetermined, T2 is vulnerable to a counterexample (Searle's ChineseRoom Argument), and T4 and T5 are arbitrarily overdetermined. Hence T3is the appropriate target level for cognitive science. When it isreached, however, there will still remain more unanswerable questionsthan when Physics reaches its Grand Unified Theory of Everything (GUTE),because of the mind/body problem and the other-minds problem, both ofwhich are inherent in this empirical domain, even though Turing hardlymentions them. (shrink)
There are currently considerable confusion and disarray about just how we should view computationalism, connectionism and dynamicism as explanatory frameworks in cognitive science. A key source of this ongoing conflict among the central paradigms in cognitive science is an equivocation on the notion of computation simpliciter. ‘Computation’ is construed differently by computationalism, connectionism, dynamicism and computational neuroscience. I claim that these central paradigms, properly understood, can contribute to an integrated cognitive science. Yet, before this claim can be defended, a better (...) understanding of ‘computation’ is required. ‘Digital computation’ is an ambiguous concept. It is not just the classical dichotomy between analogue and digital computation that is the basis for the equivocation on ‘computation’ simpliciter in cognitive science, but also the diversity of extant accounts of digital computation. There are many answers on what it takes for a system to perform digital computation. Answers to this problem range from Turing machine computation, through the formal manipulation of symbols, the execution of algorithms and others, to the strong-pancomputational thesis, according to which every physical system computes every Turing-computable function. Despite some overlap among them, extant accounts of concrete digital computation are non-equivalent, thus, rendering ‘digital computation’ ambiguous. The objective of this dissertation is twofold. First, it is to promote a clearer understanding of concrete digital computation. Accordingly, my main thesis is that not only are extant accounts of concrete digital computation non-equivalent, but most of them are inadequate. I show that these accounts are not just intensionally different (this is quite trivially the case), but also extensionally distinct. In the course of examining several key accounts of concrete digital computation, I propose the instructional information processing account, according to which digital computation is the processing of discrete data in accordance with finite instructional information. The second objective is to establish the foundational role of computation in cognitive science whilst rejecting the purported representational nature of computation. (shrink)
Many debates about consciousness appear to be endless, in part because of conceptual confusions preventing clarity as to what the issues are and what does or does not count as evidence. This makes it hard to decide what should go into a machine if it is to be described as 'conscious'. Thus, triumphant demonstrations by some AI developers may be regarded by others as proving nothing of interest because the system does not satisfy *their* definitions or requirements specifications.
We argue that the set of humanly known mathematical truths (at any given moment in human history) is finite and so recursive. But if so, then given various fundamental results in mathematical logic and the theory of computation (such as Craig’s in J Symb Log 18(1): 30–32(1953) theorem), the set of humanly known mathematical truths is axiomatizable. Furthermore, given Godel’s (Monash Math Phys 38: 173–198, 1931) First Incompleteness Theorem, then (at any given moment in human history) humanly known mathematics must (...) be either inconsistent or incomplete. Moreover, since humanly known mathematics is axiomatizable, it can be the output of a Turing machine. We then argue that any given mathematical claim that we could possibly know could be the output of a Turing machine, at least in principle. So the Lucas-Penrose (Lucas in Philosophy 36:112–127, 1961; Penrose, in The Emperor’s new mind. Oxford University Press, Oxford (1994)) argument cannot be sound. (shrink)
The properties of Turing’s famous ‘universal machine’ has long sustained functionalist intuitions about the nature of cognition. Here, I show that there is a logical problem with standard functionalist arguments for multiple realizability. These arguments rely essentially on Turing’s powerful insights regarding computation. In addressing a possible reply to this criticism, I further argue that functionalism is not a useful approach for understanding what it is to have a mind. In particular, I show that the difficulties involved in (...) distinguishing implementation from function make multiple realizability claims untestable and uninformative. As a result, I conclude that the role of Turingmachines in philosophy of mind needs to be reconsidered. (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)
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)
Since the introduction of the imitation game by Turing in 1950 there has been much debate as to its validity in ascertaining machine intelligence. We wish herein to consider a different issue altogether: granted that a computing machine passes the Turing Test, thereby earning the label of ``Turing Chatterbox'', would it then be of any use (to us humans)? From the examination of scenarios, we conclude that when machines begin to participate in social transactions, unresolved issues (...) of trust and responsibility may well overshadow any raw reasoning ability they possess. (shrink)
In this report I provide an introduction to the burgeoning field of hypercomputation – the study of machines that can compute more than Turingmachines. I take an extensive survey of many of the key concepts in the field, tying together the disparate ideas and presenting them in a structure which allows comparisons of the many approaches and results. To this I add several new results and draw out some interesting consequences of hypercomputation for several different disciplines.
We characterise explicitly the decidable predicates on integers of Infinite Time Turingmachines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that (...) the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)
This paper presents an analysis of three major contests for machine intelligence. We conclude that a new era for Turing’s test requires a fillip in the guise of a committed sponsor, not unlike DARPA, funders of the successful 2007 Urban Challenge.
Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing a (...) class='Hi'>test of a known physical theory T. (shrink)
Andrew Boucher (1997) argues that ``parallel computation is fundamentally different from sequential computation'' (p. 543), and that this fact provides reason to be skeptical about whether AI can produce a genuinely intelligent machine. But parallelism, as I prove herein, is irrelevant. What Boucher has inadvertently glimpsed is one small part of a mathematical tapestry portraying the simple but undeniable fact that physical computation can be fundamentally different from ordinary, ``textbook'' computation (whether parallel or sequential). This tapestry does indeed immediately imply (...) that human cognition may be uncomputable. (shrink)
What is the relation between intelligence and computation? Although the difficulty of defining `intelligence' is widely recognized, many are unaware that it is hard to give a satisfactory definition of `computational' if computation is supposed to provide a non-circular explanation for intelligent abilities. The only well-defined notion of `computation' is what can be generated by a Turing machine or a formally equivalent mechanism. This is not adequate for the key role in explaining the nature of mental processes, because it (...) is too general, as many computations involve nothing mental, nor even processes: they are simply abstract structures. We need to combine the notion of `computation' with that of `machine'. This may still be too restrictive, if some non-computational mechanisms prove to be useful for intelligence. We need a theory-based taxonomy of {\em architectures} and {\em mechanisms} and corresponding process types. Computational machines my turn out to be a sub-class of the machines available for implementing intelligent agents. The more general analysis starts with the notion of a system with independently variable, causally interacting sub-states that have different causal roles, including both `belief-like' and `desire-like' sub-states, and many others. There are many significantly different such architectures. For certain architectures (including simple computers), some sub-states have a semantic interpretation for the system. The relevant concept of semantics is defined partly in terms of a kind of Tarski-like structural correspondence (not to be confused with isomorphism). This always leaves some semantic indeterminacy, which can be reduced by causal loops involving the environment. But the causal links are complex, can share causal pathways, and always leave mental states to some extent semantically indeterminate. (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)
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)
Let psychologism be the doctrine that whether behavior is intelligent behavior depends on the character of the internal information processing that produces it. More specifically, I mean psychologism to involve the doctrine that two systems could have actual and potential behavior _typical_ of familiar intelligent beings, that the two systems could be exactly alike in their actual and potential behavior, and in their behavioral dispositions and capacities and counterfactual behavioral properties (i.e., what behaviors, behavioral dispositions, and behavioral capacities they would (...) have exhibited had their stimuli differed)--the two systems could be alike in all these ways, yet there could be a difference in the information processing that mediates their stimuli and responses that determines that one is not at all intelligent while the other is fully intelligent. (shrink)
On a literal reading of `Computing Machinery and Intelligence'', Alan Turing presented not one, but two, practical tests to replace the question `Can machines think?'' He presented them as equivalent. I show here that the first test described in that much-discussed paper is in fact not equivalent to the second one, which has since become known as `the Turing Test''. The two tests can yield different results; it is the first, neglected test that provides the more appropriate (...) indication of intelligence. This is because the features of intelligence upon which it relies are resourcefulness and a critical attitude to one''s habitual responses; thus the test''s applicablity is not restricted to any particular species, nor does it presume any particular capacities. This is more appropriate because the question under consideration is what would count as machine intelligence. The first test realizes a possibility that philosophers have overlooked: a test that uses a human''s linguistic performance in setting an empirical test of intelligence, but does not make behavioral similarity to that performance the criterion of intelligence. Consequently, the first test is immune to many of the philosophical criticisms on the basis of which the (so-called) `Turing Test'' has been dismissed. (shrink)
It is common in cognitive science to equate computation (and in particular digital computation) with information processing. Yet, it is hard to find a comprehensive explicit account of concrete digital computation in information processing terms. An information processing account seems like a natural candidate to explain digital computation. But when ‘information’ comes under scrutiny, this account becomes a less obvious candidate. Four interpretations of information are examined here as the basis for an information processing account of digital computation, namely Shannon (...) information, algorithmic information, factual information and instructional information. I argue that any plausible account of concrete computation has to be capable of explaining at least the three key algorithmic notions of input, output and procedures. Whist algorithmic information fares better than Shannon information, the most plausible candidate for an information processing account is instructional information. (shrink)
A series of imitation games involving 3-participant (simultaneous comparison of two hidden entities) and 2-participant (direct interrogation of a hidden entity) were conducted at Bletchley Park on the 100th anniversary of Alan Turing’s birth: 23 June 2012. From the ongoing analysis of over 150 games involving (expert and non-expert, males and females, adults and child) judges, machines and hidden humans (foils for the machines), we present six particular conversations that took place between human judges and a hidden (...) entity that produced unexpected results. From this sample we focus on features of Turing’s machine intelligence test that the mathematician/code breaker did not consider in his examination for machine thinking: the subjective nature of attributing intelligence to another mind. (shrink)
Response to Floridi et al, 2008/2009. Based on insufficient evidence, and inadequate research, Floridi and his students report inaccuracies and draw false conclusions in their Minds and Machines evaluation, which this paper aims to clarify. Acting as invited judges, Floridi et al. participated in nine, of the ninety-six, Turing tests staged in the finals of the 18th Loebner Prize for Artificial Intelligence in October 2008. From the transcripts it appears that they used power over solidarity as an interrogation (...) technique. As a result, they were fooled on several occasions into believing that a machine was a human and that a human was a machine. Worse still, they did not realise their mistake. This resulted in a combined correct identification rate of less than 56%. In their paper they assumed that they had made correct identifications when they in fact had been incorrect. (shrink)
In the centenary year of Turing’s birth, a lot of good things are sure to be written about him. But it is hard to find something new to write about Turing. This is the biggest merit of this article: it shows how von Neumann’s architecture of the modern computer is a serendipitous consequence of the universal Turing machine, built to solve a logical problem.
This paper investigates the view that digital hypercomputing is a good reason for rejection or re-interpretation of the Church-Turing thesis. After suggestion that such re-interpretation is historically problematic and often involves attack on a straw man (the ‘maximality thesis’), it discusses proposals for digital hypercomputing with Zeno-machines , i.e. computing machines that compute an infinite number of computing steps in finite time, thus performing supertasks. It argues that effective computing with Zeno-machines falls into a dilemma: either (...) they are specified such that they do not have output states, or they are specified such that they do have output states, but involve contradiction. Repairs though non-effective methods or special rules for semi-decidable problems are sought, but not found. The paper concludes that hypercomputing supertasks are impossible in the actual world and thus no reason for rejection of the Church-Turing thesis in its traditional interpretation. (shrink)
A. M. Turing has bequeathed us a conceptulary including 'Turing, or Turing-Church, thesis', 'Turing machine', 'universal Turing machine', 'Turing test' and 'Turing structures', plus other unnamed achievements. These include a proof that any formal language adequate to express arithmetic contains undecidable formulas, as well as achievements in computer science, artificial intelligence, mathematics, biology, and cognitive science. Here it is argued that these achievements hang together and have prospered well in the 50 years since (...)Turing's death. (shrink)
It is not widely realised that Turing was probably the first person to consider building computing machines out of simple, neuron-like elements connected together into networks in a largely random manner. Turing called his networks unorganised machines. By the application of what he described as appropriate interference, mimicking education an unorganised machine can be trained to perform any task that a Turing machine can carry out, provided the number of neurons is sufficient. Turing proposed (...) simulating both the behaviour of the network and the training process by means of a computer program. We outline Turing's connectionist project of 1948. (shrink)
The TuringTest is one of the most disputed topics in artificial intelligence, philosophy of mind, and cognitive science. This paper is a review of the past 50 years of the TuringTest. Philosophical debates, practical developments and repercussions in related disciplines are all covered. We discuss Turing''s ideas in detail and present the important comments that have been made on them. Within this context, behaviorism, consciousness, the `other minds'' problem, and similar topics in philosophy (...) of mind are discussed. We also cover the sociological and psychological aspects of the TuringTest. Finally, we look at the current situation and analyze programs that have been developed with the aim of passing the TuringTest. We conclude that the TuringTest has been, and will continue to be, an influential and controversial topic. (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 Turingmachines. (shrink)
The TuringTest is one of the most disputed topics in artificial intelligence, philosophy of mind, and cognitive science. This paper is a review of the past 50 years of the TuringTest. Philo- sophical debates, practical developments and repercussions in related disciplines are all covered. We discuss Turing’s ideas in detail and present the important comments that have been made on them. Within this context, behaviorism, consciousness, the ‘other minds’ problem, and similar topics in (...) philosophy of mind are discussed. We also cover the sociological and psychological aspects of the TuringTest. Finally, we look at the current situation and analyze programs that have been developed with the aim of passing the TuringTest. We conclude that the TuringTest has been, and will continue to be, an influential and controversial topic. (shrink)
Turing's (1936) analysis of effective symbolic procedures is a model of conceptual clarity that plays an essential role in the philosophy of mathematics. Yet appeal is often made to the effectiveness of human procedures in other areas of philosophy. This paper addresses the question of whether Turing's analysis can be applied to a broader class of effective human procedures. We use Sieg's (1994) presentation of Turing's Thesis to argue against Cleland's (1995) objections to Turingmachines (...) and we evaluate her proposal to understand the effectiveness of procedures in terms of their reliability and precision. A number of conditions for effectiveness are identified and these are used to provide a general argument against the possibility of a Leibnizian decision procedure. (shrink)
