The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other kind of effective (...) procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1). (shrink)

This book is a defense of modal realism; the thesis that our world is but one of a plurality of worlds, and that the individuals that inhabit our world are only a few out of all the inhabitants of all the worlds. Lewis argues that the philosophical utility of modal realism is a good reason for believing that it is true.

The mathematical theory of communication.

The views of David Lewis and the Meinongians are both often met with an incredulous stare. This is not by accident. The stunned disbelief that usually accompanies the stare is a natural first reaction to a large ontology. Indeed, Lewis has been explicitly linked with Meinong, a charge that he has taken great pains to deny. However, the issue is not a simple one. "Meinongianism" is a complex set of distinctions and doctrines about existence and predication, in addition to the (...) famously large ontology. While there are clearly non-Meinongian features of Lewis' views, it is our thesis that many of the characteristic elements of Meinongian metaphysics appear in Lewis' theory. Moreover, though Lewis rejects incomplete and inconsistent Meinongian objects, his ontology may exceed that of a Meinongian who doesn't accept his possibilia. Thus, Lewis explains the truth of "there might have been talking donkeys" by appealing to possibilia which are talking donkeys. But the Meinongian need not accept that there exist things which are talking donkeys. Indeed, we show that a Meinongian even need not accept that there are nonexistent things which are talking donkeys! (shrink)

One of the greatest revolutions in mathematics occurred when Georg Cantor promulgated his theory of transfinite sets. This revolution is the subject of Joseph Dauben's important studythe most thorough yet writtenof the philosopher and mathematician who was once called a "corrupter of youth" for an innovation that is now a vital component of elementary school curricula.Set theory has been widely adopted in mathematics and philosophy, but the controversy surrounding it at the turn of the century remains of great interest. Cantor's (...) own faith in his theory was partly theological. His religious beliefs led him to expect paradoxes in any concept of the infinite, and he always retained his belief in the utter veracity of transfinite set theory. Later in his life, he was troubled by recurring attacks of severe depression. Dauben shows that these played an integral part in his understanding and defense of set theory. (shrink)

Understanding inductive reasoning is a problem that has engaged mankind for thousands of years. This problem is relevant to a wide range of fields and is integral to the philosophy of science. It has been tackled by many great minds ranging from philosophers to scientists to mathematicians, and more recently computer scientists. In this article we argue the case for Solomonoff Induction, a formal inductive framework which combines algorithmic information theory with the Bayesian framework. Although it achieves excellent theoretical results (...) and is based on solid philosophical foundations, the requisite technical knowledge necessary for understanding this framework has caused it to remain largely unknown and unappreciated in the wider scientific community. The main contribution of this article is to convey Solomonoff induction and its related concepts in a generally accessible form with the aim of bridging this current technical gap. In the process we examine the major historical contributions that have led to the formulation of Solomonoff Induction as well as criticisms of Solomonoff and induction in general. In particular we examine how Solomonoff induction addresses many issues that have plagued other inductive systems, such as the black ravens paradox and the confirmation problem, and compare this approach with other recent approaches. (shrink)

The background of these remarks is that in 1967, in ‘’Constructive reasoning” [27], I sketched an argument that finitist arithmetic coincides with primitive recursive arithmetic, P RA; and in 1981, in “Finitism” [28], I expanded on the argument. But some recent discussions and some of the more recent literature on the subject lead me to think that a few further remarks would be useful.