The Church-Turing thesis (CTT) underlies tantalizing open questions concerning the fundamental place of computing in the physical universe. For example, is every physical system computable? Is the universe essentially computational in nature? What are the implications for computer science of recent speculation about physical uncomputability? Does CTT place a fundamental logical limit on what can be computed, a computational "barrier" that cannot be broken, no matter how far and in what multitude of ways computers develop? Or could new types of hardware, based perhaps on quantum or relativistic phenomena, lead to radically new computing paradigms that do breach the Church-Turing barrier, in which the uncomputable becomes computable, in an upgraded sense of "computable"? Before addressing these questions, we first look back to the 1930s to consider how Alonzo Church and Alan Turing formulated, and sought to justify, their versions of CTT. With this necessary history under our belts, we then turn to today's dramatically more powerful versions of CTT.
The semantic view of computation is the claim that semantic properties play an essential role in the individuation of physical computing systems such as laptops and brains. The main argument for the semantic view (“the master argument”) rests on the fact that some physical systems simultaneously implement different automata at the same time, in the same space, and even in the very same physical properties ("simultaneous implementation"). Recently, several authors have challenged this argument (Piccinini 2008, 2015; Coelho Mollo 2018; Dewhurst 2018). They accept the premise of simultaneous implementation but reject the semantic conclusion. In this paper, I aim to explicate the semantic view and to address these objections. I first characterize the semantic view and distinguish it from other, closely related views. Then, I contend that the master argument for the semantic view survives the counter-arguments against it. One counter-argument is that computational individuation is not forced to choose between the implemented automata but rather always picks out a more basic computational structure. My response is that this move might undermine the notion of computational equivalence. Another counter-argument is that while computational individuation is forced to rely on extrinsic features, these features need not be semantic. My reply is that the semantic view better accounts for these extrinsic features than the proposed non-semantic alternatives.
An underlying assumption in computational approaches in cognitive and brain sciences is that the nervous system is an input–output model of the world: Its input–output functions mirror certain relations in the target domains. I argue that the input–output modelling assumption plays distinct methodological and explanatory roles. Methodologically, input–output modelling serves to discover the computed function from environmental cues. Explanatorily, input–output modelling serves to account for the appropriateness of the computed function to the explanandum information-processing task. I compare very briefly the modelling explanation to mechanistic and optimality explanations, noting that in both cases the explanations can be seen as complementary rather than contrastive or competing.
Computer pioneer Konrad Zuse (1910-1995) built the world's first working programcontrolled general-purpose digital computer in Berlin in 1941. After the Second World War he supplied Europe with cheap relay-based computers, and later transistorized computers. Mathematical logician Robin Gandy (1919-1995) proved a number of major results in recursion theory and set theory. He was Alan Turing's only PhD student. Mathematician Roger Penrose (1931- ) is famous for his work with Stephen Hawking. What we call Zuse's thesis, Gandy's thesis, and Penrose's thesis are three fundamental theses concerning computation and physics. Zuse hypothesized that the physical universe is a computer. Gandy offered a profound analysis supporting the thesis that every discrete deterministic physical assembly is computable (assuming that there is an upper bound on the speed of propagation of effects and signals, and a lower bound on the dimensions of an assembly's components). Penrose argued that the physical universe is in part uncomputable. We explore these three theses. Zuse's thesis we believe to be false: the universe might have consisted of nothing but a giant computer, but in fact does not. Gandy viewed his claim as a relatively apriori one, provable on the basis of a set-theoretic argument that makes only very general physical assumptions about decomposability into parts and the nature of causation. We maintain that Gandy's argument does not work, and that Gandy's thesis is best viewed, like Penrose's, as an open empirical hypothesis.
A key component of scientific inquiry, especially inquiry devoted to developing mechanistic explanations, is delineating the phenomenon to be explained. The task of delineating phenomena, however, has not been sufficiently analyzed, even by the new mechanistic philosophers of science. We contend that Marr’s characterization of what he called the computational level (CL) provides a valuable resource for understanding what is involved in delineating phenomena. Unfortunately, the distinctive feature of Marr’s computational level, his dual emphasis on both what is computed and why it is computed, has not been appreciated in philosophical discussions of Marr. Accordingly we offer a distinctive account of CL. This then allows us to develop two important points about delineating phenomena. First, the accounts of phenomena that figure in explanatory practice are typically not qualitative but precise, formal or mathematical, representations. Second, delineating phenomena requires consideration of the demands the environment places on the mechanism—identifying, as Marr put it, the basis of the computed function in the world. As valuable as Marr’s account of CL is in characterizing phenomena, we contend that ultimately he did not go far enough. Determining the relevant demands of the environment on the mechanism often requires detailed empirical investigation. Moreover, often phenomena are reconstituted in the course of inquiry on the mechanism itself.
Jack Copeland, Mark Sprevak, and Oron Shagrir. 2017. “Is the Universe Computational?.” In The Turing Guide, edited by Jonathan Bowen, Jack Copeland, Mark Sprevak, and Robin Wilson, Pp. 445-462. Oxford University Press. Abstract
The theory that the whole universe is a computer is a bold and striking one. It is a theory of everything: the entire universe is to be understood, fundamentally, in terms of the universal computing machine that Alan Turing introduced in 1936. We distinguish between two versions of this grand-scale theory and explain what the universe would have to be like for one or both versions to be true. Spoiler: the question is in fact wide open – at the present stage of science, nobody knows whether it's true or false that the whole universe is a computer. But the issues are as fascinating as they are important, so it's certainly worthwhile discussing them.
This chapter deals with those fields that study computing systems. Among these computational sciences are computer science, computational cognitive science, computational neuroscience, and artificial intelligence. In the first part of the chapter, it is shown that there are varieties of computation, such as human computation, algorithmic machine computation, and physical computation. There are even varieties of versions of the Church-Turing thesis. The conclusion is that different computational sciences are often about different kinds of computation. The second part of the chapter discusses three specific philosophical issues. One is whether computers are natural kinds. Another issue is the nature of computational theories and explanations. The last section of the chapter relates remarkable results in computational complexity theory to problems of verification and confirmation.
Are all three of Marr's levels needed? Should they be kept distinct? We argue for the distinct contributions and methodologies of each level of analysis. It is important to maintain them because they provide three different perspectives required to understand mechanisms, especially information-processing mechanisms. The computational perspective provides an understanding of how a mechanism functions in broader environments that determines the computations it needs to perform (and may fail to perform). The representation and algorithmic perspective offers an understanding of how information about the environment is encoded within the mechanism and what are the patterns of organization that enable the parts of the mechanism to produce the phenomenon. The implementation perspective yields an understanding of the neural details of the mechanism and how they constrain function and algorithms. Once we adequately characterize the distinct role of each level of analysis, it is fairly straightforward to see how they relate.
Most computational neuroscientists assume that nervous systems computeand process information. We discuss foundational issues such as what we mean by ‘computation’ and ‘information processing’ in nervous systems; whether computation and information processing are matters of objective fact or of conventional, observer-dependent description; and how computational descriptions and explanations are related to other levels of analysis and organization.
Over the last three decades a vast literature has been dedicated to supervenience. Much of it has focused on the analysis of different concepts of supervenience and their philosophical consequences. This paper has two objectives. One is to provide a short, up-do-date, guide to the formal relations between the different concepts of supervenience. The other is to reassess the extent to which these concepts can establish metaphysical theses, especially about dependence. The conclusion is that strong global supervenience is the most advantageous notion of supervenience that we have.
In "A Computational Foundation for the Study of Cognition" David Chalmers articulates, justifies and defends the computational sufficiency thesis (CST). Chalmers advances a revised theory of computational implementation, and argues that implementing the right sort of computational structure is sufficient for the possession of a mind, and for the possession of a wide variety of mental properties. I argue that Chalmers`s theory of implementation is consistent with the nomological possibility of physical systems that possess different entire minds. I further argue that this brain-possessing-two-minds result challenges CST in three ways. It implicates CST with a host of epistemological problems; it undermines the underlying assumption that the mental supervenes on the physical; and it calls into question the claim that CST provides conceptual foundations for the computational science of the mind.