The familiar theories of physics have the feature that the application of the theory to make predictions in specific circumstances can be done by means of an algorithm. We propose a more precise formulation of this feature—one based on the issue of whether or not the physically measurable numbers predicted by the theory are computable in the mathematical sense. Applying this formulation to one approach to a quantum theory of gravity, there are found indications that there may exist no such (...) algorithms in this case. Finally, we discuss the issue of whether the existence of an algorithm to implement a theory should be adopted as a criterion for acceptable physical theories.“Can it then be that there is... something of use for unraveling the universe to be learned from the philosophy of computer design?” —J. A. Wheeler(1). (shrink)

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

We investigate the provability or nonprovability of certain ordinary mathematical theorems within certain weak subsystems of second order arithmetic. Specifically, we consider the Cauchy/Peano existence theorem for solutions of ordinary differential equations, in the context of the formal system RCA 0 whose principal axioms are ▵ 0 1 comprehension and Σ 0 1 induction. Our main result is that, over RCA 0 , the Cauchy/Peano Theorem is provably equivalent to weak Konig's lemma, i.e. the statement that every infinite {0, 1}-tree (...) has a path. We also show that, over RCA 0 , the Ascoli lemma is provably equivalent to arithmetical comprehension, as is Osgood's theorem on the existence of maximum solutions. At the end of the paper we digress to relate our results to degrees of unsolvability and to computable analysis. (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.

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

Dummett's case against platonism rests on arguments concerning the acquisition and manifestation of knowledge of meaning. Dummett's arguments are here criticized from a viewpoint less Davidsonian than Chomskian. Dummett's case against formalism is obscure because in its prescriptive considerations are not clearly separated from descriptive. Dummett's implicit value judgments are here made explicit and questioned. ?Combat Revisionism!? Chairman Mao.

When Ken Malone investigates a case of something causing mental static across the United States, he is teleported to a world that doesn't exist.

In his PhD thesis (1938) Turing introduced what he described as 'a new kind of machine'. He called these 'O-machines'. The present paper employs Turing's concept against a number of currently fashionable positions in the philosophy of mind.

We argue that (1) a purported example of an infinite inference we humans can actually perform admits a faithful, finitary description, and (2) infinite inference contravenes any view which does not grant our minds uncomputable powers. These arguments block the strategy, dating back to Carnap's Logical Syntax of Language, of using infinitary inference rules to secure the determinacy of arithmetical truth on conventionalist grounds.

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 central claim of computationalism is generally taken to be that the brain is a computer, and that any computer implementing the appropriate program would ipso facto have a mind. In this paper I argue for the following propositions: (1) The central claim of computationalism is not about computers, a concept too imprecise for a scientific claim of this sort, but is about physical calculi (instantiated discrete formal systems). (2) In matters of formality, interpretability, and so forth, analog computation and (...) digital computation are not essentially different, and so arguments such as Searle''s hold or not as well for one as for the other. (3) Whether or not a biological system (such as the brain) is computational is a scientific matter of fact. (4) A substantive scientific question for cognitive science is whether cognition is better modeled by discrete representations or by continuous representations. (5) Cognitive science and AI need a theoretical construct that is the continuous analog of a calculus. The discussion of these propositions will illuminate several terminology traps, in which it''s all too easy to become ensnared. (shrink)

Does what guides a pastry chef stand on par, from the standpoint of contemporary computer science, with what guides a supercomputer? Did Betty Crocker, when telling us how to bake a cake, provide an effective procedure, in the sense of `effective' used in computer science? According to Cleland, the answer in both cases is ``Yes''. One consequence of Cleland's affirmative answer is supposed to be that hypercomputation is, to use her phrase, ``theoretically viable''. Unfortunately, though we applaud Cleland's ``gadfly philosophizing'' (...) (as, in fact, seminal), we believe that unless such a modus operandi is married to formal philosophy, nothing conclusive will be produced (as evidenced by the problems plaguing Cleland's work that we uncover). Herein, we attempt to pull off not the complete marriage for hypercomputation, but perhaps at least the beginning of a courtship that others can subsequently help along. (shrink)

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)

Index sets are used to measure the complexity of properties associated with the differentiability of real functions and the existence of solutions to certain classic differential equations. The new notion of a locally computable real function is introduced and provides several examples of Σ04 complete sets.

The corpus of physical theory is a paradigm of knowledge. The evolution of modern physical theory constitutes the clearest exemplar of the growth of knowledge. If the development of physical theory does not constitute an example of progress and growth in what we know about the Universe nothing does. So anyone interested in the theory of knowledge must be interested consequently in the evolution and content of physical theory. Crucial to the conception of physics as a paradigm of knowledge is (...) the way in which physical theory provides explanations of a vast diversity of natural phenomena on the basis of a very few fundamental principles. A central problem for the epistemologist is therefore what is theoretical explanation in physics? Here we can get good insight from what Redhead has said. Indeed one could agree with almost everything Redhead says and simply endorse much of his careful and extensive defence of the covering law account of explanation in the physical sciences at least as an ideal. However I shall, I fear, try the reader's patience by extending some of the considerations he introduced and raising those issues where we disagree, especially in the important area of statistical explanation. (shrink)

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with (...) the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

Ko, K., On the computational complexity of integral equations, Annals of Pure and Applied Logic 58 201–228. The computational complexity of Volterra integral equations of the second kind and of the first kind is investigated. It is proved that if the kernel functions satisfy the Lipschitz condition, then the solutions of Volterra equations of the second kind are polynomial-space computable. If, one the other hand, the kernel functions only satisfy the local Lipschitz condition with the Lipschitz constants growing in an (...) exponential rate, then the solutions could be exponential-time hard. We identify a class of Volterra equations of the first kind that can be converted to Volterra equations of the second kind satisfying the local Lipschitz condition. The complexity of the solutions of these equations is also proved to be exponential-time hard. (shrink)

In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x1, … , xn which are related to y by a known relation y = f. Measurements are never 100% accurate; hence, the measured values equation image are different from xi, and the resulting estimate equation image is different from the desired value y = f. How different can it (...) be? Traditional engineering approach to error estimation in data processing assumes that we know the probabilities of different measurement errors equation image. In many practical situations, we only know the upper bound Δi for this error; hence, after the measurement, the only information that we have about xi is that it belongs to the interval equation image. In this case, it is important to find the range y of all possible values of y = f when xi ∈ xi. We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems: Most of the related problems turn out to be, in general, at least NP-hard. In this paper, we show how the use of quantum computing can speed up some computations related to interval and probabilistic uncertainty. We end the paper with speculations on whether “hypothetic” physical devices can compute NP-hard problems faster than in exponential time. Most of the paper's results were first presented at NAFIPS'2003 [30]. (shrink)

We study computability of the abstract linear Cauchy problem equation image)where A is a linear operator, possibly unbounded, on a Banach space X. We give necessary and sufficient conditions for A such that the solution operator K: x ↦ u of the problem is computable. For studying computability we use the representation approach to computable analysis developed by Weihrauch and others. This approach is consistent with the model used by Pour-El/Richards.

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more (...) mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable. (shrink)