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)

The description of data and computer programs with the use of numbers is epistemologically valuable, because it allows to identify the limits of different types of computations. This applies in particular to discrete computations, which can be described by means of computable numbers in the Turing sense. The mathematical fact that there are real numbers of a different type, i.e. uncomputable numbers, determines the minimal limitations of digital techniques; on the other hand, however, it points to the possibility of the (...) theoretical development and physical implementation of computationally stronger techniques, such as analogue-continuous computation. The analyses presented in this article lead to the conclusion that physical implementations of unconventional computations require the occurrence of actually infinite quantities in nature. Although some arguments of theoretical physics support the physical existence of such quantities, they are not definitive. (shrink)

Opis danych i programów komputerowych za pomocą liczb jest epistemologicznie użyteczny, ponieważ pozwala określać granice różnego typu obliczeń. Dotyczy to w szczególności obliczeń dyskretnych, opisywalnych za pomocą liczb obliczalnych w sensie Turinga. Matematyczny fakt istnienia liczb rzeczywistych innego typu, tj. nieobliczalnych, wyznacza minimalne ograniczenia technik cyfrowych; z drugiej strony jednak, wskazuje na możliwość teoretycznego opracowania i fizycznej implementacji technik obliczeniowo silniejszych, takich jak obliczenia analogowe-ciągłe. Przedstawione w artykule analizy prowadzą do wniosku, że fizyczne implementacje obliczeń niekonwencjonalnych wymagają występowania w przyrodzie (...) wielkości nieskończonych aktualnie. Za fizycznym istnieniem takich wielkości przemawiają wprawdzie pewne argumenty fizyki teoretycznej, nie są one jednak ostateczne. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

In most accounts of realization of computational processes by physical mechanisms, it is presupposed that there is one-to-one correspondence between the causally active states of the physical process and the states of the computation. Yet such proposals either stipulate that only one model of computation is implemented, or they do not reflect upon the variety of models that could be implemented physically. In this paper, I claim that mechanistic accounts of computation should allow for a broad variation of models of (...) computation. In particular, some non-standard models should not be excluded a priori. The relationship between mathematical models of computation and mechanistically adequate models is studied in more detail. (shrink)

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.

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 no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.

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.

Certain enterprises at the fringes of science, such as intelligent design creationism, claim to identify phenomena that go beyond not just our present physics but any possible physical explanation. Asking what it would take for such a claim to succeed, we introduce a version of physicalism that formulates the proposition that all available data sets are best explained by combinations of “chance and necessity”—algorithmic rules and randomness. Physicalism would then be violated by the existence of oracles that produce certain kinds (...) of noncomputable functions. Examining how a candidate for such an oracle would be evaluated leads to questions that do not admit an easy resolution. Since we lack any plausible candidate for any such oracle, however, chance-and-necessity physicalism appears very likely to be correct. (shrink)

A version of the Church-Turing 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, non-well-founded, 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 (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

The ‘Turing barrier’ is an evocative image for 0′, the degree of the unsolvability of the halting problem for Turing machines—equivalently, of the undecidability of Peano Arithmetic. The ‘barrier’ metaphor conveys the idea that effective computability is impaired by restrictions that could be removed by infinite methods. Assuming that the undecidability of PA is essentially depending on the finite nature of its computational means, decidability would be restored by the ω-rule. Hypercomputation, the hypothetical realization of infinitary machines through relativistic and (...) quantium models, would thus be capable of breaking the Turing barrier. The speculation is unfounded in principle, apart from issues of physical realizability: The point is that the ω-rule does not cope with all objects entailing the undecidability of PA. As long as the system is consistent, the computational boundary can be established by paradox-like constructions, such as Gödel-Rosser’s and Yablo’s, which are refractory to infinite induction, and do stand as the barrier’s buttresses. (shrink)

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.

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)

In this paper I will argue that Tait’s axiomatic conception of mathematics implies that it is in principle impossible to be justified in believing a mathematical statement without being justified in believing that statement to be provable. I will then show that there are possible courses of experience which would justify acceptance of a mathematical statement without justifying belief that this statement is provable.

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 recent debate on hypercomputation has raised new questions both on the computational abilities of quantum systems and the Church-Turing Thesis role in Physics.We propose here the idea of “effective physical process” as the essentially physical notion of computation. By using the Bohm and Hiley active information concept we analyze the differences between the standard form (quantum gates) and the non-standard one (adiabatic and morphogenetic) of Quantum Computing, and we point out how its Super-Turing potentialities derive from an incomputable information (...) source in accordance with Bell’s constraints. On condition that we give up the formal concept of “universality”, the possibility to realize quantum oracles is reachable. In this way computation is led back to the logic of physical world. (shrink)

Motivation and perspective for an exciting new research direction interconnecting logic, spacetime theory, relativity--including such revolutionary areas as black hole physics, relativistic computers, new cosmology--are presented in this paper. We would like to invite the logician reader to take part in this grand enterprise of the new century. Besides general perspective and motivation, we present initial results in this direction.