Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

In the paper some applications of Gödel's incompleteness theorems to discussions of problems of computer science are presented. In particular the problem of relations between the mind and machine (arguments by J.J.C. Smart and J.R. Lucas) is discussed. Next Gödel's opinion on this issue is studied. Finally some interpretations of Gödel's incompleteness theorems from the point of view of the information theory are presented.

The alleged proof of the non-mechanical, or non-computational, character of the human mind based on Gödel’s incompleteness theorem is revisited. Its history is reviewed. The proof, also known as the Lucas argument and the Penrose argument, is refuted. It is claimed, following Gödel himself and other leading logicians, that antimechanism is not implied by Gödel’s theorems alone. The present paper sets out this refutation in its strongest form, demonstrating general theorems implying the inconsistency of Lucas’s arithmetic and the semantic inadequacy (...) of Penrose’s arithmetic. On the other hand, the limitations to our capacity for mechanizing or programming the mind are also indicated, together with two other corollaries of Gödel’s theorems: that we cannot prove that we are consistent, and that we cannot fully describe our notion of a natural number. (shrink)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that all physical systems (...) can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

Gödel’s first incompleteness theorem is sometimes said to refute mechanism about the mind. §1 contains a discussion of mechanism. We look into its origins, motivations and commitments, both in general and with regard to the human mind, and ask about the place of modern computers and modern cognitive science within the general mechanistic paradigm. In §2 we give a sharp formulation of a mechanistic thesis about the mind in terms of the mathematical notion of computability. We present the argument from (...) Gödel’s theorem against mechanism in terms of this formulation and raise two objections, one of which is known but is here given a more precise formulation, and the other is new and based on the discussion in §1. (shrink)

The late 19th-century Ignorabimus controversy over the limits of scientific knowledge has often been characterized as proclaiming the end of intellectual progress, and by implication, as plunging Germany into a crisis of pessimism from which Liberalism never recovered. My research supports the opposite interpretation. The initiator of the Ignorabimus controversy, Emil du Bois-Reymond, was a physiologist who worked his whole life against the forces of obscurantism, whether they came from the Catholic and Conservative Right or the scientistic and millenarian Left. (...) Du Bois-Reymond’s doubt that scientists would ever elucidate consciousness must therefore be seen as an endorsement, and not a rejection, of his faith in reason. (shrink)

Philosophical questions about minds and computation need to focus squarely on the mathematical theory of Turing machines (TM's). Surrogate TM's such as computers or formal systems lack abilities that make Turing machines promising candidates for possessors of minds. Computers are only universal Turing machines (UTM's)—a conspicuous but unrepresentative subclass of TM. Formal systems are only static TM's, which do not receive inputs from external sources. The theory of TM computation clearly exposes the failings of two prominent critiques, Searle's Chinese room (...) (1980) and arguments from Gödel's Incompleteness theorems (e.g., Lucas, 1961; Penrose, 1989), both of which fall short of addressing the complete TM model. Both UTM-computers and formal systems provide an unsound basis for debate. In particular, their special natures easily foster the misconception that computation entails intrinsically meaningless symbol manipulation. This common view is incorrect with respect to full-fledged TM's, which can process inputs non-formally, i.e., in a subjective and dynamically evolving fashion. To avoid a distorted understanding of the theory of computation, philosophical judgments and discussions should be grounded firmly upon the complete Turing machine model, the proper model for real computers. (shrink)