The aim of this paper is to propose an alternative behavioural definition of computation (and of a computer) based simply on whether a system is capable of reacting to the environment—the input—as reflected in a measure of programmability. This definition is intended to have relevance beyond the realm of digital computers, particularly vis-à-vis natural systems. This will be done by using an extension of a phase transition coefficient previously defined in an attempt to characterise the dynamical behaviour of cellular automata (...) and other systems. The transition coefficient measures the sensitivity of a system to external stimuli and will be used to define the susceptibility of a system to be (efficiently) programmed. (shrink)

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)

In this paper we discuss a particular example of the passage from the informal, but rigorous description of a concept to the axiomatic formulation of principles holding for the concept; in particular, we look at the principles of continuity and lawlike choice in the theory of lawless sequences. Our discussion also leads to a better understanding of the rôle of the so-called density axiom for lawless sequences.

We critically discuss Cleland''s analysis of effective procedures as mundane effective procedures. She argues that Turing machines cannot carry out mundane procedures, since Turing machines are abstract entities and therefore cannot generate the causal processes that are generated by mundane procedures. We argue that if Turing machines cannot enter the physical world, then it is hard to see how Cleland''s mundane procedures can enter the world of numbers. Hence her arguments against versions of the Church-Turing thesis for number theoretic functions (...) miss the mark. (shrink)

This paper deals with the question: what are the key requirements for a physical system to perform digital computation? Time and again cognitive scientists are quick to employ the notion of computation simpliciter when asserting basically that cognitive activities are computational. They employ this notion as if there was or is a consensus on just what it takes for a physical system to perform computation, and in particular digital computation. Some cognitive scientists in referring to digital computation simply adhere to (...) Turing’s notion of computability . Classical computability theory studies what functions on the natural numbers are computable and what mathematical problems are undecidable. Whilst a mathematical formalism of computability may perform a methodological function of evaluating computational theories of certain cognitive capacities, concrete computation in physical systems seems to be required for explaining cognition as an embodied phenomenon . There are many non-equivalent accounts of digital computation in physical systems. I examine only a handful of those in this paper: (1) Turing’s account ; (2) The triviality “account”; (3) Reconstructing Smith’s account of participatory computation ; (4) The Algorithm Execution account . My goal in this paper is twofold. First, it is to identify and clarify some of the underlying key requirements mandated by these accounts. I argue that these differing requirements justify a demand that one commits to a particular account when employing the notion of computation in regard to physical systems. Second, it is to argue that despite the informative role that mathematical formalisms of computability may play in cognitive science, they do not specify the relationship between abstract and concrete computation. (shrink)

I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space of computational complexity theory hence militate against the autonomous character of some of the concepts and categories of computer science.

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like (...) manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)

Which notion of computation (if any) is essential for explaining cognition? Five answers to this question are discussed in the paper. (1) The classicist answer: symbolic (digital) computation is required for explaining cognition; (2) The broad digital computationalist answer: digital computation broadly construed is required for explaining cognition; (3) The connectionist answer: sub-symbolic computation is required for explaining cognition; (4) The computational neuroscientist answer: neural computation (that, strictly, is neither digital nor analogue) is required for explaining cognition; (5) The extreme (...) dynamicist answer: computation is not required for explaining cognition. The first four answers are only accurate to a first approximation. But the “devil” is in the details. The last answer cashes in on the parenthetical “if any” in the question above. The classicist argues that cognition is symbolic computation. But digital computationalism need not be equated with classicism. Indeed, computationalism can, in principle, range from digital (and analogue) computationalism through (the weaker thesis of) generic computationalism to (the even weaker thesis of) digital (or analogue) pancomputationalism. Connectionism, which has traditionally been criticised by classicists for being non-computational, can be plausibly construed as being either analogue or digital computationalism (depending on the type of connectionist networks used). Computational neuroscience invokes the notion of neural computation that may (possibly) be interpreted as a sui generis type of computation. The extreme dynamicist argues that the time has come for a post-computational cognitive science. This paper is an attempt to shed some light on this debate by examining various conceptions and misconceptions of (particularly digital) computation. (shrink)