References in:
On the Possibilities of Hypercomputing Supertasks
Minds and Machines 21 (1):8396 (2011)
Add references
You must login to add references.


We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis. 

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

We describe in some detail how to build an infinite computing machine within a continuous Newtonian universe. The relevance of our construction to the ChurchTuring thesis and the PlatonistIntuitionist debate about the nature of mathematics is also discussed. 

We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous nogo claims against quantum hypercomputation are then reviewed in the light of this new positive proposal. 

A version of the ChurchTuring Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, nonwellfounded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) 

The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation (...) 



In his bestselling work of popular science, Sir Roger Penrose takes us on a fascinating rollercoaster ride through the basic principles of physics, cosmology, mathematics, and philosophy to show that human thinking can never be emulated by a machine. 



The Church–Turing Thesis (CTT) is often employed in arguments for computationalism. I scrutinize the most prominent of such arguments in light of recent work on CTT and argue that they are unsound. Although CTT does nothing to support computationalism, it is not irrelevant to it. By eliminating misunderstandings about the relationship between CTT and computationalism, we deepen our appreciation of computationalism as an empirical hypothesis. 

In Computers Ltd, David Harel, bestselling author of Algorithmics, explains and illustrates one of the most fundamental, yet underexposed facets of computers  their inherent limitations. Looking at the bad news that is proven, lasting, and robust, discussing limitations that no amounts of hardware, software, talents, or resources can overcome, the book presents a disturbing and provocative view of computing at the start of the 21st century. 



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. 

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 'ChurchTuring 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 (...) 

Alan Turing anticipated many areas of current research incomputer and cognitive science. This article outlines his contributionsto Artificial Intelligence, connectionism, hypercomputation, andArtificial Life, and also describes Turing's pioneering role in thedevelopment of electronic storedprogram digital computers. It locatesthe origins of Artificial Intelligence in postwar Britain. It examinesthe intellectual connections between the work of Turing and ofWittgenstein in respect of their views on cognition, on machineintelligence, and on the relation between provability and truth. Wecriticise widespread and influential misunderstandings of theChurch–Turing thesis (...) 



A survey of the field of hypercomputation, including discussion of a variety of objections. 



Hypercomputation—the hypothesis that Turingincomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinitetime oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for nonterminating processes are likewise (...) 



In my book How the Mind Works, I defended the theory that the human mind is a naturally selected system of organs of computation. Jerry Fodor claims that 'the mind doesn't work that way'(in a book with that title) because (1) Turing Machines cannot duplicate humans' ability to perform abduction (inference to the best explanation); (2) though a massively modular system could succeed at abduction, such a system is implausible on other grounds; and (3) evolution adds nothing to our understanding (...) 

We claim that a recent article of P. Cotogno ([2003]) in this journal is based on an incorrect argument concerning the noncomputability of diagonal functions. The point is that whilst diagonal functions are not computable by any function of the class over which they diagonalise, there is no ?logical incomputability? in their being computed over a wider class. Hence this ?logical incomputability? regrettably cannot be used in his argument that no hypercomputation can compute the Halting problem. This seems to lead (...) 

Some philosophers have conflated functionalism and computationalism. I reconstruct how this came about and uncover two assumptions that made the conflation possible. They are the assumptions that (i) psychological functional analyses are computational descriptions and (ii) everything may be described as performing computations. I argue that, if we want to improve our understanding of both the metaphysics of mental states and the functional relations between them, we should reject these assumptions. 

Cognition is commonly taken to be computational manipulation of representations. These representations are assumed to be digital, but it is not usually specified what that means and what relevance it has for the theory. I propose a specification for being a digital state in a digital system, especially a digital computational system. The specification shows that identification of digital states requires functional directedness, either for someone or for the system of which it is a part. In the case or digital (...) 

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

Jerry Fodor argues against the widely held view that mental processes are largely computations, that the architecture of cognition is massively modular, and... 





Winner of the Wolf Prize for his contribution to our understanding of the universe, Penrose takes on the question of whether artificial intelligence will ever ... 

Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel’s incompleteness theorems, but also a large number of optional topics, from Turing’s theory of computability to Ramsey’s theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a (...) 



Of John Wheeler’s ‘Really Big Questions’, the one on which the most progress has been made is It From Bit? – does information play a significant role at the foundations of physics? It is perhaps less ambitious than some of the other Questions, such as How Come Existence?, because it does not necessarily require a metaphysical answer. And unlike, say, Why The Quantum?, it does not require the discovery of new laws of nature: there was room for hope that it (...) 



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. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semidecidable sets form a portion of the $\Delta^1_2$ sets. 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. 









_Philosophy and Computing_ explores each of the following areas of technology: the digital revolution; the computer; the Internet and the Web; CDROMs and Mulitmedia; databases, textbases, and hypertexts; Artificial Intelligence; the future of computing. Luciano Floridi shows us how the relationship between philosophy and computing provokes a wide range of philosophical questions: is there a philosophy of information? What can be achieved by a classic computer? How can we define complexity? What are the limits of quantam computers? Is the Internet (...) 



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. 





A new computationalist view of the mind that takes into account realworld issues of embodiment, interaction, physical implementation, and semantics. 