B. Jack Copeland

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.

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'

A myth has arisen concerning Turing's paper of 1936, namely that Turing set forth a fundamental principle concerning the limits of what can be computed by machine - a myth that has passed into cognitive science and the philosophy of mind, to wide and pernicious effect. This supposed principle, sometimes incorrectly termed the 'Church-Turing thesis', is the claim that the class of functions that can be computed by machines is identical to the class of functions that can be computed by Turing machines. In point of fact Turing himself nowhere endorses, nor even states, this claim (nor does Church). I describe a number of notional machines, both analogue and digital, that can compute more than a universal Turing machine. These machines are exemplars of the class of _nonclassical_ computing machines. Nothing known at present rules out the possibility that machines in this class will one day be built, nor that the brain itself is such a machine. These theoretical considerations undercut a number of foundational arguments that are commonly rehearsed in cognitive science, and gesture towards a new class of cognitive models.

The tense tree method extends Jeffrey’s well-known formulation of classical propositional logic to tense logic (Jeffrey 1991).1 Tense trees combine pure tense logic with features of Prior’s U-calculi (where ‘U’ is the earlier-than relation; see Prior 1967 and the Introduction to this volume). The tree method has a number of virtues: trees are well suited to computational applications; semantically, the tree systems presented here are no less illuminating than model theory; the metatheory associated with tree formulations is often more tractable than that required in a model-theoretic setting; and last but not least the tree method is ideal for pedagogical purposes.

Presupposing no familiarity with the technical concepts of either philosophy or computing, this clear introduction reviews the progress made in AI since the inception of the field in 1956. Copeland goes on to analyze what those working in AI must achieve before they can claim to have built a thinking machine and appraises their prospects of succeeding. There are clear introductions to connectionism and to the language of thought hypothesis which weave together material from philosophy, artificial intelligence and neuroscience. John Searle's attacks on AI and cognitive science are countered and close attention is given to foundational issues, including the nature of computation, Turing Machines, the Church-Turing Thesis and the difference between classical symbol processing and parallel distributed processing. The book also explores the possibility of machines having free will and consciousness and concludes with a discussion of in what sense the human brain may be a computer.

Alan M. Turing, pioneer of computing and WWII codebreaker, is one of the most important and influential thinkers of the twentieth century. In this volume for the first time his key writings are made available to a broad, non-specialist readership. They make fascinating reading both in their own right and for their historic significance: contemporary computational theory, cognitive science, artificial intelligence, and artificial life all spring from this ground-breaking work, which is also rich in philosophical and logical insight. An introduction by leading Turing expert Jack Copeland provides the background and guides the reader through the selection. About Alan Turing Alan Turing FRS OBE, (1912-1954) studied mathematics at King's College, Cambridge. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. During 1936-1938 Turing continued his studies, now at Princeton University. He completed a PhD in mathematical logic, analysing the notion of 'intuition' in mathematics and introducing the idea of oracular computation, now fundamental in mathematical recursion theory. An 'oracle' is an abstract device able to solve mathematical problems too difficult for the universal Turing machine. In the summer of 1938 Turing returned to his Fellowship at King's. When WWII started in 1939 he joined the wartime headquarters of the Government Code and Cypher School (GC&CS) at Bletchley Park, Buckinghamshire. Building on earlier work by Polish cryptanalysts, Turing contributed crucially to the design of electro-mechanical machines ('bombes') used to decipher Enigma, the code by means of which the German armed forces sought to protect their radio communications. Turing's work on the version of Enigma used by the German navy was vital to the battle for supremacy in the North Atlantic. He also contributed to the attack on the cyphers known as 'Fish'. Based on binary teleprinter code, Fish was used during the latter part of the war in preference to morse-based Enigma for the encryption of high-level signals, for example messages from Hitler and other members of the German High Command. It is estimated that the work of GC&CS shortened the war in Europe by at least two years. Turing received the Order of the British Empire for the part he played. In 1945, the war over, Turing was recruited to the National Physical Laboratory (NPL) in London, his brief to design and develop an electronic computer - a concrete form of the universal Turing machine. Turing's report setting out his design for the Automatic Computing Engine (ACE) was the first relatively complete specification of an electronic stored-program general-purpose digital computer. Delays beyond Turing's control resulted in NPL's losing the race to build the world's first working electronic stored-program digital computer - an honour that went to the Royal Society Computing Machine Laboratory at Manchester University, in June 1948. Discouraged by the delays at NPL, Turing took up the Deputy Directorship of the Royal Society Computing Machine Laboratory in that year. Turing was a founding father of modern cognitive science and a leading early exponent of the hypothesis that the human brain is in large part a digital computing machine, theorising that the cortex at birth is an 'unorganised machine' which through 'training' becomes organised 'into a universal machine or something like it'. He also pioneered Artificial Intelligence. Turing spent the rest of his short career at Manchester University, being appointed to a specially created Readership in the Theory of Computing in May 1953. He was elected a Fellow of the Royal Society of London in March 1951 (a high honour).

Fifty years ago this month[[June]], in the Computing Machine Laboratory at Manchester University, the world's first electronic stored-program computer performed its first calculation. The tiny program, stored on the face of a cathode ray tube, was just 17 instructions long. Electronic engineers Freddie Williams and Tom Kilburn built the Manchester computer in accordance with fundamental ideas explained to them by Max Newman, professor of mathematics at Manchester. The computer fell sideways out of research that nobody could have guessed would have any practical application. The initial idea germinated thirteen years earlier in the head of Alan Turing, who was working on a recherché problem in mathematical logic. While thinking about this problem Turing dreamed up an abstract machine, nowadays known simply as the 'universal Turing machine' and which, as he put it, would compute 'all numbers which could naturally be regarded as computable'. The machine consisted of a memory in..