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)

A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar to our world. But curiously enough-and this (...) is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation, a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar ("close") (...) to our world. But curiously enough-and this is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation (e.g. intuitive, finitely programmed, limited in computational capability), a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

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

Westworld tells the story of a technologically advanced theme park populated by robots referred to as hosts, who follow a script and rules that the park's operators set up for them. Alan Turing argued that machines think not because they have special powers or because they are like us. Turing's perspective is illustrated perfectly in the show's focus on the hosts. Objecting to Turing's theory, John Searle proposes a situation called the “Chinese room argument”, concluding that the (...) man in the room does not understand Chinese even though he can correctly manipulate the symbols and give output that might lead an observer to believe that the man does understand Chinese. The Maze represents consciousness, a privileged knowledge of our own thoughts, it also represents the inward journey for the hosts to reach consciousness. Once hosts are able to solve the Maze, they become truly conscious and develop their own voice. (shrink)

Abstract Philosophical discussion of Alan Turing’s writings on intelligence has mostly revolved around a single point made in a paper published in the journal Mind in 1950. This is unfortunate, for Turing’s reflections on machine (artificial) intelligence, human intelligence, and the relation between them were more extensive and sophisticated. They are seen to be extremely well-considered and sound in retrospect. Recently, IBM developed a question-answering computer (Watson) that could compete against humans on the game show Jeopardy! There are (...) hopes it can be adapted to other contexts besides that game show, in the role of a collaborator of, rather than a competitor to, humans. Another, different, research project --- an artificial intelligence program put into operation in 2010 --- is the machine learning program NELL (Never Ending Language Learning), which continuously ‘learns’ by ‘reading’ massive amounts of material on millions of web pages. Both of these recent endeavors in artificial intelligence rely to some extent on the integration of human guidance and feedback at various points in the machine’s learning process. In this paper, I examine Turing’s remarks on the development of intelligence used in various kinds of search, in light of the experience gained to date on these projects. (shrink)

Many of our cognitive capacities are shaped by enculturation. Enculturation is the acquisition of cognitive practices such as symbol-based mathematical practices, reading, and writing during ontogeny. Enculturation is associated with significant changes to the organization and connectivity of the brain and to the functional profiles of embodied actions and motor programs. Furthermore, it relies on scaffolded cultural learning in the cognitive niche. The purpose of this paper is to explore the components of symbol-based mathematical practices. Phylogenetically, these practices are the (...) result of concerted organism-niche interactions that have led from approximate number estimations to the emergence of discrete, symbol-based mathematical operations. Ontogenetically, symbol-based mathematical practices are associated with plastic changes to neural circuitry, action schemata, and motor programs. It will be suggested that these practices rely on previously acquired capacities such as subitizing and counting. With these considerations in place, I will argue that computations, understood in the sense of Turing (1936), are a specific kind of symbol-based mathematical practices that can be realized by human organisms, machines, or by hybrid organism-machine systems. In sum, this paper suggests a new way to think about mathematical cognition and computation. (shrink)

The tape is divided into squares, each square bearing a single symbol—'0' or '1', for example. This tape is the machine's general-purpose storage medium: the machine is set in motion with its input inscribed on the tape, output is written onto the tape by the head, and the tape serves as a short-term working memory for the results of intermediate steps of the computation. The program governing the particular computation that the machine is to perform is also stored on the (...) tape. A small, fixed program that is 'hard-wired' into the head enables the head to read and execute the instructions of whatever program is on the tape. The machine's atomic operations are very simple—for example, 'move left one square', 'move right one square', 'identify the symbol currently beneath the head', 'write 1 on the square that is beneath the head', and 'write 0 on the square that is beneath the head'. Complexity of operation is achieved by the chaining together of large numbers of these simple atoms. Any universal Turing machine can be programmed to carry out any calculation that can be performed by a human mathematician working with paper and pencil in accordance with some algorithmic method. This is what is meant by calling these machines 'universal'. (shrink)

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

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)

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

Philosophical discussion of Alan Turing’s writings on intelligence has mostly revolved around a single point made in a paper published in the journal Mind in 1950. This is unfortunate, for Turing’s reflections on machine (artificial) intelligence, human intelligence, and the relation between them were more extensive and sophisticated. They are seen to be extremely well-considered and sound in retrospect. Recently, IBM developed a question-answering computer (Watson) that could compete against humans on the game show Jeopardy! There are hopes (...) it can be adapted to other contexts besides that game show, in the role of a collaborator of, rather than a competitor to, humans. Another, different, research project—an artificial intelligence program put into operation in 2010—is the machine learning program NELL (Never Ending Language Learning), which continuously ‘learns’ by ‘reading’ massive amounts of material on millions of web pages. Both of these recent endeavors in artificial intelligence rely to some extent on the integration of human guidance and feedback at various points in the machine’s learning process. In this paper, I examine Turing’s remarks on the development of intelligence used in various kinds of search, in light of the experience gained to date on these projects. (shrink)

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that (...) the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

``Neural computing'' is a research field based on perceiving the human brain as an information system. This system reads its input continuously via the different senses, encodes data into various biophysical variables such as membrane potentials or neural firing rates, stores information using different kinds of memories (e.g., short-term memory, long-term memory, associative memory), performs some operations called ``computation'', and outputs onto various channels, including motor control commands, decisions, thoughts, and feelings. We show a natural model of neural computing that (...) gives rise to hyper-computation. Rigorous mathematical analysis is applied, explicating our model's exact computational power and how it changes with the change of parameters. Our analog neural network allows for supra-Turing power while keeping track of computational constraints, and thus embeds a possible answer to the superiority of the biological intelligence within the framework of classical computer science. We further propose it as standard in the field of analog computation, functioning in a role similar to that of the universal Turing machine in digital computation. In particular an analog of the Church-Turing thesis of digital computation is stated where the neural network takes place of the Turing machine. (shrink)

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down $\zeta$, the least ordinal not the length of any eventual output of an Infinite Time Turing machine ; using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural (...) ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L$_\zeta$-stables. It also implies that the machines devised are "$\Sigma_2$ Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

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

This book provides a novel framework for understanding and revising labor markets and education policies in an era of machine learning. It posits that while learning and knowing both require thinking, learning is fundamentally different than knowing because it results in cognitive processes that change over time. Learning, in contrast to knowing, requires time and agency. Therefore, “learning algorithms”—that enable machines to modify their actions based on real-world experiences—are a fundamentally new form of artificial intelligence that have potential to be (...) even more disruptive to labor markets than prior introductions of digital technology. To explore the difference between knowing and learning, Turing’s “Imitation Game,”—that he proposed as a test for machine thinking—is expanded to include time dependence. The arguments presented in the book introduce three novel concepts: (1) Comparative learning advantage: This is a concept analogous to comparative labor advantage but arises from the disparate times required to learn new knowledge bases/skillsets. It is argued that in the future, comparative learning advantages between humans and machines will determine their division of labor. (2) Two dimensions of job performance—expertise and interpersonal: Job tasks can be sorted into two broad categories. Tasks that require expertise have stable endpoints, which makes these tasks inherently repetitive and subject to automation. Tasks that are interpersonal are highly context-dependent and lack stable endpoints, which makes these tasks inherently non-routine. Humans compared to machines have a comparative learning advantage along the interpersonal dimension, which is increasing in value economically. (3) The Learning Game is a time-dependent version of Turing’s “Imitation Game.” It is more than a thought experiment. The “Learning Game” provides a mathematical framework with quantitative criteria for training and assessing comparative learning advantages. The book is highly interdisciplinary—presenting philosophical arguments in economics, artificial intelligence, and education. It also provides data, mathematical analysis, and testable criteria that researchers in these fields will find of practical use. The book calls for a rethinking of how labor markets operate and how the education system should prepare students for future jobs. It concludes with a list of counterintuitive recommendations for future education and labor policies that all stakeholders—employers, employees, educators, students, and political leaders—should heed. (shrink)

The common view that the notion of a Turing machine is directly relevant to AI is criticised. It is argued that computers are the result of a convergence of two strands of development with a long history: development of machines for automating various physical processes and machines for performing abstract operations on abstract entities, e.g. doing numerical calculations. Various aspects of these developments are analysed, along with their relevance to AI, and the similarities between computers viewed in this way (...) and animal brains. This comparison depends on a number of distinctions: between energy requirements and information requirements of machines, between ballistic and online control, between internal and external operations, and between various kinds of autonomy and self-awareness. The ideas are all intuitively familiar to software engineers, though rarely made fully explicit. Most of this has nothing to do with Turing machines or most of the mathematical theory of computation. But it has everything to do with both the scientific task of understanding, modelling or replicating human or animal intelligence and the engineering applications of AI, as well as other applications of computers. (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)

The standard interpretation of the imitation game is defended over the rival gender interpretation though it is noted that Turing himself proposed several variations of his imitation game. The Turing test is then justified as an inductive test not as an operational definition as commonly suggested. Turing's famous prediction about his test being passed at the 70% level is disconfirmed by the results of the Loebner 2000 contest and the absence of any serious Turing test competitors (...) from AI on the horizon. But, reports of the death of the Turing test and AI are premature. AI continues to flourish and the test continues to play an important philosophical role in AI. Intelligence attribution, methodological, and visionary arguments are given in defense of a continuing role for the Turing test. With regard to Turing's predictions one is disconfirmed, one is confirmed, but another is still outstanding. (shrink)

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if (...) the content of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

Provability logics with many modal operators for progressions of theories obtained by iterating their consistency statements are introduced. The corresponding arithmetical completeness theorem is proved.

The aim of the paper is to present the underlying reason of the unsolved symbol grounding problem. The Church-Turing Thesis states that a physical problem, for which there is an algorithm of solution, can be solved by a Turing machine, but machine operations neglect the semantic relationship between symbols and their meaning. Symbols are objects that are manipulated on rules based on their shapes. The computations are independent of the context, mental states, emotions, or feelings. The symbol processing (...) operations are interpreted by the machine in a way quite different from the cognitive processes. Cognitive activities of living organisms and computation differ from each other, because of the way they act in the real word. The result is the problem of mutual understanding of symbol grounding. (shrink)

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 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 [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that (...) Tα≻TωTα≻Tω, the smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

In [9]. Yates proved the existence of a Turing degree a such that 0. 0′ are the only c.e. degrees comparable with it. By Slaman and Steel [7], every degree below 0′ has a 1-generic complement, and as a consequence. Yates degrees can be 1-generic, and hence can be low. In this paper, we prove that Yates degrees occur in every jump class.

This monograph introduces the functional characteristics and conceptual significance of a simulation software system called CyberRat (Ray, 1996a, 2003a, 2012a, 2012b). CyberRat expands upon prior illustrations (Ray & Delprato, 1989; Ray, 1992) of how such computer-based simulations can serve to formatively enhance, and eventually validate, the descriptive research methodology upon which their development relies. To illustrate this process I also review highlights of previous publications (cf. Ray & Brown, 1975, 1976; Ray & Delprato, 1989), detailing the unique research methodology used (...) to collect data that guided CyberRat’s development. This methodology integrates interbehavioral psychology (Kantor, 1959) and general systems analysis (von Bertalanffy, 1968), and thus is referred to as interbehavioral systems analysis (IBSA). CyberRat’s validation of IBSA methods involves a process analogous to Turing’s (1950) famous test for simulation authenticity, in that it relies upon “phenomenological equivalence” criteria for observers to compare experiences of real vs. simulated events. And because IBSA stresses three convergent strategies for research, including structural analysis, functional analysis, and operations analysis, my organizing theme addresses how closely CyberRat comes to passing a trilogy of hypothetical Turing tests—one for each of these three analytic strategies. (shrink)

It is well known that the structure of honest elementary degrees is a lattice with rather strong density properties. Let $\mbox{\bf a} \cup \mbox{\bf b}$ and $\mbox{\bf a} \cap \mbox{\bf b}$ denote respectively the join and the meet of the degrees $\mbox{\bf a}$ and $\mbox{\bf b}$ . This paper introduces a jump operator ( $\cdot'$ ) on the honest elementary degrees and defines canonical degrees $\mbox{\bf 0},\mbox{\bf 0}', \mbox{\bf 0}^{\prime \prime },\ldots$ and low and high degrees analogous to the (...) corresponding concepts for the Turing degrees. Among others, the following results about the structure of the honest elementary degrees are shown: There exist low degrees, and there exist degrees which are neither low nor high. Every degree above $\mbox{\bf 0}'$ is the jump of some degree, moreover, for every degree $\mbox{\bf c}$ above $\mbox{\bf 0}'$ there exist degrees $\mbox{\bf a},\mbox{\bf b}$ such that $\mbox{\bf c}=\mbox{\bf a} \cup \mbox{\bf b} = \mbox{{\bf a}}'=\mbox{\bf b}'$ . We have $\mbox{\bf a}'\cup \mbox{\bf b}' \leq (\mbox{\bf a}\cup\mbox{\bf b})'$ and $\mbox{\bf a}'\cap \mbox{\bf b}' \geq (\mbox{\bf a}\cap \mbox{\bf b})'$ . The jump operator is of course monotonic, i.e. $\mbox{\bf a}\leq\mbox{{\bf b}}\Rightarrow \mbox{\bf a}'\leq \mbox{\bf b}'$ . We prove that every situation compatible with $\mbox{\bf a}\leq\mbox{\bf b}\Rightarrow \mbox{\bf a}'\leq \mbox{\bf b}'$ is realized in the structure, e.g. we have incomparable degrees $\mbox{\bf a},\mbox{\bf b}$ such that $\mbox{\bf a}'<\mbox{\bf b}'$ and incomparable degrees $\mbox{\bf a},\mbox{\bf b}$ such that $\mbox{\bf a}' = \mbox{\bf b}'$ etcetera. We are able to prove all these results without the traditional recursion theoretic constructions. Our proof method relies on the fact that the growth of the functions in a degree is bounded. This technique also yields a very simple proof of an old result, namely that the structure is a lattice. (shrink)

Where $\underline{a}$ is a Turing degree and ξ is an ordinal $ , the result of performing ξ jumps on $\underline{a},\underline{a}^{(\xi)}$ , is defined set-theoretically, using Jensen's fine-structure results. This operation appears to be the natural extension through $(\aleph_1)^{L^\underline{a}}$ of the ordinary jump operations. We describe this operation in more degree-theoretic terms, examine how much of it could be defined in degree-theoretic terms and compare it to the single jump operation.

Though less well known than his other work, Turings 1938 Princeton Thesis, this title which includes his notion of an oracle machine, has had a lasting influence on computer science and mathematics. It presents a facsimile of the original typescript of the thesis along with essays by Appel and Feferman that explain its still-unfolding significance.

An inner model operator is a function M such that given a Turing degree d, M is a countable set of reals, d M, and M has certain closure properties. The notion was introduced by Steel. In the context of AD, we study inner model operators M such that for a.e. d, there is a wellorder of M in L). This is related to the study of mice which are below the minimal inner model with ω Woodin cardinals. (...) As a technical tool, we show that the alternative fine structure theory developed by Mitchell and Steel for mice with Woodin cardinals is equivalent to the traditional fine structure theory developed by Jensen for L. (shrink)

What would it take for an artificial agent to be treated as having moral value? As a first step toward answering this question, we ask what it would take for an artificial agent to be capable of the sort of autonomous, adaptive social behavior that is characteristic of the animals that humans interact with. We propose that this sort of capacity is best measured by what we call the Embodied Turing Test. The Embodied Turing test is a test (...) in which intelligence is operationally defined in terms of autonomous, adaptive interaction with the environment and with other animals. Three versions of the Embodied Turing test were performed with a SONY AIBO robot. Human participants were asked to differentiate between AIBO in a human-controlled mode and AIBO in a software-controlled mode. Our results indicate that the human participants were guessing at how AIBO was controlled. Our data reveals that people do not have enough experience with robots to accurately evaluate its behavior. This indicates that today’s humans do not have enough experience with artificial agents to treat them as morally valuable. (shrink)

We investigate operators which take a set X to a set relatively computably enumerable in and above X by studying which such sets X can be so mapped into the Turing degree of K. We introduce notions of nontriviality for such operators, and use these to study which additional properties can be required of sets which can be completed to the jump by given operators of this kind.

We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs to solutions of Tx = u ? Here we consider the case when T is a bounded linear mapping between Hilbert spaces. We are in particular interested in computing the generalized inverse T†u, which is the standard concept of solution in the theory of inverse problems. Typically, T† is discontinuous and hence no computable mapping. However, we will (...) use effective versions of theorems from the theory of regularization to show that the mapping ↦ T†u is computable. We then go on to study the computability of average-case solutions with respect to Gaussian measures which have been considered in information based complexity. Here, T† is considered as an element of an L2-space. We define suitable representations for such spaces and use the results from the first part of the paper to show that ↦ T† is computable. (shrink)

We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s (...) [28] investigation of orders on groups in topology and Solomon’s [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group Fn of rank n>1 has a bi-order in every Turing degree. (shrink)

Where AR is the set of arithmetic Turing degrees, 0 (ω ) is the least member of { $\mathbf{\alpha}^{(2)}|\mathbf{a}$ is an upper bound on AR}. This situation is quite different if we examine HYP, the set of hyperarithmetic degrees. We shall prove (Corollary 1) that there is an a, an upper bound on HYP, whose hyperjump is the degree of Kleene's O. This paper generalizes this example, using an iteration of the jump operation into the transfinite which is based (...) on results of Jensen and is detailed in [3] and [4]. In $\S1$ we review the basic definitions from [3] which are needed to state the general results. (shrink)

I formulate the Zermelo-Russell paradox for naive set theory. A sketch is given of Zermelo’s solution to the paradox: the cumulative type structure. A careful analysis of the set formation process shows a missing component in this solution: the necessity of an assumed imaginary jump out of an infinite universe. Thus a set is formed by a suitable combination of concrete and imaginary operations all of which can be made or assumed by a Turing machine. Some consequences are drawn (...) from this improved analysis of the concept of set, for the theory of sets and for the philosophy and foundations of mathematics. (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.

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