Online research in philosophy

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)

There are many complex characters in this paper; if you find them difficult to distinguish, you are advised to increase the viewing size. (In IExplorer, go to View menu, Text Size; in Netscape, go to View menu, Increase Font.).

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)

As is well known, Alan Turing drew a line, embodied in the "Turing test," between intellectual and physical abilities, and hence between cognitive and natural sciences. Less familiarly, he proposed that one way to produce a "passer" would be to educate a "child machine," equating the experimenter's improvements in the initial structure of the child machine with genetic mutations, while supposing that the experimenter might achieve improvements more expeditiously than natural selection. On the other hand, in his (...) foundational "On the chemical basis of morphogenesis," Turing insisted that biological explanation clearly confine itself to purely physical and chemical means, eschewing vitalist and teleological talk entirely and hewing to D'Arcy Thompson's line that "evolutionary 'explanations,'" are historical and narrative in character, employing the same intentional and teleological vocabulary we use in doing human history, and hence, while perhaps on occasion of heuristic value, are not part of biology as a natural science. To apply Turing's program to recent issues, the attempt to give foundations to the social and cognitive sciences in the "real science" of evolutionary biology (as opposed to Turing's biology) is neither to give foundations, nor to achieve the unification of the social/cognitive sciences and the natural sciences. (shrink)

In his short life, Alan Turing (1912-1954) made foundational contributions to philosophy, mathematics, biology, artificial intelligence, and computer science. He, as much as anyone, invented the digital electronic computer. From September, 1939 much of his work on computation was war-driven and brutally practical. He developed high speed computing devices needed to decipher German Enigma Machine messages to and from U-boats, countering the most serious threat by far to Britain's survival during World War Two. Yet few people have an (...) image of him. (shrink)

In his short life, <span class='Hi'>Alan</span> Turing (1912-1954) made foundational contributions to philosophy, mathematics, biology, artificial intelligence, and computer science. He, as much as anyone, invented and showed how to program the digital electronic computer. From September, 1939, his work on computation was war-driven and brutally practical. He developed high speed computing devices needed to decipher German Enigma Machine messages to and from U-boats, countering the most serious threat by far to Britain=s survival during World War Two.

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)

In his short life, Alan Turing (1912-1954) made foundational contributions to philosophy, mathematics, biology, artificial intelligence, and computer science. He, as much as anyone, invented and showed how to program the digital electronic computer. From September, 1939, his work on computation was war-driven and brutally practical. He developed high speed computing devices needed to decipher German Enigma Machine messages to and from U-boats, countering the most serious threat by far to Britain..

The origin of my article lies in the appearance of Copeland and Proudfoot's feature article in Scientific American, April 1999. This preposterous paper, as described on another page, suggested that Turing was the prophet of 'hypercomputation'. In their references, the authors listed Copeland's entry on 'The Church-Turing thesis' in the Stanford Encyclopedia. In the summer of 1999, I circulated an open letter criticising the Scientific American article. I included criticism of this Encyclopedia entry. This was forwarded (by Prof. (...) Sol Feferman) to Prof. Ed Zalta, editor of the Encyclopedia, and after some discussion he invited me to submit an entry on 'Alan Turing.'. (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 ...

The mathematical genius Alan Turing (1912-1954) was one of the greatest scientists and thinkers of the 20th century. Now well known for his crucial wartime role in breaking the ENIGMA code, he was the first to conceive of the fundamental principle of the modern computer-the idea of controlling a computing machine's operations by means of a program of coded instructions, stored in the machine's 'memory'. In 1945 Turing drew up his revolutionary design for an electronic computing machine-his (...) Automatic Computing Engine ('ACE'). A pilot model of the ACE ran its first program in 1950 and the production version, the 'DEUCE', went on to become a cornerstone of the fledgling British computer industry. The first 'personal' computer was based on Turing's ACE. -/- Alan Turing's Automatic Computing Engine describes Turing's struggle to build the modern computer. The first detailed history of Turing's contributions to computer science, this text is essential reading for anyone interested in the history of the computer and the history of mathematics. It contains first hand accounts by Turing and by the pioneers of computing who worked with him. As well as relating the story of the invention of the computer, the book clearly describes the hardware and software of the ACE-including the very first computer programs. The book is intended to be accessible to everyone with an interest in computing, and contains numerous diagrams and illustrations as well as original photographs. -/- The book contains chapters describing Turing's path-breaking research in the fields of Artificial Intelligence (AI) and Artificial Life (A-Life). The book has an extensive system of hyperlinks to The Turing Archive for the History of Computing, an on-line library of digital facsimiles of typewritten documents by Turing and the other scientists who pioneered the electronic computer. (shrink)

This is the second of two volumes of essays in commemoration of Alan Turing; it celebrates his intellectual legacy within the philosophy of mind and cognitive science. A distinguished international cast of contributors focus on the relationship beteen a scientific, computational image of the mind and a common-sense picture of the mind as an inner arena populated by concepts, beliefs, intentions, and qualia. Topics covered include the causal potency of folk-psychological states, the connectionist reconception of learning and concept (...) formation, the understanding of the notion of computation itself, and the relation between philosophical and psychological theories of concepts. -/- Also available in paperback is the companion volume, Machines and Thought, edited by Peter Millican and Andy Clark, which focuses on Turing's main innovations in artificial intelligence. (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 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)

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)

Alan Turing advocated a kind of functionalism: A machine M is a thinker provided that it responds in certain ways to certain inputs. Davidson argues that Turing’s functionalism is inconsistent with a certain kind of epistemic externalism, and is therefore false. In Davidson’s view, concepts consist of causal liasons of a certain kind between subject and object. Turing’s machine doesn’t have the right kinds of causal liasons to its environment. Therefore it doesn’t have concepts. Therefore it (...) doesn’t think. I argue that this reasoning is entirely fallacious. It is true that, in some cases, a causal liason between subject and object is part of one’s concept of that object. Consequently, to grasp certain propositions, one must have certain kids of causal ties to one’s environment. But this means that we must rethink some old views on what rationality is. It does not mean, pace Davidson, that a precondition for being rational is being causally embedded in one’s environment in a certain way. If Turing’s machine isn’t capable of thinking (I leave it open whether it is or is not), that has nothing to do with its lacking certain kinds of causal connections to the environment. The larger significance of our discussion is this: rationality consists either in one’s ability to see the bearing of purely existential propositions on one another or rationality is simply not to be understood as the ability see the bearing that propositions have on one another. (shrink)

We investigate Turing's contributions to computability theory for real numbers and real functions presented in [22, 24, 26]. In particular, it is shown how two fundamental approaches to computable analysis, the so-called ‘Type-2 Theory of Effectivity' (TTE) and the ‘realRAM machine' model, have their foundations in Turing's work, in spite of the two incompatible notions of computability they involve. It is also shown, by contrast, how the modern conceptual tools provided by these two paradigms allow a systematic interpretation (...) of Turing's pioneering work in the subject. (shrink)

Englantilaisen yleisneron Alan Turingin kuoleman yllä lepää salaperäisyyden verho. On hyvin mahdollista, ettei kenenkään muun nykyajan ajattelijan kuolemaan liity yhtä paljon legendoja ja spekulaatioita. Kiistattomat tosiasiat ovat lyhykäisyydessään seuraavat: siivooja löysi Turingin kotoaan kuolleena 8. kesäkuuta 1954. Turingin todettiin kuolleen edellisenä iltana syanidimyrkytykseen, ja hänen viereltään löytyi puoliksi syöty omena. Hän oli kuollessaan 41-vuotias. Loppu on enemmän tai vähemmän arvailujen varassa.

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

Department of Computer Engineering, Bilkent University, 06533 Ankara, Turkey E-mail: akman@cs.bilkent.edu.tr; http://www.cs.bilkent.edu.tr/?akman..

On the 27th of October, 1949, the Department of Philosophy at the University of Manchester organized a symposium "Mind and Machine", as Michael Polanyi noted in his Personal Knowledge (1974, p. 261). This event is known, especially among scholars of Alan Turing, but it is scarcely documented. Wolfe Mays (2000) reported about the debate, which he personally had attended, and paraphrased a mimeographed document that is preserved at the Manchester University archive. He forwarded a copy to Andrew Hodges (...) and B. Jack Copeland, who in then published it on their respective websites. The basis of this interpretation here is the copy preserved in the Regenstein Library of the University of Chicago, Special Collections, Polanyi Collection (abbreviated RPC, box 22, folder 19). The same collection holds the mimeographed statement that Polanyi prepared for this symposium: "Can the mind be represented by a machine?" This text has not been studied by Polanyi scholars. (shrink)

The day was particularly appropriate. There was a great deal of publicity for the 50th anniversary of the world's first working modern computer, which ran at Manchester on 21 June 1948. And at 10.30pm the night before, 22 June 1998, the House of Commons had voted by a large majority to change the law so that homosexual and heterosexual acts would alike be governed by an 'age of consent' of 16. It was recognised by all sides that the issue at (...) stake was that of equality. (Note added later: the law was indeed finally changed on 30 November 2000, despite intense opposition from christian leaders in the unelected House of Lords.). (shrink)

Stuart M. Shieber’s name is well known to computational linguists for his research and to computer scientists more generally for his debate on the Loebner Turing Test competition, which appeared a decade earlier in Communications of the ACM (Shieber 1994a, 1994b; Loebner 1994).¹ With this collection, I expect it to become equally well known to philosophers.

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)

Alan Turing devised his famous test (TT) through a slight modificationof the parlor game in which a judge tries to ascertain the gender of twopeople who are only linguistically accessible. Stevan Harnad hasintroduced the Total TT, in which the judge can look at thecontestants in an attempt to determine which is a robot and which aperson. But what if we confront the judge with an animal, and arobot striving to pass for one, and then challenge him to peg (...) which iswhich? Now we can index TTT to a particular animal and its syntheticcorrelate. We might therefore have TTTrat, TTTcat,TTTdog, and so on. These tests, as we explain herein, are abetter barometer of artificial intelligence (AI) than Turing's originalTT, because AI seems to have ammunition sufficient only to reach thelevel of artificial animal, not artificial person. (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)

In the 1950s, Alan Turing proposed his influential test for machine intelligence, which involved a teletyped dialogue between a human player, a machine, and an interrogator. Two readings of Turing''s rules for the test have been given. According to the standard reading of Turing''s words, the goal of the interrogator was to discover which was the human being and which was the machine, while the goal of the machine was to be indistinguishable from a human being. (...) According to the literal reading, the goal of the machine was to simulate a man imitating a woman, while the interrogator – unaware of the real purpose of the test – was attempting to determine which of the two contestants was the woman and which was the man. The present work offers a study of Turing''s rules for the test in the context of his advocated purpose and his other texts. The conclusion is that there are several independent and mutually reinforcing lines of evidence that support the standard reading, while fitting the literal reading in Turing''s work faces severe interpretative difficulties. So, the controversy over Turing''s rules should be settled in favor of the standard reading. (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)

John Searle has argued that the aim of strong AI of creating a thinking computer is misguided. Searle’s Chinese Room Argument purports to show that syntax does not suffice for semantics and that computer programs as such must fail to have intrinsic intentionality. But we are not mainly interested in the program itself but rather the implementation of the program in some material. It does not follow by necessity from the fact that computer programs are defined syntactically that the implementation (...) of them cannot suffice for semantics. Perhaps our world is a world in which any implementation of the right computer program will create a system with intrinsic intentionality, in which case Searle’s Chinese Room Scenario is empirically (nomically) impossible. But, indeed, perhaps our world is a world in which Searle’s Chinese Room Scenario is empirically (nomically) possible and that the silicon basis of modern day computers are one kind of material unsuited to give you intrinsic intentionality. The metaphysical question turns out to be a question of what kind of world we are in and I argue that in this respect we do not know our modal address. The Modal Address Argument does not ensure that strong AI will succeed, but it shows that Searle’s challenge on the research program of strong AI fails in its objectives. (shrink)

In 1950, Alan Turing proposed his eponymous test based on indistinguishability of verbal behavior as a replacement for the question "Can machines think?" Since then, two mutually contradictory but well-founded attitudes towards the Turing Test have arisen in the philosophical literature. On the one hand is the attitude that has become philosophical conventional wisdom, viz., that the Turing Test is hopelessly flawed as a sufficient condition for intelligence, while on the other hand is the overwhelming sense (...) that were a machine to pass a real live full-fledged Turing Test, it would be a sign of nothing but our orneriness to deny it the attribution of intelligence. The arguments against the sufficiency of the Turing Test for determining intelligence rely on showing that some extra conditions are logically necessary for intelligence beyond the behavioral properties exhibited by an agent under a Turing Test. Therefore, it cannot follow logically from passing a Turing Test that the agent is intelligent. I argue that these extra conditions can be revealed by the Turing Test, so long as we allow a very slight weakening of the criterion from one of logical proof to one of statistical proof under weak realizability assumptions. The argument depends on the notion of interactive proof developed in theoretical computer science, along with some simple physical facts that constrain the information capacity of agents. Crucially, the weakening is so slight as to make no conceivable difference from a practical standpoint. Thus, the Gordian knot between the two opposing views of the sufficiency of the Turing Test can be cut. (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)

In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis (or Thesis M), according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if (...) true, contingently so. On all accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify (or even to be true). In this paper I articulate this question and consider several tentative answers to it. (shrink)

One account of the history of computation might begin in the 1930’s with some of the work of Alonzo Church, Alan Turing, and Emil Post. One might say that this is where something like the core concept of computation was first formally articulated. Here were the first attempts to formalize an informal notion of an algorithm or effective procedure by which a mathematician might decide one or another logico-mathematical question. As each of these formalisms was shown to compute (...) the same set of functions—the partial recursive functions—each of them might be described as a form of Turing-equivalent computation. This work set the cornerstone for what we might call computation theory. This history might then proceed to give pride of place to this form of computation in subsequent developments in cognitive science and in related disciplines and subdisciplines. Such a history might note that, in the 1940’s, the results of this work would have been transferred into the emerging field of computer science with the design and construction of the first electronic digital computers. Here one would mention Turing again, as well as perhaps Norbert Wiener, Julian Bigelow, John von Neumann, and many others. At about the same time, this theory of computation would have been inserted into the theory of neural networks by way of Warren McCulloch and Walter Pitts’s seminal work, “A Logical Calculus of the Ideas Immanent in Nervous Activity.” Somewhat later, during the 1960’s, Hilary Putnam introduced Turing machine tables into the philosophy of mind as a tool for illuminating various features of the mind-body problem, eventually transforming the intellectual landscape in the metaphysics of mind. Also during the 1960’s, Turingequivalent computation would have infiltrated psychology through the influence of Chomskyan linguistics and under the rubric of information processing psychology. Further, such computation would have been integrated into the fields of cognitive science and neuroscience as they emerged during the 1970’s and 1980’s.. (shrink)

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)

One account of the history of computation might begin in the 1930's with some of the work of Alonzo Church, Alan Turing, and Emil Post. One might say that this is where something like the core concept of computation was first formally articulated. Here were the first attempts to formalize an informal notion of an algorithm or effective procedure by which a mathematician might decide one or another logico-mathematical question. As each of these formalisms was shown to compute (...) the same set of functions—the partial recursive functions—each of them might be described as a form of Turing-equivalent computation. This work set the cornerstone for what we might call computation theory. This history might then proceed to give pride of place to this form of computation in subsequent developments in cognitive science and in related disciplines and subdisciplines. Such a history might note that, in the 1940's, the results of this work would have been transferred into the emerging field of computer science with the design and construction of the first electronic digital computers. Here one would mention Turing again, as well as perhaps Norbert Wiener, Julian Bigelow, John von Neumann, and many others. At about the same time, this theory of computation would have been inserted into the theory of neural networks by way of Warren McCulloch and Walter Pitts's seminal work, “A Logical Calculus of the Ideas Immanent in Nervous Activity.” Somewhat later, during the 1960's, Hilary Putnam introduced Turing machine tables into the philosophy of mind as a tool for illuminating various features of the mind-body problem, eventually transforming the intellectual landscape in.. (shrink)

Stuart M. Shieber’s name is well known to computational linguists for his research and to computer scientists more generally for his debate on the Loebner Turing Test competition, which appeared a decade earlier in Communications of the ACM (Shieber 1994a, 1994b; Loebner 1994).¹ With this collection, I expect it to become equally well known to philosophers.

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)

If, as a number of writers have predicted, the computers of the future will possess intelligence and capacities that exceed our own then it seems as though they will be worthy of a moral respect at least equal to, and perhaps greater than, human beings. In this paper I propose a test to determine when we have reached that point. Inspired by Alan Turing’s (1950) original “Turing test”, which argued that we would be justified in (...) conceding that machines could think if they could fill the role of a person in a conversation, I propose a test for when computers have achieved moral standing by asking when a computer might take the place of a human being in a moral dilemma, such as a “triage” situation in which a choice must be made as to which of two human lives to save. We will know that machines have achieved moral standing comparable to a human when the replacement of one of these people with an artificial intelligence leaves the character of the dilemma intact. That is, when we might sometimes judge that it is reasonable to preserve the continuing existence of a machine over the life of a human being. This is the “Turing Triage Test”. I argue that if personhood is understood as a matter of possessing a set of important cognitive capacities then it seems likely that future AIs will be able to pass this test. However this conclusion serves as a reductio of this account of the nature of persons. I set out an alternative account of the nature of persons, which places the concept of a person at the centre of an interdependent network of moral and affective responses, such as remorse, grief and sympathy. I argue that according to this second, superior, account of the nature of persons, machines will be unable to pass the Turing Triage Test until they possess bodies and faces with expressive capacities akin to those of the human form. (shrink)

The Turing Test is a verbal-behavioral operational criterion of artificial intelligence. If a machine can participate in question–and–answer conversation adequately enough to deceive an intelligent interlocutor, then it has intelligent information processing abilities. Robert M. French has argued that recent discoveries in cognitive science about subcognitive processes involving associational primings prove that the Turing Test cannot provide a satisfactory criterion of machine intelligence, that Turing's prediction concerning the feasibility of building machines to play the imitation game successfully (...) is false, and that the test should be rejected as ethnocentric and incapable of measuring kinds and degrees of nonhuman intelligence. But French's criticism is flawed, because it requires Turing's sufficient conditional criterion of intelligence to serve as a necessary condition. Turing's Test is defended against these objections, and French's claim that the test ought to be rejected because machines cannot pass it is deemed unscientific, resting on the empirically unwarranted assumption that intelligent machines are possible. (shrink)

In this paper I begin by extending two results of Solovay; the first characterizes the possible Turing degrees of models of True Arithmetic (TA), the complete first-order theory of the standard model of PA, while the second characterizes the possible Turing degrees of arbitrary completions of P. I extend these two results to characterize the possible Turing degrees of m-diagrams of models of TA and of arbitrary complete extensions of PA. I next give a construction showing that (...) the conditions Solovay identified for his characterization of degrees of models of arbitrary completions of PA cannot be dropped (I showed that these conditions cannot be simplified in the paper. (shrink)

Reading through Mechanica1 Intelligence, volume III of Alan Turing's Collected Works, one begins to appreciate just how propitious Turing's timing was. If Turing's major accomplishment in ‘On Computable Numbers’ was to expose the epistemological premises built into formalism, his main achievement in the 1940s was to recognize the extent to which this outlook both harmonized with and extended contemporary psychological thought. Turing sought to synthesize these diverse mathematical and psychological elements so as to forge a (...) union between ‘embodied rules’ and ‘learning programs’. Through their joint service in the Mechanist Thesis each would validate the other: and the frameworks from whence each derived. In this paper I will try to show how Turing's psychological thesis forces us to reassess the consequences of establishing AI on the epistemological foundation that underlies behaviourism. (shrink)

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

Patterns resulting from the sole interplay between reaction and diffusion are probably involved in certain stages of morphogenesis in biological systems, as initially proposed by Alan Turing. Self-organization phenomena of this type can only develop in nonlinear systems (i.e. involving positive and negative feedback loops) maintained far from equilibrium. We present Turing patterns experimentally observed in a chemical system. An oscillating chemical reaction, the CIMA reaction, is operated in an open spatial reactor designed in order to obtain (...) a pure reaction-diffusion system. The two types of Turing patterns observed, hexagonal arrays of spots and parallel stripes, are characterized by an intrinsic wavelength. We identify the origin of the necessary difference of diffusivity between activator and inhibitor. We also describe a pattern growth mechanism by spot splitting that recalls cell division. (shrink)

In the sole extended break from his life and varing in this way we can associate a sysied career in England, Alan Turing spent the tem of logic with any constructive ordinal. It may be asked whether such a years 1936–1938 doing graduate work at..

Alan Turing devised his famous test (TT) through a slight modificationof the parlor game in which a judge tries to ascertain the gender of twopeople who are only linguistically accessible. Stevan Harnad hasintroduced the Total TT, in which the judge can look at thecontestants in an attempt to determine which is a robot and which aperson. But what if we confront the judge with an animal, and arobot striving to pass for one, and then challenge him to (...) peg which iswhich? Now we can index TTT to a particular animal and its syntheticcorrelate. We might therefore have TTTrat, TTTcat,TTTdog, and so on. These tests, as we explain herein, are abetter barometer of artificial intelligence (AI) than Turing's originalTT, because AI seems to have ammunition sufficient only to reach thelevel of artificial animal, not artificial person. (shrink)

Alan Turing draws a firm line between the mental and the physical, between the cognitive and physical sciences. For Turing, following a tradition that went back to D=Arcy Thompson, if not Geoffroy and Lucretius, throws talk of function, intentionality, and final causes from biology as a physical science. He likens Amother nature@ to the earnest A. I. scientist, who may send to school disparate versions of the Achild machine,@ eventually hoping for a test-passer but knowing that the (...) vagaries of his experimental course are history and accident. (shrink)

We prove that every countable jump upper semilattice can be embedded in D, where a jump upper semilattice (jusl) is an upper semilattice endowed with a strictly increasing and monotone unary operator that we call jump, and D is the jusl of Turing degrees. As a corollary we get that the existential theory of $\langle D, \leq_{T}, \vee, '\rangle$ is decidable. We also prove that this result is not true about jusls with 0, by proving that not every quantifier (...) free 1-type of jusl with 0 is realized in D. On the other hand, we show that every quantifier free 1-type of jump partial ordering (jpo) with 0 is realized in D. Moreover, we show that if every quantifier free type, $p(x_{1},..., x_{n})$ , of jpo with 0, which contains the formula $x_{1} \leq 0{^(m)} \& ... \& x_{n} \leq 0^{(m)}$ for some m, is realized in D, then every quantifier free type of jpo with 0 is realized in D. We also study the question of whether every jusl with the c.p.p. and size $\kappa \leq 2^{\aleph 0}$ is embeddable in D. We show that for $\kappa = 2^{\aleph 0}$ the answer is no, and that for κ = ℵ1 it is independent of ZFC. (It is true if $MA(\kappa)$ holds.). (shrink)

Cybernetics,” which he presented as en suite with six articles by several others on the same subject in the same journal during the preceding 18 months. This group of short papers, starting with one by Karl Popper, may be regarded as part of the first wave of response to Alan Turing’s famous paper, “Computing Machinery and Intelligence,” in 1950. Polanyi read Turing’s paper in draft and discussed it directly with Turing. The polemic as to whether machines (...) can think and the mind’s likeness and unlikeness to a machine, has of course never ceased since then and, as Artificial Intelligence develops, is not likely to do so for many long decades. In addition to the traditional battle lines in philosophy over the mind and the brain there are other important lines of thought that disfavor logic as the final arbiter of the great philosophical questions—for example, feminist ontology and cultural theory. Polanyi started from within logic, but his line of thought was not built out of the old philosophical topics nor did he address the matter along either the materialist or the phenomenological developments of the twentieth century. He was concerned with the cybernetic view of the human mind and also with the way the followers of Wittgenstein regarded language and philosophy. (shrink)

No computer that had not experienced the world as we humans had could pass a rigorously administered standard Turing Test. We show that the use of “subcognitive” questions allows the standard Turing Test to indirectly probe the human subcognitive associative concept network built up over a lifetime of experience with the world. Not only can this probing reveal differences in cognitive abilities, but crucially, even differences in _physical aspects_ of the candidates can be detected. Consequently, it (...) is unnecessary to propose even harder versions of the Test in which all physical and behavioral aspects of the two candidates had to be indistinguishable before allowing the machine to pass the Test. Any machine that passed the “simpler” symbols- in/symbols-out test as originally proposed by Turing would be intelligent. The problem is that, even in its original form, the Turing Test is already too hard and too anthropocentric for any machine that was not a physical, social, and behavioral carbon copy of ourselves to actually pass it. Consequently, the Turing Test, even in its standard version, is not a reasonable test for general machine intelligence. There is no need for an even stronger version of the Test. (shrink)

A. M. Turing argued that there was ‘little point in trying to make a ‘thinking machine’ more human by dressing it up in ... artificial flesh’. We should, instead, draw ‘a fairly sharp line between the physical and the intellectual capacities of a man’. For over fifty years, drawing this line has meant disregarding the role flesh plays in our intellectual capacities. Correspondingly, intelligence has been defined in terms of the algorithms that both men and machines can perform. I (...) would like to raise some doubts about this paradigm in AI research. Intelligence, I believe, does not just involve the working of algorithms. It is founded on flesh’s ability to move itself, to feel itself, and to engage in the body projects that accompanied our learning a language. This implies that to copy intelligence--i.e., produce an artificial version of it--the flesh that forms its basis must also be reproduced. (shrink)

The Gödelian symphony -- Foundations and paradoxes -- This sentence is false -- The liar and Gödel -- Language and metalanguage -- The axiomatic method or how to get the non-obvious out of the obvious -- Peano's axioms -- And the unsatisfied logicists, Frege and Russell -- Bits of set theory -- The abstraction principle -- Bytes of set theory -- Properties, relations, functions, that is, sets again -- Calculating, computing, enumerating, that is, the notion of algorithm -- Taking numbers (...) as sets of sets -- It's raining paradoxes -- Cantor's diagonal argument -- Self-reference and paradoxes -- Hilbert -- Strings of symbols -- In mathematics there is no ignorabimus -- Gödel on stage -- Our first encounter with the incompleteness theorem -- And some provisos -- Gödelization, or say it with numbers! -- TNT -- The arithmetical axioms of tnt and the standard model N -- The fundamental property of formal systems -- The Gödel numbering -- And the arithmetization of syntax -- Bits of recursive arithmetic -- Making algorithms precise -- Bits of recursion theory -- Church's thesis -- The recursiveness of predicates, sets, properties, and relations -- And how it is represented in typographical number theory -- Introspection and representation -- The representability of properties, relations, and functions -- And the Gödelian loop -- I am not provable -- Proof pairs -- The property of being a theorem of TNI (is not recursive!) -- Arithmetizing substitution -- How can a TNT sentence refer to itself? -- Fixed point -- Consistency and omega-consistency -- Proving G1 -- Rosser's proof -- The unprovability of consistency and the immediate consequences of G1 and -- G2 -- Technical interlude -- Immediate consequences of G1 and G2 -- Undecidable1 and undecidable 2 -- Essential incompleteness, or the syndicate of mathematicians -- Robinson arithmetic -- How general are Gödel's results? -- Bits of turing machine -- G1 and G2 in general -- Unexpected fish in the formal net -- Supernatural numbers -- The culpability of the induction scheme -- Bits of truth (not too much of it, though) -- The world after Gödel -- Bourgeois mathematicians! : the postmodern interpretations -- What is postmodernism? -- From Gödel to Lenin -- Is biblical proof decidable? -- Speaking of the totality -- Bourgeois teachers! -- (un)interesting bifurcations -- A footnote to Plato -- Explorers in the realm of numbers -- The essence of a life -- The philosophical prejudices of our times -- From Gödel to Tarski -- Human, too human -- Mathematical faith -- I'm not crazy! -- Qualified doubts -- From gentzen to the dialectica interpretation -- Mathematicians are people of faith -- Mind versus computer : Gödel and artificial intelligence -- Is mind (just) a program? -- Seeing the truth and going outside the system -- The basic mistake -- In the haze of the transfinite -- Know thyself : Socrates and the inexhaustibility of mathematics -- Gödel versus wittgenstein and the paraconsistent interpretation -- When geniuses meet -- The implausible Wittgenstein -- There is no metamathematics -- Proof and prose -- The single argument -- But how can arithmetic be inconsistent? -- The costs and benefits of making Wittgenstein plausible. (shrink)

In Part V of his Discourse on the Method, Descartes introduces a test for distinguishing people from machines that is similar to the one proposed much later by Alan Turing. The Cartesian test combines two distinct elements that Keith Gunderson has labeled the language test and the action test. Though traditional interpretation holds that the action test attempts to determine whether an agent is acting upon principles, I argue that the action test (...) is best understood as a test of common sense. I also maintain that this interpretation yields a stronger test than Turing's, and that contemporary artificial intelligence should consider using it as a guide for future research. (shrink)

1. One theory or many? In 2004 a very interesting and readable article by Lenore Blum, entitled “Computing over the reals: Where Turing meets Newton,” appeared in the Notices of the American Mathematical Society. It explained a basic model of computation over the reals due to Blum, Michael Shub and Steve Smale (1989), subsequently exposited at length in their influential book, Complexity and Real Computation (1997), coauthored with Felipe Cucker. The ‘Turing’ in the title of Blum’s article refers (...) of course to Alan Turing, famous for his explication of the notion of mechanical computation on discrete data such as the integers. The ‘Newton’ there has to do to with the well known numerical method due to Isaac Newton for approximating the zeros of continuous functions under suitable conditions that is taken to be a paradigm of scientific computing. Finally, the meaning of “Turing meets Newton” in the title of Blum’s article has another, more particular aspect: in connection with the problem of controlling errors in the numerical solution of linear equations and inversion of matrices,Turing (1948) defined a notion of condition for the relation of changes in the output of a computation due to small changes in the input that is analogous to Newton’s definition of the derivative. The thrust of Blum’s 2004 article was that the BSS model of computation on the reals is the appropriate foundation for scientific computing in general. By way of response, two years later another very interesting and equally readable article appeared in the Notices, this time by Mark Braverman and Stephen Cook (2006) entitled “Computing over the reals: Foundations for scientific computing,” in which the authors argued that the requisite foundation is provided by a quite different “bit computation” model, that is in fact prima facie incompatible with the BSS model. The bit computation model goes back to ideas due to Stefan Banach and Stanislaw Mazur in the latter part of the 1930s, but the first publication was not made until Mazur (1963).. (shrink)

This is the second of two volumes of essays in commemoration of Alan Turing.

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 ...

Explain how to represent claims about Turing machines (for example, claims of the form ”machine m halts on input i”) in the above language. The goal is a mechanical method for translating claims about TMs into arithmetical claims in a way that preserves truth value.

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

The unprecedented opportunities for experiments in complexity presented by the first modern computers in the late 1940's raised hopes in early computer scientists (eg. John von Neumann and Alan Turing) that the ability to think, our greatest asset in our dealings with the world, might soon be understood well enough to be duplicated. Success in such an endeavor would extend mankind's mind in the same way that the development of energy machinery extended his muscles.

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)

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of (...) homology n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

The dilemma confronted by Buridan’s Ass leads into a problem about nil-preference situations, to which there is a solution in the literature that is inspired by Alan Turing: we have evolved with a computational module in our brains that comes into play in such situations by picking a random action among the alternatives that detennines the subject’s choice. We relate these Buridan’s Ass situations to a larger, theoretically interesting category in which there is no alternative that is decisively (...) superior to others with respect to expected utility, and we try to show how our emotional makeup figures in a rational response, particularly as informed by symbolic utilitythat we draw down from our culture’s shared understandings. The category is theoretically interesting because it contains moral dilemmas, as well as hard cases in which an imponant choice must be made without an option that has clearly superior expected utility. We argue that our Emotional Response Model is preferable to Turing’s Randomizer for this category, as well as more illuminating about nil-preference situations or close approximations thereto. (shrink)

Alan Turing was probably first—in 1947, but all the ea in AI took human level as the goal. AI as an industrial with limited goals came along in the 1970s. I doubt of this research aimed at short term payoff is on any human-level AI. Indeed the researchers don’t claim it.

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...) assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.

It is shown that for every (Turing) degree 0 < a < 0´ there is a minimal degree m < 0´ such that a ∨ m = 0´ (and therefore a ∧ m = 0).

Let P 0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P 0 whose domain we suppose to be the standard integers. Let T be a recursively enumerable extension of Peano arithmetic all of whose existential consequences are satisfied in the standard model. Then there is an initial segment M ' of M which is a model of T such that the complete diagram of M ' (...) is Turing reducible to the atomic diagram of M. Moreover, neither the addition nor the multiplication of M is recursive. (shrink)

Let ϕ be a fixed numerical function. If the k-state Turing machine M with input string ϕ(k) (that is, started in its initial state scanning the leftmost 1 of a single string of ϕ(k) 1s on an otherwise blank tape) produces the output string m (that is, halts in its halting state scanning the leftmost 1 of a single string of m 1s on an otherwise blank tape), we shall say that the ϕ-fecundity of M is m. If M (...) halts in any other position or state, or fails to halt, its ϕ-fecundity is 0. (shrink)

This is the second of two volumes of essays in commemoration of Alan Turing; it celebrates his intellectual legacy within the philosophy of mind and cognitive science. A distinguished international cast of contributors focus on the relationship beteen a scientific, computational image of the mind and a common-sense picture of the mind as an inner arena populated by concepts, beliefs, intentions, and qualia. Topics covered include the causal potency of folk- psychological states, the connectionist reconception of learning and (...) concept formation, the understanding of the notion of computation itself, and the relation between philosophical and psychological theories of concepts. (shrink)

We give a new characterization of the hyperarithmetic sets: a set X of integers is recursive in e α if and only if there is a Turing machine which computes X and "halts" in less than or equal to the ordinal number ω α of steps. This result represents a generalization of the well-known "limit lemma" due to J. R. Shoenfield [Sho-1] and later independently by H. Putnam [Pu] and independently by E. M. Gold [Go]. As an application of (...) this result, we give a recursion theoretic analysis of clopen determinacy: there is a correlation given between the height α of a well-founded tree corresponding to a clopen game $A \subseteq \omega^\omega$ and the Turing degree of a winning strategy f for one of the players--roughly, f can be chosen to be recursive in 0 α and this is the best possible (see § 4 for precise results). (shrink)

Fifty years ago this month[[June]], in the Computing Machine Laboratory at Manchester University, the world's first electronic stored-program computer performed its first calculation. The tiny program, stored on the face of a cathode ray tube, was just 17 instructions long. Electronic engineers Freddie Williams and Tom Kilburn built the Manchester computer in accordance with fundamental ideas explained to them by Max Newman, professor of mathematics at Manchester. The computer fell sideways out of research that nobody could have guessed would have (...) any practical application. The initial idea germinated thirteen years earlier in the head of Alan Turing, who was working on a recherché problem in mathematical logic. While thinking about this problem Turing dreamed up an abstract machine, nowadays known simply as the 'universal Turing machine' and which, as he put it, would compute 'all numbers which could naturally be regarded as computable'. The machine consisted of a memory in.. (shrink)

From the Upanishads to Homer -- Philosophy, did the Greeks invent it -- Pythagoras and the divinity of number -- What is there? -- The Greek tragedians on man's fate -- Herodotus and the lamp of history -- Socrates on the examined life -- Plato's search for truth -- Can virtue be taught? -- Plato's Republic, man writ large -- Hippocrates and the science of life -- Aristotle on the knowable -- Aristotle on friendship -- Aristotle on the perfect life (...) -- Rome, the Stoics, and the rule of law -- The Stoic bridge to Christianity -- Roman law, making a city of the once-wide world -- The light within, Augustine on human nature -- Islam -- Secular knowledge, the idea of university -- The reappearance of experimental science -- Scholasticism and the theory of natural law -- The Renaissance, was there one? -- Let us burn the witches to save them -- Francis Bacon and the authority of experience -- Descartes and the authority of reason -- Newton, the saint of science -- Hobbes and the social machine -- Locke's Newtonian science of the mind -- No matter? The challenge of materialism -- Hume and the pursuit of happiness -- Thomas Reid and the Scottish school -- France and the philosophes -- The federalist papers and the great experiment -- What is enlightenment? Kant on freedom -- Moral science and the natural world -- Phrenology, a science of the mind -- The idea of freedom -- The Hegelians and history -- The aesthetic movement, genius -- Nietzsche at the twilight -- The liberal tradition, J.S. Mill -- Darwin and nature's "purposes" -- Marxism, dead but not forgotten -- The Freudian world -- The radical William James -- William James' pragmatism -- Wittgenstein and the discursive turn -- Alan Turing in the forest of wisdom -- Four theories of the good life -- Ontology, what there "really" is -- Philosophy of science, the last word? -- Philosophy of psychology and related confusions -- Philosophy of mind, if there is one -- What makes a problem "moral" -- Medicine and the value of life -- On the nature of law -- Justice and just wars -- Aesthetics, beauty without observers -- God, really? (shrink)

My claim is clear and unambiguous: no machine will pass a well-designed Turing Test unless we find some means of embedding it in lived social life. We have no idea how to do this but my argument, and all our evidence, suggests that it will not be a necessary condition that the machine have more than a minimal body. Exactly how minimal is still being worked out.

In this book, Livingston develops the political implications of formal results obtained over the course of the twentieth century in set theory, metalogic, and computational theory. He argues that the results achieved by thinkers such as Cantor, Russell, Gödel, Turing, and Cohen, even when they suggest inherent paradoxes and limitations to the structuring capacities of language or symbolic thought, have far-reaching implications for understanding the nature of political communities and their development and transformation. Alain Badiou's analysis of logical-mathematical structures (...) forms the backbone of his comprehensive and provocative theory of ontology, politics, and the possibilities of radical change. Through interpretive readings of Badiou's work as well as the texts of Giorgio Agamben, Jacques Lacan, Jacques Derrida, Gilles Deleuze, and Ludwig Wittgenstein, Livingston develops a formally based taxonomy of critical positions on the nature and structure of political communities. These readings, along with readings of Parmenides and Plato, show how the formal results can transfigure two interrelated and ancient problems of the One and the Many: the problem of the relationship of a Form or Idea to the many of its participants, and the problem of the relationship of a social whole to its many constituents. (shrink)

sn y™to˜er —nd xovem˜er IWHUD just over two ye—rs —fter the ™ompletion of his spe™i—l theory of rel—tivityD iinstein m—de the ˜re—kthrough th—t set him on the p—th to the gener—l theory of rel—tivityF ‡hile prep—ring — review —rti™le on his new spe™i—l theory of rel—tivityD he ˜e™—me ™onvin™ed th—t the key to the extension of the prin™iple of rel—tivity to —™™eler—ted motion l—y in the rem—rk—˜le —nd unexpl—ined empiri™—l ™oin™iden™e of the equ—lity of inerti—l —nd gr—vit—tion—l m—ssesF „o interpret (...) —nd exploit this ™oin™iden™eD he introdu™ed — new —nd powerful physi™—l prin™ipleD soon to ˜e ™—lled the ’prin™iple of equiv—len™e4 upon whi™h his se—r™h for — gener—l theory of reE l—tivity would ˜e ˜—sedF woreoverD with the ™ompletion of the theory —nd throughout the rem—inder of his lifeD iinstein insisted on the fund—ment—l import—n™e of the prin™iple to his gener—l theory of rel—tivityF iinstein9s insisten™e on this point h—s ™re—ted — puzzle for philosophers —nd histori—ns of s™ien™eF st h—s ˜een —rgued vigorously th—t the prin™iple in its tr—dition—l formul—tion does not hold in th™ gener—l theory of rel—tivityD gonsiderD for ex—mpleD — tr—dition—l formul—tion su™h —s €—uli9s in his IWPI Encyklopadie —rti™leF por €—uli the prin™iple —sserts th—t one ™—n —lw—ys tr—nsform —w—y —n —r˜itr—ry gr—vit—tion—l eld in —n innitely sm—ll region of sp—™eEtimeD ˜y tr—nsforming to —n —ppropri—te ™oordin—te system @€—uli IWPID pF IRSAF sn responseD su™h eminent rel—tivists —s ƒynge @IWTHD pF ixAD —nd even iddington ˜efore him @IWPRD ppF QW{RIAD h—ve o˜je™ted th—t — ™oordin—te tr—nsform—tion or ™h—nge of st—te of motion of the o˜server ™—n h—ve no ee™t on the presen™e or —˜sen™e of — gr—vit—tion—l eldF „he presen™e of — ’true4 gr—vit—tion—l eld is determined ˜y —n inv—ri—nt ™riterionD the ™urv—ture of the metri™F „he gr—vit—tionEfree ™—se of spe™i—l rel—tivity is just the ™—se in whi™h this ™urv—ture v—nishesD where—s the true gr—vit—tion—l elds of gener—l rel—tivity —re distinguished ˜y the nonv—nishing of this ™urv—tureF „his o˜je™tion h—s immedi—te r—mi™—tions for the ’iinstein elev—tor4 thought experimentD whi™h is ™ommonly used in the formul—tion of the prinE ™iple of equiv—len™eF sn this thought experimentD — sm—ll ™h—m˜ers su™h —s.... (shrink)