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

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)

A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis the degree of categoricity of${\cal S}$, and there are computable copies${\cal A}$and${\cal B}$of${\cal S}$such that every isomorphism from${\cal A}$onto${\cal B}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis not the strong degree of (...) categoricity of${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].For a computable structure${\cal S}$, we introduce the notion of the spectral dimension of${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of${\cal S}$. We prove that for a nonzero natural numberN, there is a computable rigid structure${\cal M}$such that$0\prime$is the degree of categoricity of${\cal M}$, and the spectral dimension of${\cal M}$is equal toN. (shrink)

Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the (...) Jump Theorem holds for the bounded jump: do we have A≤bTB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \le _{bT}B$$\end{document} if and only if Ab≤1Bb\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A^b \le _1 B^b$$\end{document}? We show the forward direction holds but not the reverse. (shrink)

(1991). Gödel, Turing, chaitin and the question of emergence as a meta‐principle of modern physics. some arguments against reductionism. World Futures: Vol. 32, Creative Evolution in Nature, Mind, and Society, pp. 185-195.

Purpose – The purpose of this paper is to explore artificial moral agency by reflecting upon the possibility of a Moral Turing Test and whether its lack of focus on interiority, i.e. its behaviouristic foundation, counts as an obstacle to establishing such a test to judge the performance of an Artificial Moral Agent. Subsequently, to investigate whether an MTT could serve as a useful framework for the understanding, designing and engineering of AMAs, we set out to address fundamental challenges (...) within the field of robot ethics regarding the formal representation of moral theories and standards. Here, typically three design approaches to AMAs are available: top-down theory-driven models and bottom-up approaches which set out to model moral behaviour by means of models for adaptive learning, such as neural networks, and finally, hybrid models, which involve components from both top-down and bottom-up approaches to the modelling of moral agency. With inspiration from Allen and Wallace as well as Prior, we elaborate on theoretically driven approaches to machine ethics by introducing deontic tense logic. Finally, within this framework, we explore the character of human interaction with a robot which has successfully passed an MTT. Design/methodology/approach – The ideas in this paper reflect preliminary theoretical considerations regarding the possibility of establishing a MTT based on the evaluation of moral behaviour, which focusses on moral reasoning regarding possible actions. The thoughts reflected fall within the field of normative ethics and apply deontic tense logic to discuss the possibilities and limitations of artificial moral agency. Findings – The authors stipulate a formalisation of logic of obligation, time and modality, which may serve as a candidate for implementing a system corresponding to an MTT in a restricted sense. Hence, the authors argue that to establish a present moral obligation, we need to be able to make a description of the actual situation and the relevant general moral rules. Such a description can never be complete, as the combination of exhaustive knowledge about both situations and rules would involve a God eye’s view, enabling one to know all there is to know and take everything relevant into consideration before making a perfect moral decision to act upon. Consequently, due to this frame problem, from an engineering point of view, we can only strive for designing a robot supposed to operate within a restricted domain and within a limited space-time region. Given such a setup, the robot has to be able to perform moral reasoning based on a formal description of the situation and any possible future developments. Although a system of this kind may be useful, it is clearly also limited to a particular context. It seems that it will always be possible to find special cases in which a given system does not pass the MTT. This calls for a new design of moral systems with trust-related components which will make it possible for the system to learn from experience. Originality/value – It is without doubt that in the near future we are going to be faced with advanced social robots with increasing autonomy, and our growing engagement with these robots calls for the exploration of ethical issues and stresses the importance of informing the process of engineering ethical robots. Our contribution can be seen as an early step in this direction. (shrink)

The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We (...) apply this result to show that there is no Turing computable embedding of the class of graphs into the class of "rank-homogeneous" trees. The second main result says that there is a Turing computable embedding of the class of rank-homogeneous trees into the class of torsion-free Abelian groups. The third main result says that there is a "rank-preserving" Turing computable embedding of the class of rank-homogeneous trees into the class of Boolean algebras. Using this result, we show that there is a computable Boolean algebra of Scott rank ${\mathrm{\omega }}_{1}^{\mathrm{C}\mathrm{K}}$. (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. 1 With this collection, I expect it to become equally well known to philosophers.

The Turing Test, originally proposed as a simple operational definition of intelligence, has now been with us for exactly half a century. It is safe to say that no other single article in computer science, and few other articles in science in general, have generated so much discussion. The present article chronicles the comments and controversy surrounding Turing's classic article from its publication to the present. The changing perception of the Turing Test over the last fifty years (...) has paralleled the changing attitudes in the scientific community towards artificial intelligence: from the unbridled optimism of 1960's to the current realization of the immense difficulties that still lie ahead. I conclude with the prediction that the Turing Test will remain important, not only as a landmark in the history of the development of intelligent machines, but also with real relevance to future generations of people living in a world in which the cognitive capacities of machines will be vastly greater than they are now. (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)

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

Aesthetic investigations of computation are stuck in an impasse, caused by the difficulty of accounting for the ontological discrepancy between the continuity of sensation and the discreteness of digital technology. This article proposes a theoretical position intended to overcome that deadlock. It highlights how an ontological focus on continuity has entered media studies via readings of Deleuze, which attempt to build a ‘digital aisthesis’ by ascribing a ‘virtuality’ to computation. This underpins, in part, the affective turn in digital theory. In (...) contrast to such positions, this article argues for a reconceptualization of formal abstraction in computation, in order to find, within the discreteness of computational formalisms, an indeterminacy that would make computing aesthetic qua inherently generative. This indeterminacy, it is argued here, can be found by reconsidering, philosophically, Turing’s notion of ‘incomputability’. (shrink)

Anti-behaviorist arguments against the validity of the Turing Test as a sufficient condition for attributing intelligence are based on a memorizing machine, which has recorded within it responses to every possible Turing Test interaction of up to a fixed length. The mere possibility of such a machine is claimed to be enough to invalidate the Turing Test. I consider the nomological possibility of memorizing machines, and how long a Turing Test they can pass. I replicate my (...) previous analysis of this critical Turing Test length based on the age of the universe, show how considerations of communication time shorten that estimate and allow eliminating the sole remaining contingent assumption, and argue that the bound is so short that it is incompatible with the very notion of the Turing Test. I conclude that the memorizing machine objection to the Turing Test as a sufficient condition for attributing intelligence is invalid. (shrink)

En partant des derniers paragraphes de la cinquième parti du Discours de la Méthode, on a reconstitué la formulation cartésienne de la perception d’un autre moi. Les critères de l’usage du langage et de la plasticité du comportement ont été analysés à la lumière de l’idée d’une machine universelle et du test de Turing. On conclut de la faiblesse de l’argument cartésien sur l’irréductibilité de la pensée à un dispositif machinal. En tant qu’issue de la difficulté, on propose une (...) révision de la façon cartésienne de caractérisation de la pensée à partir du concept d’expérience, tout en abandonnant le thème d’une perception interne incommunicable et intémoignable. (shrink)

Due to his significant role in the development of computer technology and the discipline of artificial intelligence, Alan Turing has supposedly subscribed to the theory of mind that has been greatly inspired by the power of the said technology which has eventually become the dominant framework for current researches in artificial intelligence and cognitive science, namely, computationalism or the computational theory of mind. In this essay, I challenge this supposition. In particular, I will try to show that there is (...) no evidence in Turing’s two seminal works that supports such a supposition. His 1936 paper is all about the notion of computation or computability as it applies to mathematical functions and not to the nature or workings of intelligence. On the other hand, while his 1950 work is about intelligence, it is, however, particularly concerned with the problem of whether intelligence can be attributed to computing machines and not of whether computationality can be attributed to human intelligence or to intelligence in general. (shrink)

This concise work is a study of the semantical aspects of various paradoxes arising in formal logic. The author constructs a second-order system T with an interpretation in order to provide apparatus for stating and dodging the antinomies. After presenting a number of paradoxes, the author discusses a semantic vicious-circle principle, and provides a clarification of the problems by its application. He then discusses semantic aspects of some classical meta-mathematical results of Gödel, Tarski, Kleene, and Turing on unsolvable problems. (...) Also treated is the topic of impredicative definition in mathematics, especially as it relates to the vicious-circle principle.—P. J. M. (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)

We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.

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, Godel, 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)

The uncanny valley—the unnerving nature of humanlike robots—is an intriguing idea, but both its existence and its underlying cause are debated. We propose that humanlike robots are not only unnerving, but are so because their appearance prompts attributions of mind. In particular, we suggest that machines become unnerving when people ascribe to them experience, rather than agency. Experiment 1 examined whether a machine’s humanlike appearance prompts both ascriptions of experience and feelings of unease. Experiment 2 tested whether a machine capable (...) of experience remains unnerving, even without a humanlike appearance. Experiment 3 investigated whether the perceived lack of experience can also help explain the creepiness of unfeeling humans and philosophical zombies. These experiments demonstrate that feelings of uncanniness are tied to perceptions of experience, and also suggest that experience—but not agency—is seen as fundamental to humans, and fundamentally lacking in machines. (shrink)

Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.