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

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)

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.

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)

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

We tell a story where an agent who chooses in such a way as to make the greatest possible profit on each of an infinite series of transactions ends up worse off than an agent who chooses in such a way as to make the least possible profit on each transaction. That is, contrary to what one might suppose, it is not necessarily rational always to choose the option that yields the greatest possible profit on each transaction.

Malament-Hogarth spacetimes are the sort of models within general relativity that seem to allow for the possibility of supertasks. There are various ways in which these spacetimes might be considered physically problematic. Here, we examine these criticisms and investigate the prospect of escaping them.

There exists a growing literature on the so-called physical Church-Turing thesis in a relativistic spacetime setting. The physical Church-Turing thesis is the conjecture that no computing device that is physically realizable can exceed the computational barriers of a Turing machine. By suggesting a concrete implementation of a beyond-Turing computer in a spacetime setting, Istvan Nemeti and Gyula David have shown how an appreciation of the physical Church-Turing thesis necessitates the confluence of mathematical, computational, physical, and indeed cosmological ideas. In this (...) essay, I will honour Istvan's seventieth birthday, as well as his longstanding interest in, and his seminal contributions to, this field going back to as early as 1987 by modestly proposing how the concrete implementation in Nemeti and D\'avid might be complemented by a quantum-information-theoretic communication protocol between the computing device and the logician who sets the beyond-Turing computer a task such as determining the consistency of Zermelo-Fraenkel set theory. This suggests that even the foundations of quantum theory and, ultimately, quantum gravity may play an important role in determining the validity of the physical Church-Turing thesis. (shrink)

We analyse the extent of possible computations following Hogarth ([2004]) conducted in Malament–Hogarth (MH) spacetimes, and Etesi and Németi ([2002]) in the special subclass containing rotating Kerr black holes. Hogarth ([1994]) had shown that any arithmetic statement could be resolved in a suitable MH spacetime. Etesi and Németi ([2002]) had shown that some relations on natural numbers that are neither universal nor co-universal, can be decided in Kerr spacetimes, and had asked specifically as to the extent of computational limits there. (...) The purpose of this note is to address this question, and further show that MH spacetimes can compute far beyond the arithmetic: effectively Borel statements (so hyperarithmetic in second-order number theory, or the structure of analysis) can likewise be resolved: Theorem A. If H is any hyperarithmetic predicate on integers, then there is an MH spacetime in which any query ? n H ? can be computed. In one sense this is best possible, as there is an upper bound to computational ability in any spacetime, which is thus a universal constant of that spacetime. Theorem C. Assuming the (modest and standard) requirement that spacetime manifolds be paracompact and Hausdorff, for any spacetime there will be a countable ordinal upper bound, , on the complexity of questions in the Borel hierarchy computable in it. Introduction 1.1 History and preliminaries Hyperarithmetic Computations in MH Spacetimes 2.1 Generalising SADn regions 2.2 The complexity of questions decidable in Kerr spacetimes An Upper Bound on Computational Complexity for Each Spacetime CiteULike Connotea Del.icio.us What's this? (shrink)

Does Nature permit the implementation of behaviours that cannot be simulated computationally? We consider the meaning of physical computation in some detail, and present arguments in favour of physical hypercomputation: for example, modern scientific method does not allow the specification of any experiment capable of refuting hypercomputation. We consider the implications of relativistic algorithms capable of solving the (Turing) Halting Problem. We also reject as a fallacy the argument that hypercomputation has no relevance because non-computable values are indistinguishable from sufficiently (...) close computable approximations. In addition to considering the nature of computability relative to any given physical theory, we can consider the relationship between versions of computability corresponding to different models of physics. Deutsch and Penrose have argued on mathematical grounds that quantum computation and Turing computation have equivalent formal power. We suggest this equivalence is invalid when considered from the physical point of view, by highlighting a quantum computational behaviour that cannot meaningfully be considered feasible in the classical universe. (shrink)

The view that the brain is a sort of computer has functioned as a theoretical guideline both in cognitive science and, more recently, in neuroscience. But since we can view every physical system as a computer, it has been less than clear what this view amounts to. By considering in some detail a seminal study in computational neuroscience, I first suggest that neuroscientists invoke the computational outlook to explain regularities that are formulated in terms of the information content of electrical (...) signals. I then indicate why computational theories have explanatory force with respect to these regularities:in a nutshell, they underscore correspondence relations between formal/mathematical properties of the electrical signals and formal/mathematical properties of the represented objects. I finally link my proposal to the philosophical thesis that content plays an essential role in computational taxonomy. (shrink)

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.

A critical survey of some attempts to define ‘computer’, beginning with some informal ones, then critically evaluating those of three philosophers, and concluding with an examination of whether the brain and the universe are computers.

This article shows a clear sense in which general relativity allows for a type of ‘machine’ that can bring about a spacetime structure suitable for the implementation of ‘supertasks’. 1Introduction2Preliminaries3Malament–Hogarth Spacetimes4Machines5Malament–Hogarth Machines6Conclusion.

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.

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.

Las máquinas aceleradas de Turing (ATMs) son dispositivos capaces de ejecutar súper-tareas. Sin embargo, el simple ejercicio de definirlas ha generado varias paradojas. En el presente artículo se definirán las nociones de súper-tarea y ATM de manera exhaustiva y se aclarará qué debe entenderse en un contexto lógico-formal cuando se pregunta por la existencia de un objeto. A partir de la distinción entre posibilidades lógicas y físicas se disolverán las paradojas y se concluirá que las ATMs son posibles y existen (...) como objetos abstractos. (shrink)

Historically models of eternity have been grounded in divine attributes rather than the intrinsic structure of space-time. I examine the topology of Minkowski spacetime in comparison to the Euclidean space of Newtonian Mechanics, before highlighting five common approaches to eternity. Both atemporal and temporal models of eternity are examined to establish what they tell us about the nature of eternity outside the divine attributes, before being evaluated for their coherence with the Special Theory of Relativity. I argue that the most (...) coherent models of eternity in light of the Special Theory of Relativity are those that appeal to metaphysical rather than physical time as it remains unaffected by the conventionality and relativity of simultaneity. I conclude that the special Theory of Relativity has a valid role to play in establishing the coherence of eternity. However, due to the discontinuity of concepts of time between the Special Theory of Relativity, the General theory of Relativity and Quantum Mechanics, it cannot single-handedly be used to establish which models of eternity cohere with scientific models of time, but must be use alongside the General theory of Relativity and Quantum Mechanics. (shrink)

This dissertation is concerned with two of the largest questions that we can ask about the nature of physical reality: first, whether physical reality begin to exist and, second, what criteria would physical reality have to fulfill in order to have had a beginning? Philosophers of religion and theologians have previously addressed whether physical reality began to exist in the context of defending the Kal{\'a}m Cosmological Argument (KCA) for theism, that is, (P1) everything that begins to exist has a cause (...) for its beginning to exist, (P2) physical reality began to exist, and, therefore, (C) physical reality has a cause for its beginning to exist. While the KCA has traditionally been used to argue for God's existence, the KCA does not mention God, has been rejected by historically significant Christian theologians such as Thomas Aquinas, and raises perennial philosophical questions -- about the nature and history of physical reality, the nature of time, the nature of causation, and so on -- that should be of interest to all philosophers and, perhaps, all humans. While I am not a religious person, I am interested in the questions raised by the KCA. In this dissertation, I articulate three necessary conditions that physical reality would need to fulfill in order to have had a beginning and argue that, given the current state of philosophical and scientific inquiry, we cannot determine whether physical reality began to exist. -/- Friends of the KCA have sought to defend their view that physical reality began to exist in two distinct ways. As I discuss in chapter 2, the first way in which friends of the KCA have sought to defend their view that physical reality began to exist involves a family of a priori arguments meant to show that, as a matter of metaphysical necessity, the past must be finite. If the past is necessarily finite, then the past history of physical reality is necessarily finite. And if having a finite past suffices for having a beginning, then, since the past history of physical reality is necessarily finite, physical reality necessarily began to exist. I show that the arguments which have been offered thus far for the view that the past is necessarily finite do not succeed. Moreover, as I elaborate on in chapter 5, having a finite past does not suffice for having a beginning. -/- As I discuss in chapter 3, the second way in which friends of the KCA have sought to defend their view that physical reality began to exist involves a family of a posteriori arguments meant to show that we have empirical evidence that physical reality has a finite past history. For example, the big bang is sometimes claimed to have been the beginning of physical reality and, since we have excellent empirical evidence for the big bang, we have excellent empirical evidence for the beginning of physical reality. The big bang can be understood in two ways. On the one hand, the big bang can be understood as a theory about the history and development of the observable universe. Understood in that sense, then I agree that the big bang is supported by excellent empirical evidence and by a scientific consensus. On the other hand, some authors (particularly science popularizers, science journalists, and religious apologists) have wrongly interpreted big bang theory as a theory about the beginning of the whole of physical reality. As I argue, while a beginning of physical reality may be consistent with classical big bang theory, classical big bang theory does not provide good reason for thinking that physical reality began to exist. -/- In part II, I turn to discussing three necessary, but not necessarily sufficient, conditions for physical reality to have a beginning. Before discussing the three conditions, in chapter 4, I introduce three metaphysical accounts of the nature of time (A-theory, B-theory, and C-theory) as well as some formal machinery that will subsequently become useful in the dissertation. I introduce the first of the three conditions in chapter 5. According to the Modal Condition, physical reality began to exist only if, at the closest possible worlds without time, physical reality does not exist. I show that this condition helps us to make sense of various views in both theology and philosophy of physics. In chapter 6}, I introduce the second of my three conditions, the Direction Condition, according to which, roughly, physical reality began to exist only if all space-time points agree about the direction of time, so that all space-time points can agree that physical reality's putative beginning took place in their objective past. In chapter 7, I discuss the third condition, the Boundary Condition, according to which physical reality began to exist only if there is a past temporal boundary such that physical reality did not exist before the boundary. I show that there are two senses in which physical reality could be said to have had a past temporal boundary. Lastly, in chapter 8, I show that there is a relationship between my three conditions and classical big bang theory, even though the relationship is not the one usually identified in the literature. -/- In part III, I present four arguments for the view that, at the present stage of philosophical and scientific inquiry, we cannot know whether physical reality satisfies the three necessary conditions to have had a beginning and, consequently, we cannot know whether physical reality had a beginning. As I will prove in chapter 9, no set of observations that we currently have, when conjoined with General Relativity, entails that physical reality satisfies the Direction or Boundary Conditions. As I show in chapter 10, considerations in the philosophical foundations of statistical mechanics entail either that the Cosmos violates the Modal Condition or else that there is a transcendental condition on the possibility of our knowledge of the past that prevents our access to data we would need to gather to determine whether physical reality satisfies the Boundary Condition. In chapter 11, I show that there are a number of live cosmological models according to which physical reality does not satisfy the Boundary Condition. As long as we don't know whether any of those cosmological models are correct, we do not know whether physical reality satisfies the Boundary Condition. Lastly, I turn to confirmation theory and show that, at our present stage of inquiry, ampliative inferences for the conclusion that physical reality satisfies the Modal, Direction, and Boundary Conditions are not successful. (shrink)

The Aleph Zero or Zero Dichotomy is a strong version of Zeno's Dichotomy II which being entirely derived from the topological successiveness of the w-order comes to the same Zeno's absurdity.

Bifurcated supertasks entail the actual infinite division of time (accelerated system of reference) as well as the existence of half-curves of infinite length (supertask system of reference). This paper analyzes both issues from a critique perspective. It also analyzes a conflictive case of hypercomputation performed by means of a bifurcated supertask. The results of these analyzes suggest the convenience of reviewing certain foundational aspects of infinitist theories.

I analyze here Benacerraf's criticism of Thomson arguments on the impossibility of w-supertasks. Although Benacerraf's criticism is well founded, his analysis of Thomson's lamp is incomplete. In fact, it is possible to consider a new line of argument, which Benacerraf only incidentally considered, based on the functioning laws of the lamp. This argument leads to a contradictory result that compromises the formal consistency of the w-ordering involved in all w-supertasks.