Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis.

§1. Mathematics and the physical world. Genuine scientific knowledge cannot be certain, nor can it be justified a priori. Instead, it must be conjectured, and then tested by experiment, and this requires it to be expressed in a language appropriate for making precise, empirically testable predictions. That language is mathematics.This in turn constitutes a statement about what the physical world must be like if science, thus conceived, is to be possible. As Galileo put it, “the universe is written in the (...) language of mathematics”. Galileo's introduction of mathematically formulated, testable theories into physics marked the transition from the Aristotelian conception of physics, resting on supposedly necessary a priori principles, to its modern status as a theoretical, conjectural and empirical science. Instead of seeking an infallible universal mathematical design, Galilean science usesmathematics to express quantitative descriptions of an objective physical reality. Thus mathematics became the language in which we express our knowledge of the physical world — a language that is not only extraordinarily powerful and precise, but also effective in practice. Eugene Wigner referred to “the unreasonable effectiveness of mathematics in the physical sciences”. But is this effectiveness really unreasonable or miraculous?Numbers, sets, groups and algebras have an autonomous reality quite independent of what the laws of physics decree, and the properties of these mathematical structures can be just as objective as Plato believed they were. (shrink)

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

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (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.

What psychological and philosophical significance should we attach to recent efforts at computer simulations of human cognitive capacities? In answering this question, I find it useful to distinguish what I will call "strong" AI from "weak" or "cautious" AI. According to weak AI, the principal value of the computer in the study of the mind is that it gives us a very powerful tool. For example, it enables us to formulate and test hypotheses in a more rigorous and precise fashion. (...) But according to strong AI, the computer is not merely a tool in the study of the mind; rather, the appropriately programmed computer really is a mind, in the sense that computers given the right programs can be literally said to. (shrink)

Searle has recently used two adaptations of his Chinese room argument in an attack on connectionism. I show that these new forms of the argument are fallacious. First I give an exposition of and rebuttal to the original Chinese room argument, and then a brief introduction to the essentials of connectionism.

Let psychologism be the doctrine that whether behavior is intelligent behavior depends on the character of the internal information processing that produces it. More specifically, I mean psychologism to involve the doctrine that two systems could have actual and potential behavior _typical_ of familiar intelligent beings, that the two systems could be exactly alike in their actual and potential behavior, and in their behavioral dispositions and capacities and counterfactual behavioral properties (i.e., what behaviors, behavioral dispositions, and behavioral capacities they would (...) have exhibited had their stimuli differed)--the two systems could be alike in all these ways, yet there could be a difference in the information processing that mediates their stimuli and responses that determines that one is not at all intelligent while the other is fully intelligent. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

I argue in this article that there is a mistake in Searle's Chinese room argument that has not received sufficient attention. The mistake stems from Searle's use of the Church-Turing thesis. Searle assumes that the Church-Turing thesis licences the assumption that the Chinese room can run any program. I argue that it does not, and that this assumption is false. A number of possible objections are considered and rejected. My conclusion is that it is consistent with Searle's argument to hold (...) onto the claim that understanding consists in the running of a program. (shrink)

There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument (...) for CTT by analyzing the processes carried out by a human computer. I then contend that if the Gandy–Sieg account is correct, then the notion of effective computability has changed after 1936. Today computer scientists view effective computability in terms of finite machine computation. My contention is supported by the current formulations of CTT, which always refer to machine computation, and by the current argumentation for CTT, which is different from the main arguments advanced by Turing and Church. I finally turn to discuss Robin Gandy's characterization of machine computation. I suggest that there is an ambiguity regarding the types of machines Gandy was postulating. I offer three interpretations, which differ in their scope and limitations, and conclude that none provides the basis for claiming that Gandy characterized finite machine computation. (shrink)

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.

Wilfried Sieg. Calculations by Man and Machine: Conceptual Analysis.

Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.

Currently, there is widespread skepticism that higher cognitive processes, given their apparent flexibility and globality, could be carried out by specialized computational devices, or modules. This skepticism is largely due to Fodor’s influential definition of modularity. From the rather flexible catalogue of possible modular features that Fodor originally proposed has emerged a widely held notion of modules as rigid, informationally encapsulated devices that accept highly local inputs and whose opera- tions are insensitive to context. It is a mistake, however, to (...) equate such features with computational devices in general and therefore to assume, as Fodor does, that higher cognitive processes must be non-computational. Of the many possible non-Fodorean architectures, one is explored here that offers possible solutions to computational problems faced by conventional modular systems: an ‘enzymatic’ architecture. Enzymes are computational devices that use lock-and-key template matching to iden- tify relevant information (substrates), which is then operated upon and returned to a common pool for possible processing by other devices. Highly specialized enzymes can operate together in a common pool of information that is not pre-sorted by information type. Moreover, enzymes can use molecular ‘tags’ to regulate the operations of other devices and to change how particular substrates are construed and operated upon, allowing for highly interactive, context-specific processing. This model shows how specialized, modular processing can occur in an open system, and suggests that skepti- cism about modularity may largely be due to failure to consider alternatives to the standard model. (shrink)

The paper criticizes standard functionalist arguments for multiple realization. It focuses on arguments in which psychological states are conceived as computational, which is precisely where the multiple realization doctrine has seemed the strongest. It is argued that a type-type identity thesis between computational states and physical states is no less plausible than a multiple realization thesis. The paper also presents, more tentatively, positive arguments for a picture of local reduction.