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

423 found
Order:
1 — 50 / 423
  1. added 2020-05-19
    Pincherle's Theorem in Reverse Mathematics and Computability Theory.Dag Normann & Sam Sanders - 2020 - Annals of Pure and Applied Logic 171 (5):102788.
    We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first ‘local-to-global’ principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms are necessary to (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2. added 2020-05-12
    A Minimal Pair in the Generic Degrees.Denis R. Hirschfeldt - 2020 - Journal of Symbolic Logic 85 (1):531-537.
    We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa’s result that there are no minimal pairs for relative generic computability and answers a basic structural question mentioned in several papers in the area.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3. added 2020-04-10
    Statements That Concern Computable Sets X⊆N and Cannot Be Formalized in ZFC Because They Refer to the Currently Known/Unknown Theorems About X.Apoloniusz Tyszka & Sławomir Kurpaska - manuscript
    Conditions (1)-(8) below concern sets X⊆N . (1) There are a large number of elements of X and it is conjectured that X is infinite. (2) No known algorithm decides the finiteness of X. (3) A known algorithm for every n∈N decides whether or not n∈X. (4) An explicitly known integer n satisfies: card(X)<ω ⇒ X⊆(-∞,n]. (5) X is widely known in number theory. (6) There is no known equality X = X_1 ∪ X_2, where X_1 and X_2 are defined (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  4. added 2019-12-21
    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   Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  5. added 2019-11-08
    Recursive Baire Classification and Speedable Functions.Cristian Calude, Gabriel Istrate & Marius Zimand - 1992 - Mathematical Logic Quarterly 38 (1):169-178.
  6. added 2019-09-15
    Weaker variants of infinite time Turing machines.Matteo Bianchetti - 2020 - Archive for Mathematical Logic 59 (3):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 (3 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  7. added 2019-09-11
    Fuzzy Time, From Paradox to Paradox.Farzad Didehvar - manuscript
    Although Fuzzy logic and Fuzzy Mathematics is a widespread subject and there is a vast literature about it, yet the use of Fuzzy issues like Fuzzy sets and Fuzzy numbers was relatively rare in time concept. This could be seen in the Fuzzy time series. In addition, some attempts are done in fuzzing Turing Machines but seemingly there is no need to fuzzy time. Throughout this article, we try to change this picture and show why it is helpful to consider (...)
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  8. added 2019-06-06
    Copeland and Proudfoot on Computability.Michael Rescorla - 2012 - Studies in History and Philosophy of Science Part A 43 (1):199-202.
    Many philosophers contend that Turing’s work provides a conceptual analysis of numerical computability. In (Rescorla, 2007), I dissented. I argued that the problem of deviant notations stymies existing attempts at conceptual analysis. Copeland and Proudfoot respond to my critique. I argue that their putative solution does not succeed. We are still awaiting a genuine conceptual analysis.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  9. added 2019-06-06
    Infinitism, Completability, and Computability: Reply to Peijnenburg: Discussions.Jeremy Gwiazda - 2010 - Mind 119 (476):1123-1124.
    In ‘Infinitism Regained’, Jeanne Peijnenburg argues for a version of infinitism wherein ‘beliefs may be justified by an infinite chain of reasons that can be actually completed’. I argue that Peijnenburg has not successfully argued for this claim, but rather has shown that certain infinite series can be computed.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10. added 2019-06-06
    Conceptualismo realista y computabilidad.Max A. Freund - 2005 - Critica 37 (111):3-38.
    El artículo formula una interpretación de la computabilidad desde la perspectiva del conceptualismo realista. En esta interpretación, la noción central es la de concepto computable, el cual se entiende como cierto tipo de capacidad cognitiva. Aquí se muestra cómo difiere esa interpretación conceptualista de la clásica, denominada teoría de la computabilidad efectiva, en la cual el concepto fundamental es el de algoritmo; también se discute la relación entre estas dos interpretaciones. La discusión explora las consecuencias de la idea de que (...)
    Remove from this list   Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  11. added 2019-06-06
    Computability Over the Partial Continuous Functionals.Dag Normann - 2000 - Journal of Symbolic Logic 65 (3):1133-1142.
    We show that to every recursive total continuous functional $\Phi$ there is a PCF-definable representative $\Psi$ of $\Phi$ in the hierarchy of partial continuous functionals, where PCF is Plotkin's programming language for computable functionals. PCF-definable is equivalent to Kleene's S1-S9-computable over the partial continuous functionals.
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12. added 2019-06-06
    Some Reflections on the Foundations of Ordinary Recursion Theory and a New Proposal.George Tourlakis - 1986 - Mathematical Logic Quarterly 32 (31-34):503-515.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13. added 2019-06-06
    Comparing Hierarchies of Primitive Recursive Sequence Functions.E. Fachini & A. Maggiolo-Schettini - 1982 - Mathematical Logic Quarterly 28 (27-32):431-445.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14. added 2019-06-06
    The Continuous Functionals; Computations, Recursions and Degrees.Dag Normann - 1981 - Annals of Pure and Applied Logic 21 (1):1.
  15. added 2019-06-06
    Recursively Invariant Beta-Recursion Theory.Wolfgand Maass - 1981 - Annals of Mathematical Logic 21 (1):27.
  16. added 2019-06-06
    Recursion Theory on Algebraic Structures with Independent Sets.J. B. Remmel - 1980 - Annals of Pure and Applied Logic 18 (2):153.
  17. added 2019-06-06
    Two Splitting Theorems for Beta-Recursion Theory.Steven Homer - 1980 - Annals of Pure and Applied Logic 18 (2):137.
  18. added 2019-06-06
    Degrees of Functionals.Dag Normann - 1979 - Annals of Pure and Applied Logic 16 (3):269.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  19. added 2019-06-06
    N-Ary Almost Recursive Functions.John W. Berry - 1974 - Mathematical Logic Quarterly 20 (34-36):551-559.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20. added 2019-06-06
    Minimal Degrees in Generalized Recursion Theory.Michael Machtey - 1974 - Mathematical Logic Quarterly 20 (8-12):133-148.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21. added 2019-06-06
    On Suborderings of Degrees of Recursive Unsolvability.Gerald E. Sacks - 1961 - Mathematical Logic Quarterly 7 (1-5):46-56.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  22. added 2019-04-15
    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 (...)
    No categories
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  23. added 2019-04-14
    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   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  24. added 2019-02-24
    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   Direct download  
     
    Export citation  
     
    Bookmark  
  25. added 2018-11-26
    Defining a Halting Decidability Decider.Pete Olcott - manuscript
    In this paper we show how to define a halting decidability decider that rejects all finite string Turing machine descriptions that would otherwise make halting undecidable. All of the conventional halting problem proof counter-examples would be rejected on the basis that they specify an infinitely recursive evaluation sequence thus are malformed expressions of the language of Turing Machine descriptions.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    Bookmark  
  26. added 2018-08-18
    On the Question of Whether the Mind Can Be Mechanized, I: From Gödel to Penrose.Peter Koellner - 2018 - Journal of Philosophy 115 (7):337-360.
    In this paper I address the question of whether the incompleteness theorems imply that “the mind cannot be mechanized,” where this is understood in the specific sense that “the mathematical outputs of the idealized human mind do not coincide with the mathematical outputs of any idealized finite machine.” Gödel argued that his incompleteness theorems implied a weaker, disjunctive conclusion to the effect that either “the mind cannot be mechanized” or “mathematical truth outstrips the idealized human mind.” Others, most notably, Lucas (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  27. added 2018-05-30
    Solovay's Theorem Cannot Be Simplified.Andrew Arana - 2001 - Annals of Pure and Applied Logic 112 (1):27-41.
    In this paper we consider three potential simplifications to a result of Solovay’s concerning the Turing degrees of nonstandard models of arbitrary completions of first-order Peano Arithmetic (PA). Solovay characterized the degrees of nonstandard models of completions T of PA, showing that they are the degrees of sets X such that there is an enumeration R ≤T X of an “appropriate” Scott set and there is a family of functions (tn)n∈ω, ∆0 n(X) uniformly in n, such that lim tn(s) s→∞.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  28. added 2018-02-26
    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   Direct download  
     
    Export citation  
     
    Bookmark  
  29. added 2018-02-20
    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   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30. added 2017-08-31
    Deviant Encodings and Turing’s Analysis of Computability.B. Jack Copeland & Diane Proudfoot - 2010 - Studies in History and Philosophy of Science Part A 41 (3):247-252.
    Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  31. added 2017-07-30
    Intractability and the Use of Heuristics in Psychological Explanations.Iris Rooij, Cory Wright & Todd Wareham - 2012 - Synthese 187 (2):471-487.
  32. added 2017-02-15
    Resolving the Infinitude Controversy.András Kornai - 2014 - Journal of Logic, Language and Information 23 (4):481-492.
    A simple inductive argument shows natural languages to have infinitly many sentences, but workers in the field have uncovered clear evidence of a diverse group of ‘exceptional’ languages from Proto-Uralic to Dyirbal and most recently, Pirahã, that appear to lack recursive devices entirely. We argue that in an information-theoretic setting non-recursive natural languages appear neither exceptional nor functionally inferior to the recursive majority.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  33. added 2017-02-14
    Expression de la Recursion Primitive Dans le Calcul-XK.J. Ladriere - forthcoming - Logique Et Analyse.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    Bookmark  
  34. added 2017-02-14
    The Impact of Starting Small on the Learnability of Recursion.Jun Lai & Fenna H. Poletiek - 2010 - In S. Ohlsson & R. Catrambone (eds.), Proceedings of the 32nd Annual Conference of the Cognitive Science Society. Cognitive Science Society.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  35. added 2017-02-14
    The Contribution of Polish Logicians to Recursion Theory.Roman Murawski - 1998 - In Katarzyna Kijania-Placek & Jan Woleński (eds.), The Lvov-Warsaw School and Contemporary Philosophy. Kluwer Academic Publishers. pp. 265--282.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  36. added 2017-02-14
    SEarch Via Recursive Rejection (SERR).H. J. Müller, G. W. Humphreys & A. C. Olson - 1998 - In Richard D. Wright (ed.), Visual Attention. Oxford University Press. pp. 8--389.
    Remove from this list  
     
    Export citation  
     
    Bookmark   1 citation  
  37. added 2017-02-13
    Geeks and Recursive Publics.Christopher Kelty - 2012 - In Christian Emden & David R. Midgley (eds.), Beyond Habermas: Democracy, Knowledge, and the Public Sphere. Berghahn Books. pp. 99.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  38. added 2017-02-13
    How Much Randomness is Needed for Statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2012 - In S. Barry Cooper (ed.), Annals of Pure and Applied Logic. pp. 395--404.
    In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle . The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ . While the Hippocratic approach is in general much more restrictive, there are cases where the (...)
    Remove from this list   Direct download (12 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  39. added 2017-02-13
    Construction Theory, Self-Replication, and the Halting Problem.Hiroki Sayama - 2008 - Complexity 13 (5):16-22.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  40. added 2017-02-13
    Computability and Computational Complexity.Patrick Doyle - 2003 - In L. Nadel (ed.), Encyclopedia of Cognitive Science. Nature Publishing Group.
  41. added 2017-02-13
    Managing Complexity by Recursion.Bernd Schiemenz - 2002 - In Robert Trappl (ed.), Cybernetics and Systems. Austrian Society for Cybernetics Studies. pp. 475--479.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  42. added 2017-02-13
    Filter Spaces and Continuous Functionals.J. M. E. Hyland - 1979 - Annals of Mathematical Logic 16 (2):101-143.
  43. added 2017-02-13
    Quelques Procedes de Definition En Topologffi Recursive.Daniel Lacombe - 1959 - In A. Heyting (ed.), Constructivity in Mathematics. Amsterdam: North-Holland Pub. Co.. pp. 24--129.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  44. added 2017-02-13
    Quelques Procédés de Définition En Topologie Récursive.Daniel Lacombe - 1959 - In A. Heyting (ed.), Journal of Symbolic Logic. Amsterdam: North-Holland Pub. Co.. pp. 129--158.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  45. added 2017-02-12
    Algorithmic Randomness and Measures of Complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  46. added 2017-02-12
    Truth-Table Schnorr Randomness and Truth-Table Reducible Randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
    Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  47. added 2017-02-12
    Higher Kurtz Randomness.Bjørn Kjos-Hanssen, André Nies, Frank Stephan & Liang Yu - 2010 - Annals of Pure and Applied Logic 161 (10):1280-1290.
    A real x is -Kurtz random if it is in no closed null set . We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  48. added 2017-02-12
    Constructive Equivalence Relations on Computable Probability Measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
    A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  49. added 2017-02-12
    Ordinal Machines and Admissible Recursion Theory.Peter Koepke & Benjamin Seyfferth - 2009 - Annals of Pure and Applied Logic 160 (3):310-318.
    We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  50. added 2017-02-12
    Connectivity Properties of Dimension Level Sets.Jack H. Lutz & Klaus Weihrauch - 2008 - Mathematical Logic Quarterly 54 (5):483-491.
    This paper initiates the study of sets in Euclidean spaces ℝn that are defined in terms of the dimensions of their elements. Specifically, given an interval I ⊆ [0, n ], we are interested in the connectivity properties of the set DIMI, consisting of all points in ℝn whose dimensions lie in I, and of its dual DIMIstr, consisting of all points whose strong dimensions lie in I. If I is [0, 1) or.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
1 — 50 / 423