Throughout what is now the more than 50-year history of the computer many theories have been advanced regarding the contribution this machine would make to changes both in the structure of society and in ways of thinking. Like other theories regarding the future, these should also be taken with a pinch of salt. The history of the development of computer technology contains many predictions which have failed to come true and many applications that have not been foreseen. While we must (...) reserve judgment as to the question of the impact on the structure of society and human thought, there is no reason to wait for history when it comes to the question: what are the properties that could give the computer such far-reaching importance? The present book is intended as an answer to this question. The fact that this is a theoretical analysis is due to the nature of the subject. No other possibilities are available because such a description of the properties of the computer must be valid for any kind of application. An additional demand is that the description should be capable of providing an account of the properties which permit and limit these possible applications, just as it must make it possible to characterize a computer as distinct from a) other machines whether clocks, steam engines, thermostats, or mechanical and automatic calculating machines, b) other symbolic media whether printed, mechanical, or electronic and c) other symbolic languages whether ordinary languages, spoken or written or formal languages. This triple limitation, however, (with regard to other machines, symbolic media and symbolic languages) raises a theoretical question as it implies a meeting between concepts of mechanical-deterministic systems, which stem from mathematical physics, and concepts of symbolic systems which stem from the description of symbolic activities common to the humanities. The relationship between science and the humanities has traditionally been seen from a dualistic perspective, as a relationship between two clearly separate subject areas, each studied on its own set of premises and using its own methods. In the present case, however, this perspective cannot be maintained since there is both a common subject area and a new - and specific - kind of interaction between physical and symbolic processes. (shrink)

It is often said that the best system account of laws needs supplementing with a theory of perfectly natural properties. The ‘strength’ and ‘simplicity’ of a system is language-relative and without a fixed vocabulary it is impossible to compare rival systems. Recently a number of philosophers have attempted to reformulate the BSA in an effort to avoid commitment to natural properties. I assess these proposals and argue that they are problematic as they stand. Nonetheless, I agree with their aim, and (...) show that if simplicity is interpreted as ‘compression’, algorithmic information theory provides a framework for system comparison without the need for natural properties. (shrink)

Ordinal polytheism is motivated by the cosmological and design arguments. It is also motivated by Leibnizian–Lewisian modal realism. Just as there are many universes, so there are many gods. Gods are necessary concrete grounds of universes. The god-universe relation is one-to-one. Ordinal polytheism argues for a hierarchy of ranks of ever more perfect gods, one rank for every ordinal number. Since there are no maximally perfect gods, ordinal polytheism avoids many of the familiar problems of monotheism. It links theology with (...) counterpart theory, mathematics and computer science. And it entails that the system of universes has an attractive axiological structure. (shrink)

As interpreted by Pattee, von Neumann’s Theory of Self-Reproducing Automata has proved to be a useful tool for understanding some of the difficulties and paradoxes of molecular biosemiotics. But is its utility limited to molecular systems or is it more generally applicable within biosemiotics? One way of answering that question is to look at the Theory as a model for one particular high-level biosemiotic activity, human language. If the model is not useful for language, then it certainly cannot be generally (...) useful to biosemiotics. Beginning with the Universal Turing Machine and continuing with von Neumann’s Theory and Pattee’s interpretation, the properties of universality, programmability, underspecification, complementarity of description/construction, and open-ended evolutionary potential are shown to be usefully applicable to language, thus opening a new line of inquiry in biosemiotics. (shrink)

In light of the close connection between the ontological hierarchy of set theory and the ideological hierarchy of type theory, Øystein Linnebo and Agustín Rayo have recently offered an argument in favour of the view that the set-theoretic universe is open-ended. In this paper, we argue that, since the connection between the two hierarchies is indeed tight, any philosophical conclusions cut both ways. One should either hold that both the ontological hierarchy and the ideological hierarchy are open-ended, or that neither (...) is. If there is reason to accept the view that the set-theoretic universe is open-ended, that will be because such a view is the most compelling one to adopt on the purely ontological front. (shrink)

The identification of an informal concept of ‘effective calculability’ with a rigorous mathematical notion like ‘recursiveness’ or ‘Turing computability’ is still viewed as problematic, and I think rightly so. I analyze three different and conflicting perspectives Gödel articulated in the three decades from 1934 to 1964. The significant shifts in Gödel's position underline the difficulties of the methodological issues surrounding the Church-Turing Thesis.

This paper is dedicated to Alonzo Church, who died in August 1995 after a long life devoted to logic. To Church we owe lambda calculus, the thesis bearing his name and the solution to the Entscheidungsproblem.His well-known book Introduction to Mathematical LogicI, defined the subject matter of mathematical logic, the approach to be taken and the basic topics addressed. Church was the creator of the Journal of Symbolic Logicthe best-known journal of the area, which he edited for several decades This (...) paper is in three sections. The first is written in journalistic style:the story of the life of AlonzoChurch is told, including some of the many anecdotes I have collected from different sources. The secondpart is devoted to his work, but is far from being exhaustive. The last part is more original; in it I attempto show that Church’s great discovery was lambda calculus and that his remaining contributions weremainly inspired afterthoughts in the sense that most of his contributions as well as some of his pupils derivefrom that initial achievement. Included are Kleene’s Recursion Theory and the completeness proof ofHenkin. I have added an appendix in which is presented the typed lambda calculus and a proof of theundecidability of first-order logic. (shrink)

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (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)

This paper challenges two orthodox theses: (a) that computational processes must be algorithmic; and (b) that all computed functions must be Turing-computable. Section 2 advances the claim that the works in computability theory, including Turing's analysis of the effective computable functions, do not substantiate the two theses. It is then shown (Section 3) that we can describe a system that computes a number-theoretic function which is not Turing-computable. The argument against the first thesis proceeds in two stages. It is first (...) shown (Section 4) that whether a process is algorithmic depends on the way we describe the process. It is then argued (Section 5) that systems compute even if their processes are not described as algorithmic. The paper concludes with a suggestion for a semantic approach to computation. (shrink)

The main factor of intelligence is defined as the ability tocomprehend, formalising this ability with the help of new constructsbased on descriptional complexity. The result is a comprehension test,or C- test, which is exclusively defined in computational terms. Due toits absolute and non-anthropomorphic character, it is equally applicableto both humans and non-humans. Moreover, it correlates with classicalpsychometric tests, thus establishing the first firm connection betweeninformation theoretical notions and traditional IQ tests. The TuringTest is compared with the C- test and the (...) combination of the two isquestioned. In consequence, the idea of using the Turing Test as apractical test of intelligence should be surpassed, and substituted bycomputational and factorial tests of different cognitive abilities, amuch more useful approach for artificial intelligence progress and formany other intriguing questions that present themselves beyond theTuring Test. (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.

Metaphors of mind and their elaboration into models serve a crucial explanatory role in psychology. In this article, an attempt is made to describe how biology and engineering provide the predominant metaphors for contemporary psychology. A contrast between the discursive and descriptive functions of metaphor use in theory construction serves as a platform for deliberation upon the pragmatic consequences of models derived therefrom. The conclusion contains reflections upon the possibility of an integrative interdisciplinary psychology.

Against the opinion that DNA as program is not sufficiently explanatory, we maintain that the cellular machinery is entirely computational, and we identify the crucial notion of the interpreter that expresses the gene with the minimal gene set. Epigenetics research does not so much need paradigm shifts as the unraveling of an exceedingly complex computational machine.

This essay will be divided into three parts. In the first part, we discuss the case of infintesimals seen as a bridge between the discrete and the continuous. This leads in the second part to a discussion of the nature of numbers. In the last part, we follow up with some observations on the obvious applicability of mathematics.

Ioannidis [Why most published research findings are false. PLoS Med 2: e124 ] identifies six factors that contribute to explaining why most of the current published research findings are more likely to be false than true, and argues that for many current scientific fields, claimed research findings may often be simply accurate measures of the prevailing bias. In this article, we argue that three “hot” areas in current biological research, viz., agent-based modeling, evolutionary developmental biology, and systems biology, are especially (...) prone to the flaws. (shrink)

The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. Turing admits that (...) non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind. (shrink)

Machines were introduced as calculating devices to simulate operations carried out by human computers following fixed algorithms. The mathematical study of (paper) machines is the topic of our essay. The first three sections provide necessary logical background, examine the analyses of effective calculability given in the thirties, and describe results that are central to recursion theory, reinforcing the conceptual analyses. In the final section we pursue our investigation in a quite different way and focus on principles that govern the operations (...) of physically realizable machines. (shrink)

Ioannidis [Why most published research findings are false. PLoS Med 2: e124 ] identifies six factors that contribute to explaining why most of the current published research findings are more likely to be false than true, and argues that for many current scientific fields, claimed research findings may often be simply accurate measures of the prevailing bias. In this article, we argue that three “hot” areas in current biological research, viz., agent-based modeling, evolutionary developmental biology , and systems biology, are (...) especially prone to the flaws. (shrink)