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

The emperor's new mind (hereafter Emperor) is an attempt to put forward a scientific alternative to the viewpoint of according to which mental activity is merely the acting out of some algorithmic procedure. John Searle and other thinkers have likewise argued that mere calculation does not, of itself, evoke conscious mental attributes, such as understanding or intentionality, but they are still prepared to accept the action the brain, like that of any other physical object, could in principle be simulated by (...) a computer. In Emperor I go further than this and suggest that the outward manifestations ofconscious mental activity cannot even be properly simulated by calculation. To support this view, I use various arguments to show that the results of mathematical insight, in particular, do not seem to be obtained algorithmically. The main thrust ofthis work, however, is to present an overview ofthe present state of physical understanding and to show that an important gap exists at the point where, quantum and classical physics meet, as well as to speculate on how the conscious brain might be taking advantage ofwhatever new physics is needed to fill this gap to achieve its nonalgorithmic effects. (shrink)

The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other kind of effective (...) procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1). (shrink)

This book is a sustained defense of the compatibility of the presence of idealizations in the sciences and scientific realism. So, the book is essentially a detailed response to the infamous arguments raised by Nancy Cartwright to the effect that idealization and scientific realism are incompatible.

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)

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)

Following Nancy Cartwright and others, I suggest that most (if not all) theories incorporate, or depend on, one or more idealizing assumptions. I then argue that such theories ought to be regimented as counterfactuals, the antecedents of which are simplifying assumptions. If this account of the logic form of theories is granted, then a serious problem arises for Bayesians concerning the prior probabilities of theories that have counterfactual form. If no such probabilities can be assigned, the the posterior probabilities will (...) be undefined, as the latter are defined in terms of the former. I argue here that the most plausible attempts to address the problem of probabilities of conditionals fail to help Bayesians, and, hence, that Bayesians are faced with a new problem. In so far as these proposed solutions fail, I argue that Bayesians must give up Bayesianism or accept the counterintuitive view that no theories that incorporate any idealizations have ever really been confirmed to any extent whatsoever. Moreover, as it appears that the latter horn of this dilemma is highly implausible, we are left with the conclusion that Bayesianism should be rejected, at least as it stands. (shrink)

Continuity as appears to us immediately by intuition differs from its current formalization, the arithmetical continuum or equivalently the set of real numbers used in modern mathematical analysis. Motivated by the known mathematical and physical problems arising from this formalization of the continuum, our aim in this paper is twofold. Firstly, by interpreting Chaitin’s variant of Gödel’s first incompleteness theorem as an inherent uncertainty or fuzziness of the arithmetical continuum, a formal set-theoretic entropy is assigned to the arithmetical continuum. Secondly, (...) by analyzing Noether’s theorem on symmetries and conserved quantities, we argue that whenever the four dimensional space-time continuum containing a single, stationary, asymptotically flat black hole is modeled by the arithmetical continuum in the mathematical formulation of general relativity, the hidden set-theoretic entropy of this latter structure reveals itself as the entropy of the black hole, indicating that this apparently physical quantity might have a pure set-theoretic origin, too. (shrink)

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.

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.

It is commonly believed that there is no equivalent of the Church–Turing thesis for computation over the reals. In particular, computational models on this domain do not exhibit the convergence of formalisms that supports this thesis in the case of integer computation. In the light of recent philosophical developments on the different meanings of the Church–Turing thesis, and recent technical results on analog computation, I will show that this current belief confounds two distinct issues, namely the extension of the notion (...) of effective computation to the reals on the one hand, and the simulation of analog computers by Turing machines on the other hand. I will argue that it is possible in both cases to defend an equivalent of the Church–Turing thesis over the reals. Along the way, we will learn some methodological caveats on the comparison of different computational models, and how to make it meaningful. (shrink)

La filosofía de la ciencia se desarrolló durante la primera mitad del siglo xx bajo el supuesto de que la ciencia podía caracterizarse por la estructura lógica tanto del conocimiento articulado en las teorías más exitosas como de sus explicaciones. En la segunda mitad del siglo xx se cuestiona fuertemente esa idea, pero se sigue asumiendo que la filosofía de la ciencia debe hacerse siguiendo los cánones de una epistemología fundamentalista que considera que el avance de la ciencia pasa por (...) una ontología cada vez mas austera guiada por la idea de "mientras menos mejor". Desde esta perspectiva fundamentalista, el que las diferentes ciencias hablen de diferentes tipos de cosas es un obstáculo al entendimiento, producto de la imperfección del conocimiento actual. Este ideal nos invita a pensar que la epistemología debe hacerse reflexionando sobre el conocimiento articulado en nuestras teorías más austeras y nos compromete con propuestas reduccionistas problemáticas que no permiten explicar la diversidad de recursos epistémicos que de hecho utilizan los científicos. En este libro promovemos una epistemología que no sigue el lema de "mientras menos mejor", sino el de "organizar nuestros recursos epistémicos de manera que se genere entendimiento". Así, la misma estructura de las explicaciones y las prácticas (que incluye métodos y normas respecto de lo que se considera plausible y valioso) es lo que nos da la pauta para responder a la pregunta de qué es lo que hay. Esta estrategia epistémica nos obliga a hacer una filosofía de la ciencia muy cercana a la ciencia, reconociendo la pluralidad de sus métodos, objetivos y prácticas, sin reducir la filosofía de la ciencia a la sociología o a cualquier otra ciencia en particular. (shrink)

The purpose of this paper is to provide an account of the epistemology and metaphysics of universe creation on a computer. The paper begins with F.J.Tipler's argument that our experience is indistinguishable from the experience of someone embedded in a perfect computer simulation of our own universe, hence we cannot know whether or not we are part of such a computer program ourselves. Tipler's argument is treated as a special case of epistemological scepticism, in a similar vein to `brain-in-a-vat' arguments. (...) It is argued that the hypothesis that our universe is a program running on a digital computer in another universe generates empirical predictions, and is therefore a falsifiable hypothesis. The computer program hypothesis is also treated as a hypothesis about what exists beyond the physical world, and is compared with Kant's metaphysics of noumena. It is proposed that a theory about what exists beyond the physical world should be formulated with the precise concepts of mathematics, and should generate physical predictions. It is argued that if our universe is a program running on a digital computer, then our universe must have compact spatial topology, and the possibilities of observationally testing this prediction are considered. The possibility of testing the computer program hypothesis with the value of the density parameter Omega_0 is also analysed. The informational requirements for a computer to represent a universeexactly and completely are considered. Consequent doubt is thrown upon Tipler's claim that if a hierarchy of computer universes exists, we would not be able to know which `level of implementation' our universe exists at. It is then argued that a digital computer simulation of a universe cannot exist as a universe. However, the paper concludes with the acknowledgement that an analog computer simulation can be objectively related to the thing it represents, hence an analog computer simulation of a universe could, in principle, exist as a universe. (shrink)

Motivated by the known mathematical and physical problems arising from the current mathematical formalization of the physical spatio-temporal continuum, as a substantial technical clarification of our earlier attempt (Etesi in Found Sci 25:327–340, 2020), the aim in this paper is twofold. Firstly, by interpreting Chaitin’s variant of Gödel’s first incompleteness theorem as an inherent uncertainty or fuzziness present in the set of real numbers, a set-theoretic entropy is assigned to it using the Kullback–Leibler relative entropy of a pair of Riemannian (...) manifolds. Then exploiting the non-negativity of this relative entropy an abstract Hawking-like area theorem is derived. Secondly, by analyzing Noether’s theorem on symmetries and conserved quantities, we argue that whenever the four dimensional space-time continuum containing a single, stationary, asymptotically flat black hole is modeled by the set of real numbers in the mathematical formulation of general relativity, the hidden set-theoretic entropy of this latter structure reveals itself as the entropy of the black hole (proportional to the area of its “instantaneous” event horizon), indicating that this apparently physical quantity might have a pure set-theoretic origin, too. (shrink)

Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing a test of a known physical (...) theory T. Our earlier work was based upon experiments in Newtonian mechanics. Here we extend the scope of the theory of experimental oracles beyond Newtonian mechanics to electrical theory. First, we specify an experiment that measures resistance using a Wheatstone bridge and start to classify the computational power of this experimental oracle using non-uniform complexity classes. Secondly, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on our ability to measure resistance by the Wheatstone bridge. The connection between the algorithm and physical test is mediated by a protocol controlling each query, especially the physical time taken by the experimenter. In our studies we find that physical experiments have an exponential time protocol, this we formulate as a general conjecture. Our theory proposes that measurability in Physics is subject to laws which are co-lateral effects of the limits of computability and computational complexity. (shrink)

We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of measurement processes. We examine eight different experiments that make measurements and, by introducing the idea of an observable indicator, we identify three distinct forms (...) of measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis. (shrink)

Sumário Mostramos que, em virtude dos limites teóricos da computação, nem toda a ciência formulada com carácter preditivo pode ser simulada. Em particular, evidencia- se que a Fisica Clássica, nomeadamente a Físíca Newtoniana, padece deste mal, encerrando processos de Zenão.

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that all physical systems (...) can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

The purpose of this paper is to elucidate, by means of concepts and theorems drawn from mathematical logic, the conditions under which the existence of a multiverse is a logical necessity in mathematical physics, and the implications of Gödel’s incompleteness theorem for theories of everything.Three conclusions are obtained in the final section: (i) the theory of the structure of our universe might be an undecidable theory, and this constitutes a potential epistemological limit for mathematical physics, but because such a theory (...) must be complete, there is no ontological barrier to the existence of a final theory of everything; (ii) in terms of mathematical logic, there are two different types of multiverse: classes of non-isomorphic but elementarily equivalent models, and classes of model which are both non-isomorphic and elementarily inequivalent; (iii) for a hypothetical theory of everything to have only one possible model, and to thereby negate the possible existence of a multiverse, that theory must be such that it admits only a finite model. (shrink)