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.

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and (...) the theoretical limits of computability. Contrary to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

Since the beginning of the twenty-first century there has been an increasing awareness that software rep- resents a blind spot in new media theory. The growing interest in software also influences the argument in this paper, which sets out from the assumption that Alan M. Turing's concept of the universal machine, the first theoretical description of a computer program, is a kind of bachelor machine. Previous writings based on a similar hypothesis have focused either on a comparison (...) of the universal machine and the bachelor machine in terms of the similarities of their structural features, or they have taken the bachelor machine as a metaphor for a man or a computer. Unlike them, this paper stresses the importance of the con- text as a key to interpreting the universal Turing machine as a bachelor machine and, potentially, as a self-portrait. (shrink)

In I used Turing machine arguments to show that computers can recognize humanly recognizable patterns in principle. In 1978 James D. Heffernan has expressed some doubts about such arguments. He does not question the propositions that I defend in the paper, nor the specific arguments in their support. What he does criticize are certain background assumptions.

Accelerated Turing machines are Turing machines that perform tasks commonly regarded as impossible, such as computing the halting function. The existence of these notional machines has obvious implications concerning the theoretical limits of computability.

Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as “the work-horse of hypercomputation” (Potgieter and Rosinger 2010: 853). But do they really compute beyond the “Turing limit”—e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that (...) in the current literature the term “accelerating Turing machine” is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical. (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.

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)

Storrs McCall appeals to a particular true but improvable sentence of formal arithmetic to argue, by appeal to its irrefutability, that human minds transcend Turing machines. Metamathematical oversights in McCall's discussion of the Godel phenomena, however, render invalid his philosophical argument for this transcendentalist conclusion.

The properties of Turing’s famous ‘universal machine’ has long sustained functionalist intuitions about the nature of cognition. Here, I show that there is a logical problem with standard functionalist arguments for multiple realizability. These arguments rely essentially on Turing’s powerful insights regarding computation. In addressing a possible reply to this criticism, I further argue that functionalism is not a useful approach for understanding what it is to have a mind. In particular, I show that the difficulties involved (...) in distinguishing implementation from function make multiple realizability claims untestable and uninformative. As a result, I conclude that the role of Turing machines in philosophy of mind needs to be reconsidered. (shrink)

Can mind be modeled as a Turing machine? If you find such questions irrelevant, e.g. because the subject is already exhausted, then you need not read the book Mind versus Computer (Gams et al., 1991). If, on the other hand, you do find such questions relevant, then perhaps you need not read Dunlop's review of the book (Dunlop, 2000). (...).

We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one-tape computable, and so the two models of (...) infinitary computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals. (shrink)

Vann McGee has argued that, given certain background assumptions and an ought-implies-can thesis about norms of rationality, Bayesianism conflicts globally with computationalism due to the fact that Robinson arithmetic is essentially undecidable. I show how to sharpen McGee's result using an additional fact from recursion theory—the existence of a computable sequence of computable reals with an uncomputable limit. In conjunction with the countable additivity requirement on probabilities, such a sequence can be used to construct a specific proposition to which Bayesianism (...) requires an agent to assign uncomputable credence—yielding a local conflict with computationalism. (shrink)

In his article “On Mechanical Recognition” R. J. Nelson brings to bear a branch of mathematical logic called automata theory on problems of artificial intelligence. Specifically he attacks the anti-mechanist claim that “[i]nasmuch as human recognition to a very great extent relies on context and on the ability to grasp wholes with some independence of the quality of the parts, even to fill in the missing parts on the basis of expectations, it follows that computers cannot in principle be programmed (...) to recognize or learn to recognize all patterns”, p. 24). Nelson proposes, contrary to this claim, that “gestalt recognition is not beyond digital automata”. in particular, he claims, he will establish by what he calls “Turing machine arguments” that the following four theses are true: automata can recognize different pattern types in one and the same set of instances;automata can recognize the “same” pattern in different sets of instances;automata can recognize incomplete, degraded patterns having missing or indeterminate parts;automata can recognize family resemblances. (shrink)

The Turing Machine presents itself as the very landmark and initial design of digital automata present in all modern general-purpose digital computers and whose design on computable numbers implies deeply ontological as well as epistemological foundations for today’s computers. These lines of work attempt to briefly analyze the fundamental epistemological problem that rose in the late 19th and early 20th century whereby “machine cognition” emerges. The epistemological roots addressed in the TM and notably in its “Halting Problem” (...) uncovers the tension between determinism and uncertainty, regarded here as the primal and inherent features of machine cognition. Resumen La Máquina de Turing se presenta como el hito y el diseño inicial de un autómata digital presente en todas las computadoras digitales modernas de propósito general y cuyo diseño en números computables establece bases profundamente ontológicas y epistemológicas para las computadoras de hoy. Estas líneas de trabajo intentan analizar brevemente el problema epistemológico fundamental que surgió a finales del siglo XIX y principios del XX mediante el cual emerge la “cognición de la máquina”. Las raíces epistemológicas que se abordan en la TM y, en particular, en su “Problema de detención” ponen al descubierto la tensión entre el determinismo y la incertidumbre, consideradas aquí, como las características primordiales e inherentes de la cognición de la máquina. (shrink)

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)

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)

Lucas and Penrose have contended that, by displaying how any characterisation of arithmetical proof programmable into a machine allows of diagonalisation, generating a humanly recognisable proof which eludes that characterisation, Gödel's incompleteness theorem rules out any purely mechanical model of the human intellect. The main criticisms of this argument have been that the proof generated by diagonalisation (i) will not be humanly recognisable unless humans can grasp the specification of the object-system (Benacerraf); and (ii) counts as a proof only (...) on the (unproven) hypothesis that the object system is consistent (Putnam). The present paper argues that criticism (ii) may be met head-on by an intuitionistic proponent of the anti-mechanist argument; and that criticism (i) is simply mistaken. However the paper concludes by questioning the sufficiency of the situation for an interesting anti-mechanist conclusion. (shrink)

The aim of this paper is to argue about the impossibility of constructing a complete formal theory or a complete Turing machines' algorithm that represent the human capacity of recognizing mathematical truths. More specifically, based on a direct argument from Gödel's First Incompleteness Theorem, we discuss the impossibility of constructing a complete formal theory or a complete Turing machines' algorithm to the human capacity of recognition of first-order arithmetical truths and so of mathematical truths in general.

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)

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)

Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing (...) a test of a known physical theory T. Our earlier work was based upon experiments in Newtonian mechanics. Here we extend the scope of the theory of experimental oracles beyond Newtonian mechanics to electrical theory. First, we specify an experiment that measures resistance using a Wheatstone bridge and start to classify the computational power of this experimental oracle using non-uniform complexity classes. Secondly, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on our ability to measure resistance by the Wheatstone bridge. The connection between the algorithm and physical test is mediated by a protocol controlling each query, especially the physical time taken by the experimenter. In our studies we find that physical experiments have an exponential time protocol, this we formulate as a general conjecture. Our theory proposes that measurability in Physics is subject to laws which are co-lateral effects of the limits of computability and computational complexity. (shrink)

We first discuss Michael Dummett’s philosophy of mathematics and Robert Brandom’s philosophy of language to demonstrate that inferentialism entails the falsity of Church’s Thesis and, as a consequence, the Computational Theory of Mind. This amounts to an entirely novel critique of mechanism in the philosophy of mind, one we show to have tremendous advantages over the traditional Lucas-Penrose argument.

In their recent paper “Do Accelerating Turing Machines Compute the Uncomputable?” Copeland and Shagrir draw a distinction between a purist conception of Turing machines, according to which these machines are purely abstract, and Turing machine realism according to which Turing machines are spatio-temporal and causal “notional" machines. In the present response to that paper we concede the realistic aspects of Turing’s own presentation of his machines, pointed out by Copeland and Shagrir, but argue that (...) Turing's treatment of symbols in the course of that presentation opens the door for later purist conceptions. Also, we argue that a purist conception of Turing machines plays an important role not only in the analysis of the computational properties of Turing machines, but also in the philosophical debates over the nature of their realization. (shrink)

In this report I provide an introduction to the burgeoning field of hypercomputation – the study of machines that can compute more than Turing machines. I take an extensive survey of many of the key concepts in the field, tying together the disparate ideas and presenting them in a structure which allows comparisons of the many approaches and results. To this I add several new results and draw out some interesting consequences of hypercomputation for several different disciplines.

Symmetric instruction machines (SIAs) and symmetric Turing machines (STMs) are models of computation involving concepts derived from those of classical Turing machines such as tape (memory) and head (processor), but with different functional and structural characteristics. The former model (SIAs) introduced in this paper and preferred by Mark Burgin is a result of a reformulation of the latter model (STMs) published in several articles by the second author in the past. The properties of both models are analyzed and (...) compared. The word “symmetric” in both cases represents the feature of the design which is distinct from classical Turing machines where only cells on the tape change under the action of the head. In both models, symmetric computing involves changes of the tape and parallel (“symmetric”) changes of instructions listed in the head. The key difference between SIAs and STMs is in the dynamic of the changes, which in the former model has the form of compound one-way actions and in the latter model, it has the form of uniform mutual interactions, which only in specific realizations can be separated into a pair of actions. Because of the untimely passing of Mark Burgin, the discussion of the two models and cooperation on the paper has never been finished. For this reason, the arguments of both authors are reported even though, in some cases, they are mutually inconsistent or even contradictory. (shrink)

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)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been (...) theorisation that all physical systems can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

Recent advances in neuroscience lead to a wider realm for philosophy to include the science of the Darwinian-evolved computational brain, our inner world producing organ, a non-recursive super- Turing machine combining 100B synapsing-neuron DNA-computers based on the genetic code. The whole system is a logos machine offering a world map for global context, essential for our intentional grasp of opportunities. We start from the observable contrast between the chaotic universe vs. our orderly inner world, the noumenal cosmos. (...) So far, philosophy has been rehearsing our thoughts, our human-internal world, a grand painting of the outer world, how we comprehend subjectively our experience, worked up by the logos machine, but now we seek a wider horizon, how humans understand the world thanks to Darwinian evolution to adapt in response to the metaphysical gap, the chasm between the human animal and its environment, shaping the organism so it can deal with its variable world. This new horizon embraces global context coded in neural structures that support the noumenal cosmos, our inner mental world, for us as denizens of the outer environment. Kant’s inner and outer senses are fundamental ingredients of scientific philosophy. Several sections devoted to Heidegger, his lizard debunked, but his version of the metaphysical gap & his doctrine of the logos praised. Rorty and others of the behaviorist school discussed also. (shrink)