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.

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)

Stereotypically, computation involves intrinsic changes to the medium of representation: writing new symbols, erasing old symbols, turning gears, flipping switches, sliding abacus beads. Perspectival computation leaves the original inscriptions untouched. The problem solver obtains the output by merely alters his orientation toward the input. There is no rewriting or copying of the input inscriptions; the output inscriptions are numerically identical to the input inscriptions. This suggests a loophole through some of the computational limits apparently imposed by physics. There can be (...) symbol manipulation without inscription manipulation because symbols are complex objects that have manipulatable elements besides their inscriptions. Since a written symbol is an ordered pair of consisting of a shape and the reader's orientation to that inscription, the symbol can be changed by changing the orientation rather than inscription. Although there are the usual physical limits associated with reading the answer, the computation is itself instantaneous. This is true even when the sub-calculations are algorithmically complex, exponentially increasing or even infinite. (shrink)

Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as “the work-horse of hypercomputation” (Potgieter and Rosinger 2010: 853). But do they really compute beyond the “Turing limit”—e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that in the current literature the term (...) “accelerating Turing machine” is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical. (shrink)

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)