This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related

Contents
41 found
Order:
  1. David Wolpert on impossibility, incompleteness, the liar paradox, the limits of computation, a non-quantum mechanical uncertainty principle and the universe as computer—the ultimate theorem in Turing Machine Theory.Michael Starks - manuscript
    I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  2. Only Human: a book review of The Turing Guide. [REVIEW]Bjørn Kjos-Hanssen - forthcoming - Notices of the American Mathematical Society 66 (4).
    This is a review of The Turing Guide (2017), written by Jack Copeland, Jonathan Bowen, Mark Sprevak, Robin Wilson, and others. The review includes a new sociological approach to the problem of computability in physics.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  3. The Church-Turing Thesis and Hyper-computation.O. Shagrir & I. Pitowsky - forthcoming - Minds and Machines.
  4. Limitative computational explanations.André Curtis-Trudel - 2023 - Philosophical Studies 180 (12):3441-3461.
    What is computational explanation? Many accounts treat it as a kind of causal explanation. I argue against two more specific versions of this view, corresponding to two popular treatments of causal explanation. The first holds that computational explanation is mechanistic, while the second holds that it is interventionist. However, both overlook an important class of computational explanations, which I call limitative explanations. Limitative explanations explain why certain problems cannot be solved computationally, either in principle or in practice. I argue that (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5. ¿Existen las Máquinas Aceleradas de Turing? Paradojas y posibilidades lógicas.Jose Alejandro Fernández Cuesta - 2023 - Techno Review. International Technology, Science and Society Review 13 (1):49.74.
    Las máquinas aceleradas de Turing (ATMs) son dispositivos capaces de ejecutar súper-tareas. Sin embargo, el simple ejercicio de definirlas ha generado varias paradojas. En el presente artículo se definirán las nociones de súper-tarea y ATM de manera exhaustiva y se aclarará qué debe entenderse en un contexto lógico-formal cuando se pregunta por la existencia de un objeto. A partir de la distinción entre posibilidades lógicas y físicas se disolverán las paradojas y se concluirá que las ATMs son posibles y existen (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  6. Not All Computational Methods Are Effective Methods.Mark Sprevak - 2022 - Philosophies 7 (5):113.
    An effective method is a computational method that might, in principle, be executed by a human. In this paper, I argue that there are methods for computing that are not effective methods. The examples I consider are taken primarily from quantum computing, but these are only meant to be illustrative of a much wider class. Quantum inference and quantum parallelism involve steps that might be implemented in multiple physical systems, but cannot be implemented, or at least not at will, by (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7. The Physics of God and the Quantum Gravity Theory of Everything.James Redford - 2021 - In The Physics of God and the Quantum Gravity Theory of Everything: And Other Selected Works. Chișinău, Moldova: Eliva Press. pp. 1-186.
    Analysis is given of the Omega Point cosmology, an extensively peer-reviewed proof (i.e., mathematical theorem) published in leading physics journals by professor of physics and mathematics Frank J. Tipler, which demonstrates that in order for the known laws of physics to be mutually consistent, the universe must diverge to infinite computational power as it collapses into a final cosmological singularity, termed the Omega Point. The theorem is an intrinsic component of the Feynman-DeWitt-Weinberg quantum gravity/Standard Model Theory of Everything (TOE) describing (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8. Weaker variants of infinite time Turing machines.Matteo Bianchetti - 2020 - Archive for Mathematical Logic 59 (3-4):335-365.
    Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if the content (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  9. (1 other version)Representation and Reality by Language: How to make a home quantum computer?Vasil Penchev - 2020 - Philosophy of Science eJournal (Elsevier: SSRN) 13 (34):1-14.
    A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having a remarkable (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  10. Two Strategies to Infinity: Completeness and Incompleteness. The Completeness of Quantum Mechanics.Vasil Penchev - 2020 - High Performance Computing eJournal 12 (11):1-8.
    Two strategies to infinity are equally relevant for it is as universal and thus complete as open and thus incomplete. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, thеse phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  11. A Class of Examples Demonstrating That 'P ≠ NP' in the 'P Vs NP' Problem.Vasil Penchev - 2020 - Computing Methodology eJournal (Elsevier: SSRN) 3 (19):1-19.
    The CMI Millennium “P vs NP Problem” can be resolved e.g. if one shows at least one counterexample to the "P = NP" conjecture. A certain class of problems being such counterexamples will be formulated. This implies the rejection of the hypothesis that "P = NP" for any conditions satisfying the formulation of the problem. Thus, the solution "P is different from NP" of the problem in general is proved. The class of counterexamples can be interpreted as any quantum superposition (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12. A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory.Vasil Penchev - 2020 - Information Theory and Research eJournal 1 (15):1-13.
    A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  13. Physical Perspectives on Computation, Computational Perspectives on Physics.Michael E. Cuffaro & Samuel C. Fletcher (eds.) - 2018 - Cambridge University Press.
    Although computation and the science of physical systems would appear to be unrelated, there are a number of ways in which computational and physical concepts can be brought together in ways that illuminate both. This volume examines fundamental questions which connect scholars from both disciplines: is the universe a computer? Can a universal computing machine simulate every physical process? What is the source of the computational power of quantum computers? Are computational approaches to solving physical problems and paradoxes always fruitful? (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  14. Why We Shouldn't Reason Classically, and the Implications for Artificial Intelligence.Douglas Campbell - 2016 - In Vincent C. Müller (ed.), Computing and philosophy: Selected papers from IACAP 2014. Cham: Springer. pp. 151--165.
    In this paper I argue that human beings should reason, not in accordance with classical logic, but in accordance with a weaker ‘reticent logic’. I characterize reticent logic, and then show that arguments for the existence of fundamental Gödelian limitations on artificial intelligence are undermined by the idea that we should reason reticently, not classically.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15. Practical Intractability: A Critique of the Hypercomputation Movement. [REVIEW]Aran Nayebi - 2014 - Minds and Machines 24 (3):275-305.
    For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more (...)
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  16. (11 other versions)Отвъд машината на Тюринг: квантовият компютър.Vasil Penchev - 2014 - Sofia: BAS: ISSK (IPS).
    Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum computer might (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17. From the Closed Classical Algorithmic Universe to an Open World of Algorithmic Constellations.Mark Burgin & Gordana Dodig-Crnkovic - 2013 - In Gordana Dodig-Crnkovic Raffaela Giovagnoli (ed.), Computing Nature. pp. 241--253.
    In this paper we analyze methodological and philosophical implications of algorithmic aspects of unconventional computation. At first, we describe how the classical algorithmic universe developed and analyze why it became closed in the conventional approach to computation. Then we explain how new models of algorithms turned the classical closed algorithmic universe into the open world of algorithmic constellations, allowing higher flexibility and expressive power, supporting constructivism and creativity in mathematical modeling. As Goedels undecidability theorems demonstrate, the closed algorithmic universe restricts (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  18. Eric Winsberg: Science in the Age of Computer Simulation: The University of Chicago Press, Chicago, IL, 2010, 168 pp., $ 24.00 , ISBN: 978-0-226-90204-3. [REVIEW]Stefan Gruner - 2013 - Minds and Machines 23 (2):251-254.
  19. Ideal Negative Conceivability and the Halting Problem.Manolo Martínez - 2013 - Erkenntnis 78 (5):979-990.
    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.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  20. On the Possibilities of Hypercomputing Supertasks.Vincent C. Müller - 2011 - Minds and Machines 21 (1):83-96.
    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 (...)
    Remove from this list   Direct download (10 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  21. The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
    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. (...)
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    Bookmark   24 citations  
  22. A brief critique of pure hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.
    Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for non-terminating processes are likewise (...)
    Remove from this list   Direct download (9 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  23. Physics of emergence and organization.Ignazio Licata & Ammar Sakaji (eds.) - 2008 - United Kingdom: World Scientific.
    This book is a state-of-the-art review on the Physics of Emergence. Foreword v Gregory J. Chaitin Preface vii Ignazio Licata Emergence and Computation at the Edge of Classical and Quantum Systems 1 Ignazio Licata Gauge Generalized Principle for Complex Systems 27 Germano Resconi Undoing Quantum Measurement: Novel Twists to the Physical Account of Time 61 Avshalom C. Elitzur and Shahar Dolev Process Physics: Quantum Theories as Models of Complexity 77 Kirsty Kitto A Cross-disciplinary Framework for the Description of Contextually Mediated (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  24. Effective Physical Processes and Active Information in Quantum Computing.Ignazio Licata - 2007 - Quantum Biosystems 1 (1):51-65.
    The recent debate on hypercomputation has raised new questions both on the computational abilities of quantum systems and the Church-Turing Thesis role in Physics.We propose here the idea of “effective physical process” as the essentially physical notion of computation. By using the Bohm and Hiley active information concept we analyze the differences between the standard form (quantum gates) and the non-standard one (adiabatic and morphogenetic) of Quantum Computing, and we point out how its Super-Turing potentialities derive from an incomputable information (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  25. Why there is no such discipline as hypercomputation.Martin Davis - 2006 - Applied Mathematics and Computation, Volume 178, Issue 1, 1.
    Remove from this list  
     
    Export citation  
     
    Bookmark   12 citations  
  26. The Myth of Hypercomputation.Martin Davis - 2004 - In Christof Teuscher (ed.), Alan Turing: Life and Legacy of a Great Thinker. Springer-Verlag. pp. 196-211.
    Under the banner of "hypercomputat ion" various claims are being made for the feasibility of modes of computation that go beyond what is permitted by Turing computability. In this article it will be shown that such claims fly in the face of the inability of all currently accepted physical theories to deal with infinite precision real numbers. When the claims are viewed critically, it is seen that they amount to little more than the obvious comment that if non-computable inputs are (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   23 citations  
  27. Notes on Landauer's principle, reversible computation, and Maxwell's Demon.Charles H. Bennett - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (3):501-510.
    Landauer's principle, often regarded as the basic principle of the thermodynamics of information processing, holds that any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information-bearing degrees of freedom of the information-processing apparatus or its environment. Conversely, it is generally accepted that any logically reversible transformation of information can in principle be accomplished by an appropriate physical mechanism operating in a (...)
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    Bookmark   37 citations  
  28. Computation and hypercomputation.Mike Stannett - 2003 - Minds and Machines 13 (1):115-153.
    Does Nature permit the implementation of behaviours that cannot be simulated computationally? We consider the meaning of physical computation in some detail, and present arguments in favour of physical hypercomputation: for example, modern scientific method does not allow the specification of any experiment capable of refuting hypercomputation. We consider the implications of relativistic algorithms capable of solving the (Turing) Halting Problem. We also reject as a fallacy the argument that hypercomputation has no relevance because non-computable values are indistinguishable from sufficiently (...)
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  29. 'Turing limit'. Some of them (Steinhart, Copeland) represent extensions of Tur-ing's account, whereas others defend alternatives notions of effective computability (Bringsjord and Zenzen, Wells).Carol E. Cleland - 2002 - Minds and Machines 12:157-158.
  30. Hypercomputation: Computing more than the Turing machine.Toby Ord - 2002 - Dissertation, University of Melbourne
    In this report I provide an introduction to the burgeoning field of hypercomputation – the study of machines that can compute more than Turing machines. I take an extensive survey of many of the key concepts in the field, tying together the disparate ideas and presenting them in a structure which allows comparisons of the many approaches and results. To this I add several new results and draw out some interesting consequences of hypercomputation for several different disciplines.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   8 citations  
  31. Ordinary Devices: Reply to Bringsjord's `Clarifying the Logic of Anti-Computationalism: Reply to Hauser'1.Larry Hauser - 2000 - Minds and Machines 10 (1):115-117.
    What Robots Can and Can't Be (hereinafter Robots) is, as Selmer Bringsjord says "intended to be a collection of formal-arguments-that-border-on-proofs for the proposition that in all worlds, at all times, machines can't be minds" (Bringsjord, forthcoming). In his (1994) "Précis of What Robots Can and Can't Be" Bringsjord styles certain of these arguments as proceeding "repeatedly . . . through instantiations of" the "simple schema".
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  32. Beyond the universal Turing machine.Jack Copeland - 1999 - Australasian Journal of Philosophy 77 (1):46-67.
    We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    Bookmark   20 citations  
  33. Super Turing-machines.Jack Copeland - 1998 - Complexity 4 (1):30-32.
    The tape is divided into squares, each square bearing a single symbol—'0' or '1', for example. This tape is the machine's general-purpose storage medium: the machine is set in motion with its input inscribed on the tape, output is written onto the tape by the head, and the tape serves as a short-term working memory for the results of intermediate steps of the computation. The program governing the particular computation that the machine is to perform is also stored on the (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  34. Why Godel's theorem cannot refute computationalism: A reply to Penrose.Geoffrey LaForte, Patrick J. Hayes & Kenneth M. Ford - 1998 - Artificial Intelligence 104 (1-2):265-286.
  35. The broad conception of computation.Jack Copeland - 1997 - American Behavioral Scientist 40 (6):690-716.
    A myth has arisen concerning Turing's paper of 1936, namely that Turing set forth a fundamental principle concerning the limits of what can be computed by machine - a myth that has passed into cognitive science and the philosophy of mind, to wide and pernicious effect. This supposed principle, sometimes incorrectly termed the 'Church-Turing thesis', is the claim that the class of functions that can be computed by machines is identical to the class of functions that can be computed by (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  36. Counting information: A note on physicalized numbers. [REVIEW]Brian Rotman - 1996 - Minds and Machines 6 (2):229-238.
    Existing work on the ultimate limits of computation has urged that the apparatus of real numbers should be eschewed as an investigative tool and replaced by discrete mathematics. The present paper argues for a radical extension of this viewpoint: not only the continuum but all infinitary constructs including the rationals and the potential infinite sequence of whole numbers need to be eliminated if a self-consistent investigative framework is to be achieved.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  37. The Physical Church Thesis and Physical Computational Complexity.Itamar Pitowski - 1990 - Iyyun 39:81-99.
  38. Computationalism is Dead; Now What?Selmer Bringsjord - unknown
    In this paper I place Jim Fetzer's esemplastic burial of the computational conceptionof mind within the context of both my own burial and the theory of mind I would put in place of this dead doctrine. My view..
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  39. The Impact of Computing on Epistemology: Knowing Gödel's Mind Through Computation.Selmer Bringsjord - unknown
    I know that those of you who know my mind know that I think I know that we can't know Gödel's mind through computation: ``The Impact : Failing to Know " If computationalism is false, observant philosophers willing to get their hands dirty should be able to find tell-tale signs today: automated theorem proving tomorrow (Eastern APA): robots as zombanimals But let's start with little 'ol me, and literary, not mathematical, creativity: Selmer (samples) vs. Brutus1 (samples again).
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  40. On the physical possibility of ordinal computation (draft).Jeffrey A. Barrett & Wayne Aitken - unknown
    α-recursion lifts classical recursion theory from the first transfinite ordinal ω to an arbitrary admissible ordinal α [10]. Idealized computational models for α-recursion analogous to Turing machine models for classical recursion have been proposed and studied [4] and [5] and are applicable in computational approaches to the foundations of logic and mathematics [8]. They also provide a natural setting for modeling extensions of the algorithmic logic described in [1] and [2]. On such models, an α-Turing machine can complete a θ-step (...)
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  41. On the impossibility of using analogue machines to calculate non-computable functions.Robin O. Gandy - manuscript - Translated by Aran Nayebi.
    A number of examples have been given of physical systems (both classical and quantum mechanical) which when provided with a (continuously variable) computable input will give a non-computable output. It has been suggested that these systems might allow one to design analogue machines which would calculate the values of some number-theoretic non-computable function. Analysis of the examples show that the suggestion is wrong. In Section 4 I claim that given a reasonable definition of analogue machine it will always be wrong. (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark