Gualtiero Piccinini articulates and defends a mechanistic account of concrete, or physical, computation. A physical system is a computing system just in case it is a mechanism one of whose functions is to manipulate vehicles based solely on differences between different portions of the vehicles according to a rule defined over the vehicles. Physical Computation discusses previous accounts of computation and argues that the mechanistic account is better. Many kinds of computation are explicated, (...) such as digital vs. analog, serial vs. parallel, neural network computation, program-controlled computation, and more. Piccinini argues that computation does not entail representation or information processing although information processing entails computation. Pancomputationalism, according to which every physical system is computational, is rejected. A modest version of the physical Church-Turing thesis, according to which any function that is physically computable is computable by Turing machines, is defended. (shrink)

Physical Computation is the summation of Piccinini’s work on computation and mechanistic explanation over the past decade. It draws together material from papers published during that time, but also provides additional clarifications and restructuring that make this the definitive presentation of his mechanistic account of physical computation. This review will first give a brief summary of the account that Piccinini defends, followed by a chapter-by-chapter overview of the book, before finally discussing one aspect of the (...) account in more critical detail. (shrink)

The aim of this paper is to offer a formal criterion for physical computation that allows us to objectively distinguish between competing computational interpretations of a physical system. The criterion construes a computational interpretation as an ordered pair of functions mapping (1) states of a physical system to states of an abstract machine, and (2) inputs to this machine to interventions in this physical system. This interpretation must ensure that counterfactuals true of the abstract machine (...) have appropriate counterparts which are true of the physical system. The criterion proposes that rival interpretations be assessed on the basis of simplicity. Simplicity is construed as the Kolmogorov complexity of the interpretation. This approach is closely related to the notion of algorithmic information distance and draws on earlier work on real patterns. (shrink)

According to Frank Jacksonʼs knowledge argument, Mary, who lives in a black-and-white world, has all the physical knowledge about the world, yet she has new information when she sees a red apple. If we accept this, then physicalism – according to which the description of the world can be realised entirely with the help of physical theories – is false. However, even if Jacksonʼs argument about new information is true, we do not have to discard physicalism. Even exclusively (...) physical computer systems are not capable of predicting their own sensory information if they are built using a specific structure and complexity. It can be shown that a specific type of computational system can lead to the creation of decision-related unpredictability of a specific type of sensory information. This investigation takes a charitable position towards the concept of qualia to provide it with a physicalist and computationalist explanation. (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)

The purpose of this paper is to argue against the claim that morphological computation is substantially different from other kinds of physical computation. I show that some (but not all) purported cases of morphological computation do not count as specifically computational, and that those that do are solely physical computational systems. These latter cases are not, however, specific enough: all computational systems, not only morphological ones, may (and sometimes should) be studied in various ways, including (...) their energy efficiency, cost, reliability, and durability. Second, I critically analyze the notion of “offloading” computation to the morphology of an agent or robot, by showing that, literally, computation is sometimes not offloaded but simply avoided. Third, I point out that while the morphology of any agent is indicative of the environment that it is adapted to, or informative about that environment, it does not follow that every agent has access to its morphology as the model of its environment. (shrink)

What does it mean to say that an object or system computes? What is it about laptops, smartphones, and nervous systems that they are considered to compute, and why does it seldom occur to us to describe stomachs, hurricanes, rocks, or chairs that way? Though computing systems are everywhere today, it is very difficult to answer these questions. The book aims to shed light on the subject by arguing for the semantic view of computation, which states that computingsystems are (...) always accompanied by representations. This view is presented as an alternative to non-semantic views such as the mechanistic account of computation. (shrink)

This is review of the book "Physical Computation and Cognitive Science" by Nir Fresco: http://www.springer.com/la/book/9783642413742.

The phenomenon of consciousness has always been a central question for philosophers and scientists. Emerging in the past decade are new approaches to the understanding of consciousness in a scientific light. This book presents a series of essays by leading thinkers giving an account of the current ideas prevalent in the scientific study of consciousness. The value of the book lies in the discussion of this interesting though complex subject from different points of view ranging from physics, computer science to (...) the cognitive sciences. Reviews of controversial ideas related to the philosophy of mind from western and eastern sources including classical Indian first person methodologies provide a breadth of coverage that has seldom been attempted in a book before. Additionally, chapters relating to the new approaches in computational modelling of higher order cognitive function and consciousness are included. The book is of great value for established as well as young researchers from a wide cross-section of interdisciplinary scientific backgrounds, aiming to pursue research in this field, as well as an informed public. * Presents the latest developments in the scientific study of consciousness * Critically reviews different theoretical and philosophical explanations related to the subject * An important book for both students and researchers in designing research projects on consciousness. (shrink)

Structuralism about mathematical objects and structuralist accounts of physical computation both face indeterminacy objections. For the former, the problem arises for cases such as the complex roots i and \, for which a automorphism can be defined, thus establishing the structural identity of these importantly distinct mathematical objects. In the case of the latter, the problem arises for logical duals such as AND and OR, which have invertible structural profiles :369–400, 2001). This makes their physical implementations indeterminate, (...) in the sense that their structural profiles alone cannot establish whether a given physical component is an AND-gate or an OR-gate. Doherty has recently shown both problems to be analogous, and has argued that computational structuralism is threatened with the absurd conclusion that computational digits might be indiscernible, such that, if structural properties are all that we have to go on, the binary digit 0 must be treated as identical to the binary digit 1. However, we think that a solution to the indiscernibility problem for mathematical structuralists, drawing on the work of David Hilbert, can be adapted for the analogous problem in the computational case, thereby rescuing the structuralist approach to physical computation. (shrink)

Basic Digital Education is already planned to be integrated with the forthcoming curriculum for Austrian primary schools as it was already implemented for lower secondary schools in 2018. BDE includes the most essential and novel developments of Computational Thinking, which are fundamentally responsible for nurturing students' problem-solving skills. Thus, evaluating teaching materials, scaffolding guidelines, and assessments is becoming increasingly important for the successful implementation of CT in Austrian classrooms. This study is a part of a longitudinal multi-cycle educational design research (...) project aiming to explore how to foster CT and to raise the awareness, importance, and confidence of teachers and students in applying CT for everyday uses. Our paper focuses on a sub-study in which teaching units for grade 3 and 4 students were designed by combining an Open Educational Resource textbook and Physical Computing with the micro:bit device. The designed learning environment consists of three units and was implemented in two classes over 3 weeks. The two classes were further split into two groups each, to ensure better support during implementation. The class teachers received upfront teacher training and conducted pre- and post-test assessments with the students. The resulting data was then analyzed to gain insights into the effects on CT skills of the young learners. Results showed that combining block-based programming and physical computing devices could become a promising approach to promote computational thinking skills in lower school grades. Furthermore, the observed direction of the designed units supports low-barrier access to increase the desired uses of CT in classrooms. (shrink)

Much has been written as of late on the status of the physical Church- Turing thesis and the relation between physics and computer science in general. The following discussion will focus on one such article [5]. The purpose of these notes is not so much to argue for a particular thesis as it is to solicit a dialog that will help clarify our own thoughts.

In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis, according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently so. On all (...) accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify. In this paper I articulate this question and consider several tentative answers to it. (shrink)

For over 50 years, since the development of nuclear-armed ICBMs, the USA has sought a way to defend against them. These efforts evolved through various strategies and technologies: from nuclear-tipped rockets through space-based laser weapons to today’s system of ground-based kinetic-kill interceptors. Public debate around these issues reached a peak in the 1980s with President Reagan’s Strategic Defense Initiative, popularly known as Star Wars.Rebecca Slayton examines this history in Arguments that Count, a valuable and well-told account of a particular aspect (...) of missile defense: computer software. Missile defense required identifying a hostile missile launch, keeping track of thousands of incoming warheads on their ballistic trajectories, and directing interceptors to the right place—and doing all this in less than 30 minutes. From the outset, designers turned to computers to do the complex calculations quickly enough. But missile defense presented an additional factor, in that any m .. (shrink)

This note discusses the account of physical computation offered in Part II of Primiero’s On the Foundations of Computing. Although there is much to find attractive about the account, I argue that the account is obscure at certain crucial junctures and that it does not supply a wholly satisfactory account of miscomputation. I close by considering whether the engineering foundation of computing requires a theory of physical computation in the first place, suggesting tentatively that it does (...) not. (shrink)

The relationship between abstract formal procedures and the activities of actual physical systems has proved to be surprisingly subtle and controversial, and there are a number of competing accounts of when a physical system can be properly said to implement a mathematical formalism and hence perform a computation. I defend an account wherein computational descriptions of physical systems are high-level normative interpretations motivated by our pragmatic concerns. Furthermore, the criteria of utility and success vary according to (...) our diverse purposes and pragmatic goals. Hence there is no independent or uniform fact to the matter, and I advance the ‘anti-realist’ conclusion that computational descriptions of physical systems are not founded upon deep ontological distinctions, but rather upon interest-relative human conventions. Hence physical computation is a ‘conventional’ rather than a ‘natural’ kind. (shrink)

The so-called integration problem concerning mechanistic and computational explanation asks how they are related to each other. One approach is that a computational explanation is a species of mechanistic explanation. According to this view, computational or mathematical descriptions are mechanism sketches or macroscopic descriptions that include computationally relevant and exclude computationally irrelevant physical properties. Some suggest that this results in a so-called single hierarchy view of physical computation, where computational or mathematical properties sit together in the same (...) mechanistic hierarchy with the implementational properties. This view can be contrasted with a separate hierarchy view, according to which computational and physical descriptions have their own hierarchies which are related to each other via a bridging implementation relation. The single hierarchy view has been criticized for downplaying the explanatory value of computational explanations and not being hospitable to multiple realization of cognitive processes. In this paper, I argue that the aforementioned criticisms fail, and there might be a deeper problem with the single hierarchy view, which is that the single hierarchy view might collapse into a separate hierarchy view. The kind of abstraction used by the single hierarchy view does not seem to grant mathematical or computational descriptions but only more stripped physical or implementational descriptions. (shrink)

Descriptive abstraction means omission of information from descriptions of phenomena. In this paper, I introduce a distinction between vertical and horizontal descriptive abstraction. Vertical abstracts away levels of mechanism or organization, while horizontal abstracts away details within one level of organization. The distinction is implicit in parts of the literature, but it has received insufficient attention and gone mainly unnoticed. I suggest that the distinction can be used to clarify how computational descriptions are formed in some variants of the mechanistic (...) account of physical computation. Furthermore, I suggest that, if this suggestion is adopted, it can be used to resolve what I call abstraction, hierarchy, and generality problems raised against mechanistic account of physical computation. According to the abstraction problem, the mechanistic account of physical computation is conceptually confused in claiming that physical systems process computational, abstract properties. An existing solution distinguishes between descriptive and metaphysical abstraction, suggesting that the abstraction problem unnecessarily postulates metaphysically abstract entities. The solution has been criticized for leading to what I call hierarchy and generality problems: it results in two separate hierarchies, one physical and one computational, making it problematic both to account for the generality of computational descriptions and to specify how the two hierarchies are related to each other. Adopting the vertical-horizontal distinction and the view that computational descriptions are achieved by horizontal abstraction allows one to account for the generality of computational descriptions, and to form a single hierarchy in which there are no separate hierarchies in need of integration. (shrink)

In this paper, I present an overview of personal and intimate technologies within a pedagogical context. I describe two courses that I have developed for Computation Arts at Concordia University: “Tangible Media and Physical Computing” and “Second Skin and Soft Wear.” Each course deals with different aspects of physical computing and tangible media in a Fine Arts context. In both courses, I introduce concepts of soft computation and intimate reactive artifacts as artworks. I emphasize the concept (...) of memory (contrasting computer memory and personal, interpretive memory), and explore how responsive or interactive objects can create a new medium for annotating architectural space and objects, for leaving traces of presence, and for recording personal histories. At the core of this pedagogical practice is a strong emphasis on engaging a vulnerable, personal approach to working with electronics and physical computation. To contextualize the teaching practice, I begin by presenting some of my own research projects developed at Extra Soft Labs (also known as XS Labs), then segue into a detailed discussion of these two classes, and conclude with a discussion of some student work. (shrink)

This Element has three main aims. First, it aims to help the reader understand the concept of computation that Turing developed, his corresponding results, and what those results indicate about the limits of computational possibility. Second, it aims to bring the reader up to speed on analyses of computation in physical systems which provide the most general characterizations of what it takes for a physical system to be a computational system. Third, it aims to introduce the (...) reader to some different kinds of quantum computers, describe quantum speedup, and present some explanation sketches of quantum speedup. If successful, this Element will equip the reader with a basic knowledge necessary for pursuing these topics in more detail. (shrink)

Andrew Boucher (1997) argues that ``parallel computation is fundamentally different from sequential computation'' (p. 543), and that this fact provides reason to be skeptical about whether AI can produce a genuinely intelligent machine. But parallelism, as I prove herein, is irrelevant. What Boucher has inadvertently glimpsed is one small part of a mathematical tapestry portraying the simple but undeniable fact that physical computation can be fundamentally different from ordinary, ``textbook'' computation (whether parallel or sequential). This (...) tapestry does indeed immediately imply that human cognition may be uncomputable. (shrink)

Goswami proposes to replace the current scientific paradigm of physical realism with that of a quantum-based monistic idealism and, in the process, accomplish the following goals: establish a basis for explaining consciousness, reintegrate spirituality, mysticism, morality, a sense that the universe is meaningful, etc., with scientific discoveries and the scientific enterprise, and support the assumption that humans possess free will - i.e., that they are not controlled by the apparently inexorable causality of the physical laws that govern the (...) functioning of their brains. Here, we critically examine this approach, from an artificial intelligence and neural network perspective, and point out what appear to be some inherent weaknesses in Goswami's arguments. (shrink)

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)

Although computation and the science of physical systems would appear to be unrelated, there are a number of ways in which computational and physical concepts can be brought together in ways that illuminate both. This volume examines fundamental questions which connect scholars from both disciplines: is the universe a computer? Can a universal computing machine simulate every physical process? What is the source of the computational power of quantum computers? Are computational approaches to solving physical (...) problems and paradoxes always fruitful? Contributors from multiple perspectives reflecting the diversity of thought regarding these interconnections address many of the most important developments and debates within this exciting area of research. Both a reference to the state of the art and a valuable and accessible entry to interdisciplinary work, the volume will interest researchers and students working in physics, computer science, and philosophy of science and mathematics. (shrink)

Computer simulation is shown to be philosophically interesting because it introduces a qualitatively new methodology for theory construction in science different from the conventional two components of "theory" and "experiment and/or observation". This component is "experimentation with theoretical models." Two examples from the physical sciences are presented for the purpose of demonstration but it is claimed that the biological and social sciences permit similar theoretical model experiments. Furthermore, computer simulation permits theoretical models for the evolution of physical systems (...) which use cellular automata rather than differential equations as their syntax. The great advantages of the former are indicated. (shrink)

The problem of multiple-computations discovered by Hilary Putnam presents a deep difficulty for functionalism (of all sorts, computational and causal). We describe in out- line why Putnam’s result, and likewise the more restricted result we call the Multiple- Computations Theorem, are in fact theorems of statistical mechanics. We show why the mere interaction of a computing system with its environment cannot single out a computation as the preferred one amongst the many computations implemented by the system. We explain why (...) nonreductive approaches to solving the multiple- computations problem, and in particular why computational externalism, are dualistic in the sense that they imply that nonphysical facts in the environment of a computing system single out the computation. We discuss certain attempts to dissolve Putnam’s unrestricted result by appealing to systems with certain kinds of input and output states as a special case of computational externalism, and show why this approach is not workable without collapsing to behaviorism. We conclude with some remarks about the nonphysical nature of mainstream approaches to both statistical mechanics and the quantum theory of measurement with respect to the singling out of partitions and observables. (shrink)

This paper makes a novel linkage between the multiple-computations theorem in philosophy of mind and Landauer’s principle in physics. The multiple-computations theorem implies that certain physical systems implement simultaneously more than one computation. Landauer’s principle implies that the physical implementation of “logically irreversible” functions is accompanied by minimal entropy increase. We show that the multiple-computations theorem is incompatible with, or at least challenges, the universal validity of Landauer’s principle. To this end we provide accounts of both ideas (...) in terms of low-level fundamental concepts in statistical mechanics, thus providing a deeper understanding of these ideas than their standard formulations given in the high-level terms of thermodynamics and cognitive science. Since Landauer’s principle is pivotal in the attempts to derive the universal validity of the second law of thermodynamics in statistical mechanics, our result entails that the multiple-computations theorem has crucial implications with respect to the second law. Finally, our analysis contributes to the understanding of notions, such as “logical irreversibility,” “entropy increase,” “implementing a computation,” in terms of fundamental physics, and to resolving open questions in the literature of both fields, such as: what could it possibly mean that a certain physical process implements a certain computation. (shrink)

In this paper, we pursue three general aims: (I) We will define a notion of fundamental opacity and ask whether it can be found in High Energy Physics (HEP), given the involvement of machine learning (ML) and computer simulations (CS) therein. (II) We identify two kinds of non-fundamental, contingent opacity associated with CS and ML in HEP respectively, and ask whether, and if so how, they may be overcome. (III) We address the question of whether any kind of opacity, contingent (...) or fundamental, is unique to ML or CS, or whether they stand in continuity to kinds of opacity associated with other scientific research. (shrink)

Quantum physics is a linear theory, so it is somewhat puzzling that it can underlie very complex systems such as digital computers and life. This paper investigates how this is possible. Physically, such complex systems are necessarily modular hierarchical structures, with a number of key features. Firstly, they cannot be described by a single wave function: only local wave functions can exist, rather than a single wave function for a living cell, a cat, or a brain. Secondly, the quantum to (...) classical transition is characterised by contextual wave-function collapse shaped by macroscopic elements that can be described classically. Thirdly, downward causation occurs in the physical hierarchy in two key ways: by the downward influence of time dependent constraints, and by creation, modification, or deletion of lower level elements. Fourthly, there are also logical modular hierarchical structures supported by the physical ones, such as algorithms and computer programs, They are able to support arbitrary logical operations, which can influence physical outcomes as in computer aided design and 3-d printing. Finally, complex systems are necessarily open systems, with heat baths playing a key role in their dynamics and providing local arrows of time that agree with the cosmological direction of time that is established by the evolution of the universe. (shrink)

In this philosophical paper, we explore computational and biological analogies to address the fine-tuning problem in cosmology. We first clarify what it means for physical constants or initial conditions to be fine-tuned. We review important distinctions such as the dimensionless and dimensional physical constants, and the classification of constants proposed by Lévy-Leblond. Then we explore how two great analogies, computational and biological, can give new insights into our problem. This paper includes a preliminary study to examine the two (...) analogies. Importantly, analogies are both useful and fundamental cognitive tools, but can also be misused or misinterpreted. The idea that our universe might be modelled as a computational entity is analysed, and we discuss the distinction between physical laws and initial conditions using algorithmic information theory. Smolin introduced the theory of "cosmological natural selection" with a biological analogy in mind. We examine an extension of. (shrink)

This paper presents several observations on the connections between information, physics, and computation. In particular, the computing power of quantum computers is examined. Quantum theory is characterized by superimposed states and nonlocal interactions. It is argued that recently studied quantum computers, which are based on local interactions, cannot simulate quantum physics.

Digital computers are by design completely deterministic, yet they are often consumers of randomness in cryptography, simulations, science experiments and computer games. To generate randomness in software, programmers implement special mathematical algorithms, which produce a series of numbers that appear nondeterministic, so called pseudo random number generators (PRNGs). Computer games make heavy use of such PRNGs to make game simulations and behaviors of game elements appear more natural. An important design element of many video games is game physics, the simulation (...) of physical reality in video games. Generally overlooked by game developers, is the fact that randomness based on PRNGs are mere simulations themselves and randomness is not treated as a physical property of reality, and thus a form of game physics. Since the dynamics of the very small and the very complex invariably contains randomness, the author suggests this can be used to extend to the scope of game physics by defining two new game physics elements: 1. providing physics based random data to games or interactive media and 2. extracting true randomness from game-player interactions themselves. (shrink)

This dissertation is an investigation into the degree to which the mathematics used in physical theories can be constructivized. The techniques of recursive function theory and classical logic are used to separate out the algorithmic content of mathematical theories rather than attempting to reformulate them in terms of "intuitionistic" logic. The guiding question is: are there experimentally testable predictions in physics which are not computable from the data? ;The nature of Church's thesis, that the class of effectively calculable functions (...) on the natural numbers is identical to the class of general recursive functions, is discussed. It is argued that this thesis is an example of an explication of the very notion of an effectively calculable function. This is contrary to a view of the thesis as a hypothesis about the limitations of the human mind. ;The extension to functions of a real variable of the notion of effective calculability is discussed, and it is argued that a function of a real variable must be continuous in order to be considered effectively calculable . The relation between continuity and computability is significant for the problem at hand. The results of a well-designed experiment do not depend critically upon the precise values of the relevant parameters. Accordingly, if the solution to a problem in mathematical physics depends discontinuously upon the data, it cannot be regarded as an experimentally testable prediction of the theory. The principle that the testable predictions of a physical theory cannot be singular is known as the principle of regularity. This principle is significant, because discontinuities generate non-computability, but they also disqualify a prediction from being experimentally testable. ;A mathematical framework is set up for discussing computability in physical theories. This framework is then applied to the case of quantum mechanics. It is found that, due to the use of unbounded operators in the theory, noncomputable objects appear, but predictions which satisfy the principle of regularity are nevertheless computable functions of the data. (shrink)

Realism about computation is the view that whether or not a particular physical system is performing a particular computation is at least sometimes a mindindependent feature of reality. The caveat ’at least sometimes’ is necessary here because a realist about computation need not believe that all instances of computation should be realistically construed. The computational theory of mind presupposes realism about computation. If whether or not the human nervous system implements particular computations is not (...) a natural fact about the world that is independent of whether we represent it as doing so, then the computational theory of mind fails to naturalise the mind. Realism about computation is also presupposed by attempts to use computational principles such as Landauer’s Principle to dispel Maxwell’s Demon. Realism about computation has been challenged by Hilary Putnam and John Searle among others. Various arguments have been put forward purporting to show that any physical system of sufficient complexity trivially implements all computations. Ladyman et al. offer a precisification and general proof Landauer’s Principle. In order to do this they present an analysis of what it is for a physical process to implement a logical transformation. In this paper, their analysis is explained and its implications for realism about computation and the use of Landauer’s Principle in foundational debates is assessed. (shrink)

Vesely (experimental physics, U. of Vienna, Austria) provides the basic numerical and computational techniques, followed by an explanation of specific problems of computational physics. Appendices address properties of computing machines and an outline of the technique of Fast Fourier Transformation. The first edition, published by Plenum Press, Ne.

α-recursion lifts classical recursion theory from the first transfinite ordinal ω to an arbitrary admissible ordinal α [10]. Idealized computational models for α-recursion analogous to Turing machine models for classical recursion have been proposed and studied [4] and [5] and are applicable in computational approaches to the foundations of logic and mathematics [8]. They also provide a natural setting for modeling extensions of the algorithmic logic described in [1] and [2]. On such models, an α-Turing machine can complete a θ-step (...) computation for any ordinal θ < α. Here we consider constraints on the physical realization of α-Turing machines that arise from the structure of physical spacetime. In particular, we show that an α-Turing machine is realizable in a spacetime constructed from R only if α is countable. While there are spacetimes where uncountable computations are possible and while they may even be empirically distinguishable from a standard spacetime, there is good reason to suppose that such nonstandard spacetimes are nonphysical. We conclude with a suggestion for a revision of Church’s thesis appropriate as an upper bound for physical computation. (shrink)

The aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit, for the reader's consideration, a tentative resolution to it. In particular, I argue, in this dissertation, that the physical explanation for quantum speedup is precisely the fact that the phenomenon of quantum entanglement enables a quantum computer to fully exploit the representational capacity of Hilbert space. This is impossible for classical systems, joint states of which must always be representable as (...) product states. I begin the dissertation by considering, in Chapter 2, the most popular of the candidate physical explanations for quantum speedup: the many worlds explanation of quantum computation. I argue that, although it is inspired by the neo-Everettian interpretation of quantum mechanics, unlike the latter it does not have the conceptual resources required to overcome objections such as the so-called `preferred basis objection'. I further argue that the many worlds explanation, at best, can serve as a good description of the physical process which takes place in so-called network-based computation, but that it is incompatible with other models of computation such as cluster state quantum computing. I next consider, in Chapter 3, a common component of most other candidate explanations of quantum speedup: quantum entanglement. I investigate whether entanglement can be said to be a necessary component of any explanation for quantum speedup, and I consider two major purported counter-examples to this claim. I argue that neither of these, in fact, show that entanglement is unnecessary for speedup, and that, on the contrary, we should conclude that it is. In Chapters 4 and 5 I then ask whether entanglement can be said to be sufficient as well. In Chapter 4 I argue that despite a result that seems to indicate the contrary, entanglement, considered as a resource, can be seen as sufficient to enable quantum speedup. Finally, in Chapter 5 I argue that entanglement is sufficient to explain quantum speedup as well. (shrink)

I articulate and defend a new theory of what it is for a physical system to implement an abstract computational model. According to my descriptivist theory, a physical system implements a computational model just in case the model accurately describes the system. Specifically, the system must reliably transit between computational states in accord with mechanical instructions encoded by the model. I contrast my theory with an influential approach to computational implementation espoused by Chalmers, Putnam, and others. I deploy (...) my theory to illuminate the relation between computation and representation. I also rebut arguments, propounded by Putnam and Searle, that computational implementation is trivial. (shrink)