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)

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.

Turing's analysis of computation is a fundamental part of the background of cognitive science. In this paper it is argued that a re‐interpretation of Turing's work is required to underpin theorizing about cognitive architecture. It is claimed that the symbol systems view of the mind, which is the conventional way of understanding how Turing's work impacts on cognitive science, is deeply flawed. There is an alternative interpretation that is more faithful to Turing's original insights, avoids the criticisms made of the (...) symbol systems approach and is compatible with the growing interest in agent‐environment interaction. It is argued that this interpretation should form the basis for theories of cognitive architecture. (shrink)

Turing was an exceptional mathematician with a peculiar and fascinating personality and yet he remains largely unknown. In fact, he might be considered the father of the von Neumann architecture computer and the pioneer of Artificial Intelligence. And all thanks to his machines; both those that Church called “Turing machines” and the a-, c-, o-, unorganized- and p-machines, which gave rise to evolutionary computations and genetic programming as well as connectionism and learning. This paper looks at all of these and (...) at why he is such an often overlooked and misunderstood figure. (shrink)

The abstract basis of modern computation is the formal description of a finite state machine, the Universal Turing Machine, based on manipulation of integers and logic symbols. In this contribution to the discourse on the computer-brain analogy, we discuss the extent to which analog computing, as performed by the mammalian brain, is like and unlike the digital computing of Universal Turing Machines. We begin with ordinary reality being a permanent dialog between continuous and discontinuous worlds. So it is with computing, (...) which can be analog or digital, and is often mixed. The theory behind computers is essentially digital, but efficient simulations of phenomena can be performed by analog devices; indeed, any physical calculation requires implementation in the physical world and is therefore analog to some extent, despite being based on abstract logic and arithmetic. The mammalian brain, comprised of neuronal networks, functions as an analog device and has given rise to artificial neural networks that are implemented as digital algorithms but function as analog models would. Analog constructs compute with the implementation of a variety of feedback and feedforward loops. In contrast, digital algorithms allow the implementation of recursive processes that enable them to generate unparalleled emergent properties. We briefly illustrate how the cortical organization of neurons can integrate signals and make predictions analogically. While we conclude that brains are not digital computers, we speculate on the recent implementation of human writing in the brain as a possible digital path that slowly evolves the brain into a genuine (slow) Turing machine. (shrink)

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

Epistrofē, ili, Fenomen "vozvrashchenii︠a︡" v pervoĭ evropeĭskoĭ kulʹture -- "Osevye veka" evropeĭskoĭ istorii -- Logika istorii -- Istina i istorii︠a︡ -- Evropeĭskiĭ istorizm (nekotorye aspekty problemy).

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)

It is perhaps in the functioning of the brain that we can make contextual information most prominent. Indeed, while von Neumann and others invented computers with mimicking the brain in mind, the brain does not appear to behave as a Turing Machine. Neither is it a mechanical automaton. There is no “gost in the machine”. However, nobody would doubt that brain manages information, and in a very efficient way. To my view this is a strong indication that the information we (...) describe when considering messages is a tiny part of what information is. Because we use language, built on the exchange of sequences of symbols, exactly as programs are exchanged in computers, linguists often saw the brain as a Turing Machine. But language is deeply associated to meaning, so that beside grammatical syntactic structures, there may exist a variety of superimposed contexts which transmit information mediated by channels that are not those usually considered. (shrink)

In this paper, we present an intelligent tutoring system developed to help students in learning Computer Theory. The Intelligent tutoring system was built using ITSB authoring tool. The system helps students to learn finite automata, pushdown automata, Turing machines and examines the relationship between these automata and formal languages, deterministic and nondeterministic machines, regular expressions, context free grammars, undecidability, and complexity. During the process the intelligent tutoring system gives assistance and feedback of many types in an intelligent manner according to (...) the behavior of the student. An evaluation of the intelligent tutoring system has revealed reasonably acceptable results in terms of its usability and learning abilities are concerned. (shrink)

We show that there are Π5 formulas in the language of the Turing degrees, [Formula: see text], with ≤, ∨ and ∧, that define the relations x″ ≤ y″, x″ = y″ and so {x ∈ L2 = x ≥ y|x″ = y″} in any jump ideal containing 0. There are also Σ6&Π6 and Π8 formulas that define the relations w = x″ and w = x', respectively, in any such ideal [Formula: see text]. In the language with just ≤ (...) the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Π2 or Σ2 formula in the language with just ≤ defines L2 or L2. Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of [Formula: see text] is fixed on every degree above 0″ and every relation on [Formula: see text] which is invariant under the double jump or under join with 0″ is definable over [Formula: see text] if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in [Formula: see text]. (shrink)

The Turing Test is claimed by many to be a way to test for the presence, in computers, of such ``deep'' phenomena as thought and consciousness. Unfortunately, attempts to build computational systems able to pass TT have devolved into shallow symbol manipulation designed to, by hook or by crook, trick. The human creators of such systems know all too well that they have merely tried to fool those people who interact with their systems into believing that these systems really have (...) minds. And the problem is fundamental: the structure of the TT is such as to cultivate tricksters. A better test is one that insists on a certain restrictive epistemic relation between an artificial agent A, its output o, and the human architect H of A – a relation which, roughly speaking, obtains when H cannot account for how A produced o. We call this test the ``Lovelace Test'' in honor of Lady Lovelace, who believed that only when computers originate things should they be believed to have minds. (shrink)

The extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately be unnecessary. The thesis would however be strongly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. BosonSampling - the sampling from a distribution of n photons undergoing some linear-optical process - is a recently developed, and experimentally accessible example of (...) such a task [1]. (shrink)

In this note, we consider constraints on the physical possibility of transfinite Turing machines that arise from how one models the continuous structure of space and time in one's best physical theories. We conclude by suggesting a version of Church's thesis appropriate as an upper bound for physical computation given how space and time are modeled on our current physical theories.

Open peer commentary on the article “Info-computational Constructivism and Cognition” by Gordana Dodig-Crnkovic. Upshot: I propose a mathematical approach to the framework developed in Dodig-Crnkovic’s target article. It points to an important property of natural computation, called the multiplicity principle (MP), which allows the development of increasingly complex cognitive processes and knowledge. While local dynamics are classically computable, a consequence of the MP is that the global dynamics is not, thus raising the problem of developing more elaborate computations, perhaps with (...) the help of Turing oracles. (shrink)

Tom 1. Rannekhristianskiĭ gnosticheskiĭ tekst v rossiĭskoĭ kulʹture (21 i︠a︡nvari︠a︡ 2011 g.) -- Tom 2. Sudʹby religiozno-filosofskikh iskaniĭ Nikolai︠a︡ Novikova i ego kruga (15-17 okti︠a︡bri︠a︡ 2012 g.).

В монографии рассматриваются различные аспекты проявления философии Платона в русской культуре. Существенное значение имеет уточнение в названии монографии - это очерки русской философской мысли. Для тех, кому небезразлична судьба истории русской философии.

We study the structure of families of theories in the language of arithmetic extended to allow these families to refer to one another and to themselves. If a theory contains schemata expressing its own truth and expressing a specific Turing index for itself, and contains some other mild axioms, then that theory is untrue. We exhibit some families of true self-referential theories that barely avoid this forbidden pattern.

Jerry Fodor presents a new development of his famous Language of Thought hypothesis, which has since the 1970s been at the centre of interdisciplinary debate about how the mind works. Fodor defends and extends the groundbreaking idea that thinking is couched in a symbolic system realized in the brain. This idea is central to the representational theory of mind which Fodor has established as a key reference point in modern philosophy, psychology, and cognitive science. The foundation stone of our present (...) cognitive science is Turing's suggestion that cognitive processes are not associations but computations; and computation requires a language of thought. So the latest on the Language of Thought hypothesis, from its progenitor, promises to be a landmark in the study of the mind. LOT 2 offers a more cogent presentation and a fuller explication of Fodor 's distinctive account of the mind, with various intriguing new features. The central role of compositionality in the representational theory of mind is revealed: most of what we know about concepts follows from the compositionality of thoughts. Fodor shows the necessity of a referentialist account of the content of intentional states, and of an atomistic account of the individuation of concepts. Not least among the new developments is Fodor 's identification and persecution of pragmatism as the leading source of error in the study of the mind today. LOT 2 sees Fodor advance undaunted towards the ultimate goal of a theory of the cognitive mind, and in particular a theory of the intentionality of cognition. No one who works on the mind can ignore Fodor 's views, expressed in the coruscating and provocative style which has delighted and disconcerted countless readers over the years. (shrink)

Posner [6] has shown, by a nonuniform proof, that every ▵ 0 2 degree has a complement below 0'. We show that a 1-generic complement for each ▵ 0 2 set of degree between 0 and 0' can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above $\varnothing'$ . In the second half of the paper, we show that the complementation (...) of the degrees below 0' does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees a above b such that no degree strictly below a joins b above a. (This result is independently due to S. B. Cooper.) We end with some open problems. (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)