# Computability

Related
Siblings

Contents
47 found
Order:
1. 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.

Export citation

Bookmark
2. 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 (...)

Export citation

Bookmark   1 citation
3. 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.

Export citation

Bookmark
4. A simulating halt decider correctly predicts whether or not its correctly simulated input can possibly reach its own final state and halt. It does this by correctly recognizing several non-halting behavior patterns in a finite number of steps of correct simulation. Inputs that do terminate are simply simulated until they complete.

Export citation

Bookmark
5. 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 (...)

Export citation

Bookmark
6. Hehner and Stoddart agree that the halting problem has an inconsistent, unsatisfiable specification. Hehner and Macias agree that a key issue with the halting problem is that it requires a: subjective specification(Hehner) / context dependent function(Macias). When a problem has an unsatisfiable specification because this specification is inconsistent then the unsatisfiability of the specification is anchored in its error thus does not actually limit computation.

Export citation

Bookmark
7. 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.

Export citation

Bookmark
8. A pair of C functions are defined such that D has the halting problem proof's pathological relationship to simulating termination analyzer H. When D correctly simulated by H must be aborted to prevent its own infinite execution then H is necessarily correct to reject D as specifying non-halting behavior. This exact same reasoning is applied to the Peter Linz Turing machine based halting problem proof.

Export citation

Bookmark
9. 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.

Export citation

Bookmark
10. 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.

Export citation

Bookmark
11. A simulating halt decider correctly predicts what the behavior of its input would be if this simulated input never had its simulation aborted. It does this by correctly recognizing several non-halting behavior patterns in a finite number of steps of correct simulation. -/- When simulating halt decider H correctly predicts that directly executed D(D) would remain stuck in recursive simulation (run forever) unless H aborts its simulation of D this directly applies to the halting theorem.

Export citation

Bookmark
12. 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 (...)

Export citation

Bookmark
13. The novel concept of a simulating halt decider enables halt decider H to to correctly determine the halt status of the conventional “impossible” input D that does the opposite of whatever H decides. This works equally well for Turing machines and “C” functions. The algorithm is demonstrated using “C” functions because all of the details can be shown at this high level of abstraction.

Export citation

Bookmark
14. The van Wijngaarden grammars: A syntax primer with decidable restrictions.Luis M. Augusto - 2023 - Journal of Knowledge Structures and Systems 4 (2):1-39.
Expressiveness and decidability are two core aspects of programming languages that should be thoroughly known by those who use them; this includes knowledge of their metalanguages a.k.a. formal grammars. The van Wijngaarden grammars (WGs) are capable of generating all the languages in the Chomsky hierarchy and beyond; this makes them a relevant tool in the design of (more) expressive programming languages. But this expressiveness comes at a very high cost: The syntax of WGs is extremely complex and the decision problem (...)

Export citation

Bookmark
15. Effective Procedures.Nathan Salmon - 2023 - Philosophies 8 (2):27.
This is a non-technical version of "The Decision Problem for Effective Procedures." The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an (...)

Export citation

Bookmark
16. The Decision Problem for Effective Procedures.Nathan Salmón - 2023 - Logica Universalis 17 (2):161-174.
The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined even if it is not sufficiently formal and precise to belong to mathematics proper (in a narrow sense)—and even if (as many have asserted) for that reason the Church–Turing thesis is unprovable. It is proved logically that the class of effective procedures is not decidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. This (...)

Export citation

Bookmark   1 citation
17. An interview by Alex Thomson of UKColumn on Landgrebe and Smith's book: Why Machines Will Never Rule the World. The subtitle of the book is Artificial Intelligence Without Fear, and the interview begins with the question of the supposedly imminent takeover of one profession or the other by artificial intelligence. Is there truly reason to be afraid that you will lose your job? The interview itself is titled 'Where this is no will there is no way', drawing on one thesis (...)

Export citation

Bookmark
18. 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. (...)

Export citation

Bookmark
19. 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 (...)

Export citation

Bookmark   4 citations
20. 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 (...)

Export citation

Bookmark
21. 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 (...)

Export citation

Bookmark
22. 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 (...)

Export citation

Bookmark
23. 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. (...)

Export citation

Bookmark
24. 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 (...)

Export citation

Bookmark
25. 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 (...)

Export citation

Bookmark   33 citations
26. 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.

Export citation

Bookmark
27. The Development of Ideas on Computable Intelligence.Yinsheng Zhang - 2017 - Journal of Human Cognition 1 (1):97-108.
This paper sums up the fundamental features of intelligence through the common features stated by various definitions of "intelligence": Intelligence is the ability of achieving systematic goals (functions) of brain and nerve system through selecting, and artificial intelligence or machine intelligence is an imitation of life intelligence or a replication of features and functions. Based on the definition mentioned above, this paper discusses and summarizes the development routes of ideas on computable intelligence, including Godel's "universal recursive function", the computation activities (...)

Export citation

Bookmark
28. 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) (...)

Export citation

Bookmark   4 citations
29. 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 (...)

Export citation

Bookmark   1 citation
30. 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. (...)

Export citation

Bookmark
31. 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.

Export citation

Bookmark   13 citations
32. A paradox related to the Turing Test.Samuel Alexander - 2011 - The Reasoner 5 (6):90-90.

Export citation

Bookmark
33. 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 (...)

Export citation

Bookmark   2 citations
34. 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 (...)

Export citation

Bookmark   3 citations
35. 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 (...)

Export citation

Bookmark   5 citations
36. 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 (...)

Export citation

Bookmark   4 citations
37. Formulas for Computable and Non-Computable Functions.Samuel Alexander - 2006 - Rose-Hulman Undergraduate Mathematics Journal 7 (2).

Export citation

Bookmark
38. 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 (...)

Export citation

Bookmark
39. 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. (...)

Export citation

Bookmark   3 citations
40. 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.

Export citation

Bookmark
41. 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.

Export citation

Bookmark   4 citations
42. 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.

Export citation

Bookmark
43. 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?

Export citation

Bookmark   5 citations
44. Recursive predicates and quantifiers.S. C. Kleene - 1943 - Transactions of the American Mathematical Society 53:41-73.

Export citation

Bookmark   34 citations
45. در تکوین نظریه محاسبات از اوایل قرن بیستم پارادکسها و خود ارجاعی نقش ویژه ای را بازی کرده اند. هر چند نظریه محاسبات عام بر اساس تعریف ماشین تورینگ، فرض تورینگ_چرچ و کاربردهای آن بنا شده ،اما از همان ابتدا تا به امروز منطق و حوزه های مختلف این علم در ارتباط تنگاتنگ با این تیوری و در ابتدا نظریه محاسبات خاص بوده و این ارتباط روز به روز گسترده و گسترده تر گشته است. از تاثیر پارادوکس دروغگو و پارادکس (...)

Export citation

Bookmark
46. 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 (...)