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)

Infinite Time Register Machines are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. , and . We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in [6] and applied to ITRM 's in [3]. A real x is ITRM -recognizable iff there is an ITRM -program P such that PyPy stops with output 1 iff y=xy=x, and otherwise stops with output 0. In [3], it is (...) shown that the recognizable reals are not contained in the ITRM -computable reals. Here, we investigate in detail how the ITRM -recognizable reals are distributed along the canonical well-ordering shrink)

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

In this paper I argue that whether or not a computer can be built that passes the Turing test is a central question in the philosophy of mind. Then I show that the possibility of building such a computer depends on open questions in the philosophy of computer science: the physical Church-Turing thesis and the extended Church-Turing thesis. I use the link between the issues identified in philosophy of mind and philosophy of computer science to respond to a prominent argument (...) against the possibility of building a machine that passes the Turing test. Finally, I respond to objections against the proposed link between questions in the philosophy of mind and philosophy of computer science. (shrink)

Our limited a priori-reasoning skills open a gap between our finding a proposition conceivable and its metaphysical possibility. A prominent strategy for closing this gap is the postulation of ideal conceivers, who suffer from no such limitations. In this paper I argue that, under many, maybe all, plausible unpackings of the notion of ideal conceiver, it is false that ideal negative conceivability entails possibility.

A philosophical position may be characterized in different ways. Here we try to say how the naturalist answers certain . The questions come from very different areas; the spectrum of subjects is therefore quite mixed. There are, however, aspects of order: We start with (questions about) abstract subjects like logic, mathematics, metaphysics, then turn to problems of realism. And since in general naturalists are realists, the following questions on truth, laws of nature, origin of the universe, cosmology, evolution, body-mind-problem, freedom (...) of the will, religion, moral, and pseudoscience, are answered against a realistic background. German Eine philosophische Haltung kann man auf verschiedene Weisen charakterisieren. Hier versuchen wir zu sagen, wie der Naturalist auf bestimmte Kernfragen antwortet. Die Fragen stammen aus sehr verschiedenen Gebieten; das Themenspektrum ist deshalb recht bunt. Es gibt aber durchaus Ordnungsgesichtspunkte: Wir beginnen mit (Fragen zu) eher abstrakten Gegenständen wie Logik, Mathematik, Metaphysik, kommen dann zu Problemen des Realismus. Und da Naturalisten im Allgemeinen Realisten sind, werden die anschließenden Fragen über Wahrheit, Naturgesetze, Weltentstehung, Kosmologie, Evolution, Leib-Seele-Problem, Willensfreiheit, Religion, Moral und Pseudowissenschaften vor einem realistischen Hintergrund beantwortet. (shrink)

A god is a cosmic designer-creator. Atheism says the number of gods is 0. But it is hard to defeat the minimal thesis that some possible universe is actualized by some possible god. Monotheists say the number of gods is 1. Yet no degree of perfection can be coherently assigned to any unique god. Lewis says the number of gods is at least the second beth number. Yet polytheists cannot defend an arbitrary plural number of gods. An alternative is that, (...) for every ordinal, there is a god whose perfection is proportional to it. The n -th god actualizes the best universe(s) in the n -th level of an axiological hierarchy of possible universes. Despite its unorthodoxy, ordinal polytheism has many metaphysically attractive features and merits more serious study. (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)

In [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that Tα≻TωTα≻Tω, the (...) smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation (...) does not occur for the methods of hypercomputation under attack, and why it is unlikely to occur for any other serious methods. Introduction Issues with specific hypermachines Conclusions for hypercomputation. (shrink)

This paper investigates the view that digital hypercomputing is a good reason for rejection or re-interpretation of the Church-Turing thesis. After suggestion that such re-interpretation is historically problematic and often involves attack on a straw man (the ‘maximality thesis’), it discusses proposals for digital hypercomputing with Zeno-machines , i.e. computing machines that compute an infinite number of computing steps in finite time, thus performing supertasks. It argues that effective computing with Zeno-machines falls into a dilemma: either they are specified such (...) that they do not have output states, or they are specified such that they do have output states, but involve contradiction. Repairs though non-effective methods or special rules for semi-decidable problems are sought, but not found. The paper concludes that hypercomputing supertasks are impossible in the actual world and thus no reason for rejection of the Church-Turing thesis in its traditional interpretation. (shrink)

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a (...) Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers. (shrink)

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

The starting point of the following considerations is a case study concerning the discovery of Halley's comet and the theoretical description of its path. It is shown that the set of objects involved in that system and the time interval during which their paths are observed are determined in a theory dependent way – thereby making use of the very theory later used for that system's theoretical description. Metatheoretical consequences this fact has with respect to the structuralist view of empirical (...) theories are discussed in detail. German Den Ausgangspunkt der folgenden Überlegungen bildet eine Fallstudie, die der Entdeckung und theoretischen Beschreibung des Halleyschen Kometen gewidmet ist. Es wird gezeigt, dass bei diesem System die Menge der involvierten Objekte und die Zeitintervalle, über die sich die Beobachtung der Bahnen dieser Objekte erstreckt, in theorieabhängiger Weise bestimmt werden – und zwar in Abhängigkeit von genau derjenigen Theorie, die anschließend zur theoretischen Beschreibung des Systems eingesetzt wird. Metatheoretische Konsequenzen, die sich aus diesem Umstand insbesondere für das strukturalistische Theorienkonzept ergeben, werden im Detail analysiert. (shrink)

Certain enterprises at the fringes of science, such as intelligent design creationism, claim to identify phenomena that go beyond not just our present physics but any possible physical explanation. Asking what it would take for such a claim to succeed, we introduce a version of physicalism that formulates the proposition that all available data sets are best explained by combinations of “chance and necessity”—algorithmic rules and randomness. Physicalism would then be violated by the existence of oracles that produce certain kinds (...) of noncomputable functions. Examining how a candidate for such an oracle would be evaluated leads to questions that do not admit an easy resolution. Since we lack any plausible candidate for any such oracle, however, chance-and-necessity physicalism appears very likely to be correct. (shrink)

There are two main ways to teach a course online: synchronously or asynchronously. In an asynchronous course, students can log on at their convenience and do the course work. In a synchronous course, there is a requirement that all students be online at specific times, to allow for a shared course environment. In this article, the author discusses the strengths and weaknesses of synchronous online learning for the teaching of undergraduate philosophy courses. The author discusses specific strategies and technologies he (...) uses in the teaching of online philosophy courses. In particular, the author discusses how he uses videoconferencing to create a classroom-like environment in an online class. (shrink)