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.

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)

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

El Test de Turing es un método tan controvertido como desafiante en Inteligencia Artificial. Se basa en la imitación de la conducta lingüística de humanos, y tiene como objetivo recabar evidencia empírica en favor de la tesis de que las máquinas programadas podrían pensar. Alan Turing, su creador, ha sido catalogado como conductista por la mayor parte de los comentaristas. En este capítulo muestro que no lo es. Por el contrario, Turing es un funcionalista, porque todo el énfasis del juego (...) de la imitación está en el engaño de la máquina hacia los humanos. Por ello el género es importante en dicho juego, al menos en su versión preliminar. (shrink)

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)

'Caractère', 'densité', 'texture', 'bloc', 'trait', 'profil', 'figure' ou encore 'énergie'... : ces termes, s'ils sont souvent convoqués dans le discours musicologique se référant aux oeuvres des XXe et XXIe siècles, résistent à la clôture d'une définition. De telles notions mobilisent différentes dimensions de l'écriture mais aussi - et peut-être surtout - cherchent chacune à désigner un aspect qualitatif du musical, ce 'devenir illimité' du discours, difficile à neutraliser et à rationaliser. Le colloque organisé à l'Université Paris 8, intitulé 'Manières d'être (...) du musical', dont nous éditons aujourd'hui les actes, proposait ainsi de 'connaître l'individu à travers l'individuation plutôt que l'individuation à partir de l'individu' en interrogeant les outils compositionnels et les catégories qualitatives de l'écriture ayant pour fonction de différencier le musical en comportements ou manières d'être singuliers'"--Page 4 of cover. (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)

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers $$\omega $$, having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness (...) of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for $$\Delta ^0_2$$ equivalence relations, starting with the $$\Pi ^{-1}_2$$ level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree $${\textbf{d}}$$, there exists a weakly precomplete c.e. equivalence E admitting a $${\textbf{d}}$$ -computable diagonal function. We observe that a Turing degree $${\textbf{d}}$$ can compute a diagonal function for every $$\Delta ^0_2$$ equivalence relation E if and only if $${\textbf{d}}$$ computes $${\textbf{0}}'$$. On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if $${\textbf{d}}$$ computes diagonal functions for all c.e. E, then $${\textbf{d}}$$ must be a DNC degree. (shrink)

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)

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

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

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)

If X0and X1are both generic, the theories of the degrees below X0and X1are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

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.