- Submit
-
Browse
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- More
Switch to: References
Citations of:
Infinite time Turing machines
Journal of Symbolic Logic 65 (2):567-604 (2000)
Add citations
You must login to add citations.
|
|
|
We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time generalization of the (...) |
|
|
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 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 (...) |
|
|
We study the complexity of the classification problem for countable models of set theory (). We prove that the classification of arbitrary countable models of is Borel complete, meaning that it is as complex as it can conceivably be. We then give partial results concerning the classification of countable well‐founded models of. |
|
|
|
|
|
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 (...)) |
|
|
|
|
|
We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and (...) |
|
|
|
|
|
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 (...) |
|
|
I articulate a novel modal argument for P=NP. |
|
|
We analyse Kreisel’s notion of human-effective computability. Like Kreisel, we relate this notion to a concept of informal provability, but we disagree with Kreisel about the precise way in which this is best done. The resulting two different ways of analysing human-effective computability give rise to two different variants of Church’s thesis. These are both investigated by relating them to transfinite progressions of formal theories in the sense of Feferman. |
|
|
In this note, we consider constraints on the physical possibility of transfinite Turing machines that arise from how one models the continuous structure of space and time in one's best physical theories. We conclude by suggesting a version of Church's thesis appropriate as an upper bound for physical computation given how space and time are modeled on our current physical theories. |
|
|
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 (...) |
|
|
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. |
|
|
In a 2022 paper, Hamami claimed that the orthodox view in mathematics is that a proof is rigorous if it can be translated into a derivation. Hamami then developed a descriptive account that explains how mathematicians check proofs for rigor in this sense and how they develop the capacity to do so. By exploring introductory texts in computability theory, we demonstrate that Hamami’s descriptive account does not accord with actual mathematical practice with respect to computability theory. We argue instead for (...) |
|
|
If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...) |
|
|
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, (...) |
|
|
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 (...) |
|
|
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 (...) |
|
|
Revision sequences are a kind of transfinite sequences which were introduced by Herzberger and Gupta in 1982 as the main mathematical tool for developing their respective revision theories of truth. We generalise revision sequences to the notion of cofinally invariant sequences, showing that several known facts about Herzberger’s and Gupta’s theories also hold for this more abstract kind of sequences and providing new and more informative proofs of the old results. |
|
|
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. (...) |
|
|
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 (...) |
|
|
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 (...) |
|
|
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. |
|
|
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 (...) |
|
|
A supertask is a task that consists in infinitely many component steps, but which in some sense is completed in a finite amount of time. Supertasks were studied by the pre-Socratics and continue to be objects of interest to modern philosophers, logicians and physicists. The term “super-task” itself was coined by J.F. Thomson (1954). Here we begin with an overview of the analysis of supertasks and their mechanics. We then discuss the possibility of supertasks from the perspective of general relativity. |
|
|
|
|
|
Selmer Bringsjord & Joshua Taylor∗ Department of Cognitive Science Department of Computer Science The Rensselaer AI & Reasoning (RAIR) Lab Rensselaer Polytechnic Institute (RPI) Troy NY 12180 USA http://www.rpi.edu/∼brings {selmer,tayloj}@rpi.edu.. |
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-64dd777598-wg6s5 uwo