The Church-Turing Thesis (CTT) is often paraphrased as ``every computable function is computable by means of a Turing machine.'' The author has constructed a family of equational theories that are not Turing-decidable, that is, given one of the theories, no Turing machine can recognize whether an arbitrary equation is in the theory or not. But the theory is called pseudorecursive because it has the additional property that when attention is limited to equations with a bounded number of variables, one obtains, (...) for each number of variables, a fragment of the theory that is indeed Turing-decidable. In a 1982 conversation, Alfred Tarski announced that he believed the theory to be decidable, despite this contradicting CTT. The article gives the background for this proclamation, considers alternate interpretations, and sets the stage for further research. (shrink)

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance theTractable Cognition thesis: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational‐level theories of cognition. To utilize this constraint, a precise and workable definition of “computational tractability” is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial‐time computability, leading to theP‐Cognition thesis. This article (...) explains how and why the P‐Cognition thesis may be overly restrictive, risking the exclusion of veridical computational‐level theories from scientific investigation. An argument is made to replace the P‐Cognition thesis by theFPT‐Cognition thesisas an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed‐parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified. (shrink)

Olszewski claims that the Church-Turing thesis can be used in an argument against platonism in philosophy of mathematics. The key step of his argument employs an example of a supposedly effectively computable but not Turing-computable function. I argue that the process he describes is not an effective computation, and that the argument relies on the illegitimate conflation of effective computability with there being a way to find out . ‘Ah, but,’ you say, ‘what’s the use of its being right twice (...) a day, if I can’t tell when the time comes?’ Why, suppose the clock points to eight o’clock, don’t you see that the clock is right at eight o’clock? Consequently, when eight o’clock comes round your clock is right. Lewis Carroll. (shrink)

I use modal logic and transfinite set-theory to define metaphysical foundations for a general theory of computation. A possible universe is a certain kind of situation; a situation is a set of facts. An algorithm is a certain kind of inductively defined property. A machine is a series of situations that instantiates an algorithm in a certain way. There are finite as well as transfinite algorithms and machines of any degree of complexity (e.g., Turing and super-Turing machines and more). There (...) are physically and metaphysically possible machines. There is an iterative hierarchy of logically possible machines in the iterative hierarchy of sets. Some algorithms are such that machines that instantiate them are minds. So there is an iterative hierarchy of finitely and transfinitely complex minds. (shrink)

Turing's (1936) analysis of effective symbolic procedures is a model of conceptual clarity that plays an essential role in the philosophy of mathematics. Yet appeal is often made to the effectiveness of human procedures in other areas of philosophy. This paper addresses the question of whether Turing's analysis can be applied to a broader class of effective human procedures. We use Sieg's (1994) presentation of Turing's Thesis to argue against Cleland's (1995) objections to Turing machines and we evaluate her proposal (...) to understand the effectiveness of procedures in terms of their reliability and precision. A number of conditions for effectiveness are identified and these are used to provide a general argument against the possibility of a Leibnizian decision procedure. (shrink)

We sketch the historical and conceptual context of Turing's analysis of algorithmic or mechanical computation. We then discuss two responses to that analysis, by Gödel and by Gandy, both of which raise, though in very different ways. The possibility of computation procedures that cannot be reduced to the basic procedures into which Turing decomposed computation. Along the way, we touch on some of Cleland's views.

Cognitive science has been dominated by the computational conception that cognition is computation across representations. To the extent to which cognition as computation across representations is supposed to be a purposive, meaningful, algorithmic, problem-solving activity, however, computers appear to be incapable of cognition. They are devices that can facilitate computations on the basis of semantic grounding relations as special kinds of signs. Even their algorithmic, problem-solving character arises from their interpretation by human users. Strictly speaking, computers as such — apart (...) from human users — are not only incapable of cognition, but even incapable of computation, properly construed. If we want to understand the nature of thought, then we have to study thinking, not computing, because they are not the same thing. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

In the technical literature of computer science, the concept of an effective procedure is closely associated with the notion of an instruction that precisely specifies an action. Turing machine instructions are held up as providing paragons of instructions that "precisely describe" or "well define" the actions they prescribe. Numerical algorithms and computer programs are judged effective just insofar as they are thought to be translatable into Turing machine programs. Nontechnical procedures (e.g., recipes, methods) are summarily dismissed as ineffective on the (...) grounds that their instructions lack the requisite precision. But despite the pivotal role played by the notion of a precisely specified instruction in classifying procedures as effective and ineffective, little attention has been paid to the manner in which instructions "precisely specify" the actions they prescribe. It is the purpose of this paper to remedy this defect. The results are startling. The reputed exemplary precision of Turing machine instructions turns out to be a myth. Indeed, the most precise specifications of action are provided not by the procedures of theoretical computer science and mathematics (algorithms) but rather by the nontechnical procedures of everyday life. I close with a discussion of some of the rumifications of these conclusions for understanding and designing concrete computers and their programming languages. (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)

Does what guides a pastry chef stand on par, from the standpoint of contemporary computer science, with what guides a supercomputer? Did Betty Crocker, when telling us how to bake a cake, provide an effective procedure, in the sense of `effective' used in computer science? According to Cleland, the answer in both cases is ``Yes''. One consequence of Cleland's affirmative answer is supposed to be that hypercomputation is, to use her phrase, ``theoretically viable''. Unfortunately, though we applaud Cleland's ``gadfly philosophizing'' (...) (as, in fact, seminal), we believe that unless such a modus operandi is married to formal philosophy, nothing conclusive will be produced (as evidenced by the problems plaguing Cleland's work that we uncover). Herein, we attempt to pull off not the complete marriage for hypercomputation, but perhaps at least the beginning of a courtship that others can subsequently help along. (shrink)

When Ken Malone investigates a case of something causing mental static across the United States, he is teleported to a world that doesn't exist.