View topic on PhilPapers for more information
Related categories

37 found
Order:
More results on PhilPapers
  1. A Contradiction and P=NP Problem.Farzad Didehvar - manuscript
    Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  2. Is Classical Mathematics Appropriate for Theory of Computation?Farzad Didehvar - manuscript
    Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this paradox, it (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   1 citation  
  3. Halting Problem Proofs Refuted on the Basis of Software Engineering ?P. Olcott - manuscript
    This is an explanation of a possible new insight into the halting problem provided in the language of software engineering. Technical computer science terms are explained using software engineering terms. No knowledge of the halting problem is required. -/- It is based on fully operational software executed in the x86utm operating system. The x86utm operating system (based on an excellent open source x86 emulator) was created to study the details of the halting problem proof counter-examples at the much higher level (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  4. Halting Problem Undecidability and Infinitely Nested Simulation (V3).P. Olcott - manuscript
    By making a slight refinement to the halt status criterion measure that remains consistent with the original a halt decider may be defined that correctly determines the halt status of the conventional halting problem proof counter-examples. This refinement overcomes the pathological self-reference issue that previously prevented halting decidability.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  5. Halting Problem Undecidability and Infinitely Nested Simulation (V4).P. Olcott - manuscript
    A Simulating Halt Decider (SHD) computes the mapping from its input to its own accept or reject state based on whether or not the input simulated by a UTM would reach its final state in a finite number of simulated steps. -/- A halt decider (because it is a decider) must report on the behavior specified by its finite string input. This is its actual behavior when it is simulated by the UTM contained within its simulating halt decider while this (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  6. Halting Problem Undecidability and Infinitely Nested Simulation (V5).P. Olcott - manuscript
    This is an explanation of a key new insight into the halting problem provided in the language of software engineering. Technical computer science terms are explained using software engineering terms. -/- To fully understand this paper a software engineer must be an expert in the C programming language, the x86 programming language, exactly how C translates into x86 and what an x86 process emulator is. No knowledge of the halting problem is required.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  7. Halting Problem Undecidability and Infinitely Nested Simulation.P. Olcott - manuscript
    The halting theorem counter-examples present infinitely nested simulation (non-halting) behavior to every simulating halt decider. The pathological self-reference of the conventional halting problem proof counter-examples is overcome. The halt status of these examples is correctly determined. A simulating halt decider remains in pure simulation mode until after it determines that its input will never reach its final state. This eliminates the conventional feedback loop where the behavior of the halt decider effects the behavior of its input.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  8. Rebutting the Sipser Halting Problem Proof.P. Olcott - manuscript
    MIT Professor Michael Sipser has agreed that the following verbatim paragraph is correct (he has not agreed to anything else in this paper) -------> -/- If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  9. Why AI Will Never Rule the World (Interview).Luke Dormehl, Jobst Landgrebe & Barry Smith - 2022 - Digital Trends.
    Call it the Skynet hypothesis, Artificial General Intelligence, or the advent of the Singularity — for years, AI experts and non-experts alike have fretted (and, for a small group, celebrated) the idea that artificial intelligence may one day become smarter than humans. -/- According to the theory, advances in AI — specifically of the machine learning type that’s able to take on new information and rewrite its code accordingly — will eventually catch up with the wetware of the biological brain. (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  10. Why Machines Will Never Rule the World: Artificial Intelligence Without Fear.Jobst Landgrebe & Barry Smith - 2022 - Abingdon, England: Routledge.
    The book’s core argument is that an artificial intelligence that could equal or exceed human intelligence—sometimes called artificial general intelligence (AGI)—is for mathematical reasons impossible. It offers two specific reasons for this claim: Human intelligence is a capability of a complex dynamic system—the human brain and central nervous system. Systems of this sort cannot be modelled mathematically in a way that allows them to operate inside a computer. In supporting their claim, the authors, Jobst Landgrebe and Barry Smith, marshal evidence (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   1 citation  
  11. Computability, Notation, and de Re Knowledge of Numbers.Stewart Shapiro, Eric Snyder & Richard Samuels - 2022 - Philosophies 1 (7).
    Saul Kripke once noted that there is a tight connection between computation and de re knowledge of whatever the computation acts upon. For example, the Euclidean algorithm can produce knowledge of which number is the greatest common divisor of two numbers. Arguably, algorithms operate directly on syntactic items, such as strings, and on numbers and the like only via how the numbers are represented. So we broach matters of notation. The purpose of this article is to explore the relationship between (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  12. Strengthening Weak Emergence.Nora Berenstain - 2020 - Erkenntnis 87 (5):2457-2474.
    Bedau's influential (1997) account analyzes weak emergence in terms of the non-derivability of a system’s macrostates from its microstates except by simulation. I offer an improved version of Bedau’s account of weak emergence in light of insights from information theory. Non-derivability alone does not guarantee that a system’s macrostates are weakly emergent. Rather, it is non-derivability plus the algorithmic compressibility of the system’s macrostates that makes them weakly emergent. I argue that the resulting information-theoretic picture provides a metaphysical account of (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  13. Hilbert's 10th Problem for Solutions in a Subring of Q.Agnieszka Peszek & Apoloniusz Tyszka - 2019 - Scientific Annals of Computer Science 29 (1):101-111.
    Yuri Matiyasevich's theorem states that the set of all Diophantine equations which have a solution in non-negative integers is not recursive. Craig Smoryński's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. Let R be a subring of Q with or without 1. By H_{10}(R), we denote the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide whether (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  14. Review of 'The Outer Limits of Reason' by Noson Yanofsky 403p (2013) (Review Revised 2019).Michael Starks - 2019 - In Suicidal Utopian Delusions in the 21st Century -- Philosophy, Human Nature and the Collapse of Civilization -- Articles and Reviews 2006-2019 4th Edition Michael Starks. Las Vegas, NV USA: Reality Press. pp. 299-316.
    I give a detailed review of 'The Outer Limits of Reason' by Noson Yanofsky from a unified perspective of Wittgenstein and evolutionary psychology. I indicate that the difficulty with such issues as paradox in language and math, incompleteness, undecidability, computability, the brain and the universe as computers etc., all arise from the failure to look carefully at our use of language in the appropriate context and hence the failure to separate issues of scientific fact from issues of how language works. (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  15. Wolpert, Chaitin e Wittgenstein em impossibilidade, incompletude, o paradoxo do mentiroso, o teísmo, os limites da computação, um princípio de incerteza mecânica não quântica e o universo como computador — o teorema final na teoria da máquina de Turing (revisado 2019).Michael Richard Starks - 2019 - In Delírios Utópicos Suicidas no Século XXI Filosofia, Natureza Humana e o Colapso da Civilization- Artigos e Comentários 2006-2019 5ª edição. Las Vegas, NV USA: Reality Press. pp. 183-187.
    Eu li muitas discussões recentes sobre os limites da computação e do universo como computador, na esperança de encontrar alguns comentários sobre o trabalho surpreendente do físico polimatemático e teórico da decisão David Wolpert, mas não encontrei uma única citação e assim que eu apresento este muito breve Resumo. Wolpert provou alguma impossibilidade impressionante ou teoremas da incompletude (1992 a 2008-Veja arxiv dot org) nos limites à inferência (computação) que são tão gerais que são independentes do dispositivo que faz a (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  16. Counterpossibles in Science: The Case of Relative Computability.Matthias Jenny - 2018 - Noûs 52 (3):530-560.
    I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as 'If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable,' which is true, and 'If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable,' which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What’s more, I (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   26 citations  
  17. The Changing Practices of Proof in Mathematics: Gilles Dowek: Computation, Proof, Machine. Cambridge: Cambridge University Press, 2015. Translation of Les Métamorphoses du Calcul, Paris: Le Pommier, 2007. Translation From the French by Pierre Guillot and Marion Roman, $124.00HB, $40.99PB. [REVIEW]Andrew Arana - 2017 - Metascience 26 (1):131-135.
    Review of Dowek, Gilles, Computation, Proof, Machine, Cambridge University Press, Cambridge, 2015. Translation of Les Métamorphoses du calcul, Le Pommier, Paris, 2007. Translation from the French by Pierre Guillot and Marion Roman.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  18. Info-Computational Constructivism and Cognition.G. Dodig-Crnkovic - 2014 - Constructivist Foundations 9 (2):223-231.
    Context: At present, we lack a common understanding of both the process of cognition in living organisms and the construction of knowledge in embodied, embedded cognizing agents in general, including future artifactual cognitive agents under development, such as cognitive robots and softbots. Purpose: This paper aims to show how the info-computational approach (IC) can reinforce constructivist ideas about the nature of cognition and knowledge and, conversely, how constructivist insights (such as that the process of cognition is the process of life) (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   3 citations  
  19. Single-Tape and Multi-Tape Turing Machines Through the Lens of the Grossone Methodology.Yaroslav Sergeyev & Alfredo Garro - 2013 - Journal of Supercomputing 65 (2):645-663.
    The paper investigates how the mathematical languages used to describe and to observe automatic computations influence the accuracy of the obtained results. In particular, we focus our attention on Single and Multi-tape Turing machines which are described and observed through the lens of a new mathematical language which is strongly based on three methodological ideas borrowed from Physics and applied to Mathematics, namely: the distinction between the object (we speak here about a mathematical object) of an observation and the instrument (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   1 citation  
  20. Laws of Form and the Force of Function: Variations on the Turing Test.Hajo Greif - 2012 - In Vincent C. Müller & Aladdin Ayesh (eds.), Revisiting Turing and His Test: Comprehensiveness, Qualia, and the Real World. AISB. pp. 60-64.
    This paper commences from the critical observation that the Turing Test (TT) might not be best read as providing a definition or a genuine test of intelligence by proxy of a simulation of conversational behaviour. Firstly, the idea of a machine producing likenesses of this kind served a different purpose in Turing, namely providing a demonstrative simulation to elucidate the force and scope of his computational method, whose primary theoretical import lies within the realm of mathematics rather than cognitive modelling. (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  21. Intractability and the Use of Heuristics in Psychological Explanations.Iris Rooij, Cory Wright & Todd Wareham - 2012 - Synthese 187 (2):471-487.
    Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   10 citations  
  22. A Paradox Related to the Turing Test.Samuel Alexander - 2011 - The Reasoner 5 (6):90-90.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  23. 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   Download  
     
    Export citation  
     
    Bookmark   2 citations  
  24. Observability of Turing Machines: A Refinement of the Theory of Computation.Yaroslav Sergeyev & Alfredo Garro - 2010 - Informatica 21 (3):425–454.
    The Turing machine is one of the simple abstract computational devices that can be used to investigate the limits of computability. In this paper, they are considered from several points of view that emphasize the importance and the relativity of mathematical languages used to describe the Turing machines. A deep investigation is performed on the interrelations between mechanical computations and their mathematical descriptions emerging when a human (the researcher) starts to describe a Turing machine (the object of the study) by (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   3 citations  
  25. A New Applied Approach for Executing Computations with Infinite and Infinitesimal Quantities.Yaroslav D. Sergeyev - 2008 - Informatica 19 (4):567-596.
    A new computational methodology for executing calculations with infinite and infinitesimal quantities is described in this paper. It is based on the principle ‘The part is less than the whole’ introduced by Ancient Greeks and applied to all numbers (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite). It is shown that it becomes possible to write down finite, infinite, and infinitesimal numbers by a finite number of symbols as particular cases of a unique framework. The (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   5 citations  
  26. Blinking Fractals and Their Quantitative Analysis Using Infinite and Infinitesimal Numbers.Yaroslav Sergeyev - 2007 - Chaos, Solitons and Fractals 33 (1):50-75.
    The paper considers a new type of objects – blinking fractals – that are not covered by traditional theories studying dynamics of self-similarity processes. It is shown that the new approach allows one to give various quantitative characteristics of the newly introduced and traditional fractals using infinite and infinitesimal numbers proposed recently. In this connection, the problem of the mathematical modelling of continuity is discussed in detail. A strong advantage of the introduced computational paradigm consists of its well-marked numerical character (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   4 citations  
  27. Formulas for Computable and Non-Computable Functions.Samuel Alexander - 2006 - Rose-Hulman Undergraduate Mathematics Journal 7 (2).
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  28. Possible M-Diagrams of Models of Arithmetic.Andrew Arana - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001.
    In this paper I begin by extending two results of Solovay; the first characterizes the possible Turing degrees of models of True Arithmetic (TA), the complete first-order theory of the standard model of PA, while the second characterizes the possible Turing degrees of arbitrary completions of P. I extend these two results to characterize the possible Turing degrees of m-diagrams of models of TA and of arbitrary complete extensions of PA. I next give a construction showing that the conditions Solovay (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  29. Three Concepts of Decidability for General Subsets of Uncountable Spaces.Matthew W. Parker - 2003 - Theoretical Computer Science 351 (1):2-13.
    There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   3 citations  
  30. The Theory of Computability Developed in Terms of Satisfaction.James Cain - 1999 - Notre Dame Journal of Formal Logic 40 (4):515-532.
    The notion of computability is developed through the study of the behavior of a set of languages interpreted over the natural numbers which contain their own fully defined satisfaction predicate and whose only other vocabulary is limited to "0", individual variables, the successor function, the identity relation and operators for disjunction, conjunction, and existential quantification.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  31. The Decision Problem for Entanglement.Wayne C. Myrvold - 1997 - In Robert S. Cohen, Michael Horne & John Stachel (eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies for Abner Shimony. Kluwer Academic Publishers. pp. 177--190.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   4 citations  
  32. Automated Theorem Proving and Its Prospects. [REVIEW]Desmond Fearnley-Sander - 1995 - PSYCHE: An Interdisciplinary Journal of Research On Consciousness 2.
    REVIEW OF: Automated Development of Fundamental Mathematical Theories by Art Quaife. (1992: Kluwer Academic Publishers) 271pp. Using the theorem prover OTTER Art Quaife has proved four hundred theorems of von Neumann-Bernays-Gödel set theory; twelve hundred theorems and definitions of elementary number theory; dozens of Euclidean geometry theorems; and Gödel's incompleteness theorems. It is an impressive achievement. To gauge its significance and to see what prospects it offers this review looks closely at the book and the proofs it presents.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  33. Computability in Quantum Mechanics.Wayne C. Myrvold - 1995 - In Werner De Pauli-Schimanovich, Eckehart Köhler & Friedrich Stadler (eds.), Vienna Circle Institute Yearbook. Kluwer Academic Publishers. pp. 33-46.
    In this paper, the issues of computability and constructivity in the mathematics of physics are discussed. The sorts of questions to be addressed are those which might be expressed, roughly, as: Are the mathematical foundations of our current theories unavoidably non-constructive: or, Are the laws of physics computable?
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   5 citations  
  34. Recursive Predicates and Quantifiers.S. C. Kleene - 1943 - Transactions of the American Mathematical Society 53:41-73.
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark   33 citations  
  35. (TC* ،زمان فازی ) تاثیر و تاثر منطق و پارادوکسها بر نظریه محاسبات عام. [REVIEW]Didehvar Farzad - manuscript
    در تکوین نظریه محاسبات از اوایل قرن بیستم پارادکسها و خود ارجاعی نقش ویژه ای را بازی کرده اند. هر چند نظریه محاسبات عام بر اساس تعریف ماشین تورینگ، فرض تورینگ_چرچ و کاربردهای آن بنا شده ،اما از همان ابتدا تا به امروز منطق و حوزه های مختلف این علم در ارتباط تنگاتنگ با این تیوری و در ابتدا نظریه محاسبات خاص بوده و این ارتباط روز به روز گسترده و گسترده تر گشته است. از تاثیر پارادوکس دروغگو و پارادکس (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  36. Defining a Decidability Decider for the Halting Problem.Pete Olcott - manuscript
    When we understand that every potential halt decider must derive a formal mathematical proof from its inputs to its final states previously undiscovered semantic details emerge. -/- When-so-ever the potential halt decider cannot derive a formal proof from its input strings to its final states of Halts or Loops, undecidability has been decided. -/- The formal proof involves tracing the sequence of state transitions of the input TMD as syntactic logical consequence inference steps in the formal language of Turing Machine (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark  
  37. Halting Problem Proof From Finite Strings to Final States.Pete Olcott - manuscript
    If there truly is a proof that shows that no universal halt decider exists on the basis that certain tuples: (H, Wm, W) are undecidable, then this very same proof (implemented as a Turing machine) could be used by H to reject some of its inputs. When-so-ever the hypothetical halt decider cannot derive a formal proof from its input strings and initial state to final states corresponding the mathematical logic functions of Halts(Wm, W) or Loops(Wm, W), halting undecidability has been (...)
    Remove from this list   Download  
     
    Export citation  
     
    Bookmark