Switch to: References

Citations of:

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers

Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co. (1989)

Add citations

You must login to add citations.
  1. The Physical Impossibility of Machine Computations on Sufficiently Large Integers Inspires an Open Problem That Concerns Abstract Computable Sets X⊆N and Cannot Be Formalized in ZFC as It Refers to Our Current Knowledge on X.Apoloniusz Tyszka & Sławomir Kurpaska - manuscript
    Edmund Landau's conjecture states that the set P(n^2+1) of primes of the form n^2+1 is infinite. Let β=(((24!)!)!)!, and let Φ denote the implication: card(P(n^2+1))<ω ⇒ P(n^2+1)⊆(-∞,β]. We heuristically justify the statement Φ without invoking Landau's conjecture. Open problem: Is there a set X⊆N that satisfies conditions (1)--(5)? (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/infiniteness of X . (3) There is a known (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Low Upper Bounds of Ideals.Antonín Kučera & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (2):517-534.
    We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • The Strength of the Grätzer-Schmidt Theorem.Katie Brodhead, Mushfeq Khan, Bjørn Kjos-Hanssen, William A. Lampe, Paul Kim Long V. Nguyen & Richard A. Shore - 2016 - Archive for Mathematical Logic 55 (5-6):687-704.
    The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show thatthe set of indices of computable lattices that are complete is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^1_1$$\end{document}-complete;the set of indices of computable lattices that are algebraic is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^1_1$$\end{document}-complete;the set of compact elements of a computable (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Logicism as Making Arithmetic Explicit.Vojtěch Kolman - 2015 - Erkenntnis 80 (3):487-503.
    This paper aims to shed light on the broader significance of Frege’s logicism against the background of discussing and comparing Wittgenstein’s ‘showing/saying’-distinction with Brandom’s idiom of logic as the enterprise of making the implicit rules of our linguistic practices explicit. The main thesis of this paper is that the problem of Frege’s logicism lies deeper than in its inconsistency : it lies in the basic idea that in arithmetic one can, and should, express everything that is implicitly presupposed so that (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Degrees Bounding Principles and Universal Instances in Reverse Mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability.Richard A. Shore - 1997 - Archive for Mathematical Logic 36 (4-5):233-253.
    . We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • On Interpreting Chaitin's Incompleteness Theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
    The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be good measure of (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Algorithmic Information Theory and Undecidability.Panu Raatikainen - 2000 - Synthese 123 (2):217-225.
    Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • 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. (...)
    Download  
     
    Export citation  
     
    Bookmark   17 citations  
  • Laskettavuuden teorian varhaishistoria.Panu Raatikainen - 1995 - In Älyn oppihistoria – matka logiikan, psykologian ja tekoälyn juurille. Espoo: Finnish Artificial Intelligence Society.
    Nykyaikaisen logiikan keskeisenä tutkimuskohteena ovat erilaiset formalisoidut teoriat. Erityisesti vuosisadan vaihteen aikoihin matematiikan perusteiden tutkimuksessa ilmaantuneiden hämmentävien paradoksien (Russell 1902, 1903) jälkeen (ks. kuitenkin jo Frege 1879, Dedekind 1888, Peano 1889; vrt. Wang 1957) keskeiset matemaattiset teoriat on pyritty tällaisten vaikeuksien välttämiseksi uudelleen muotoilemaan täsmällisesti keinotekoisessa symbolikielessä, jonka lauseenmuodostussäännöt on täsmällisesti ja yksikäsitteisesti määrätty. Edelleen teoriat on pyritty aksiomatisoimaan, ts. on pyritty antamaan joukko peruslauseita, joista kaikki muut - tai ainakin mahdollisimman monet - teorian todet lauseet voidaan loogisesti johtaa tarkoin (...)
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Learning Via Queries and Oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
    Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a non-recursive oracle. This paper combines these two types — it considers three basic models of queries to a teacher (QEX[Succ], QEX[ The results for each of these three models of query-inference are the same: If an oracle is omniscient for query-inference then it is already omniscient for EX. There is an oracle of trivial EX-degree, which allows nontrivial query-inference. Furthermore, (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Matematika a Skúsenosť.Ladislav Kvasz - 2009 - Organon F: Medzinárodný Časopis Pre Analytickú Filozofiu 16 (2):146-182.
    Mathematics is traditionally considered being an apriori discipline consisting of purely analytic propositions. The aim of the present paper is to offer arguments against this entrenched view and to draw attention to the experiential dimension of mathematical knowledge. Following Husserl’s interpretation of physical knowledge as knowledge constituted by the use of instruments, I am trying to interpret mathematical knowledge also as acknowledge based on instrumental experience. This interpretation opens a new view on the role of the logicist program, both in (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
    The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
    We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • The Diagonal Method and Hypercomputation.Toby Ord & Tien D. Kieu - 2005 - British Journal for the Philosophy of Science 56 (1):147-156.
    The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Hypersimplicity and Semicomputability in the Weak Truth Table Degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
    We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize them as the c.e. (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Proving Church's Thesis.Robert Black - 2000 - Philosophia Mathematica 8 (3):244--58.
    Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Badness and Jump Inversion in the Enumeration Degrees.Charles M. Harris - 2012 - Archive for Mathematical Logic 51 (3-4):373-406.
    This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a ${\Pi^{0}_{2}}$ set A whose enumeration degree a is bad—i.e. such that no set ${X \in a}$ is good approximable—and whose complement ${\overline{A}}$ has lowest possible jump, in other words is low2. This also ensures that the degrees y ≤ a only contain ${\Delta^{0}_{3}}$ sets and thus yields a tight lower bound for the complexity of both (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Polynomial Clone Reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
    Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and ${\fancyscript{C}_{1} (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Natural Factors of the Medvedev Lattice Capturing IPC.Rutger Kuyper - 2014 - Archive for Mathematical Logic 53 (7-8):865-879.
    Skvortsova showed that there is a factor of the Medvedev lattice which captures intuitionistic propositional logic. However, her factor is unnatural in the sense that it is constructed in an ad hoc manner. We present a more natural example of such a factor. We also show that the theory of every non-trivial factor of the Medvedev lattice is contained in Jankov’s logic, the deductive closure of IPC plus the weak law of the excluded middle ¬p∨¬¬p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Arithmetical Measure.Sebastiaan A. Terwijn & Leen Torenvliet - 1998 - Mathematical Logic Quarterly 44 (2):277-286.
    We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of measure 0 set as considered before by Martin-Löf, Schnorr, and others. We prove that the class of sets constructible by r.e.-constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [10], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursion-theoretic reducibilities below K. We note that (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Continuum, Name and Paradox.Vojtěch Kolman - 2010 - Synthese 175 (3):351 - 367.
    The article deals with Cantor's argument for the non-denumerability of reals somewhat in the spirit of Lakatos' logic of mathematical discovery. At the outset Cantor's proof is compared with some other famous proofs such as Dedekind's recursion theorem, showing that rather than usual proofs they are resolutions to do things differently. Based on this I argue that there are "ontologically" safer ways of developing the diagonal argument into a full-fledged theory of continuum, concluding eventually that famous semantic paradoxes based on (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Diagonalization in Double Frames.Andrzej Wiśniewski & Jerzy Pogonowski - 2010 - Logica Universalis 4 (1):31-39.
    We consider structures of the form, where Φ and Ψ are non-empty sets and is a relation whose domain is Ψ. In particular, by using a special kind of a diagonal argument, we prove that if Φ is a denumerable recursive set, Ψ is a denumerable r.e. set, and R is an r.e. relation, then there exists an infinite family of infinite recursive subsets of Φ which are not R -images of elements of Ψ. The proof is a very elementary (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • First-Order Logic in the Medvedev Lattice.Rutger Kuyper - 2015 - Studia Logica 103 (6):1185-1224.
    Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to first-order logic, using the notion of a first-order hyperdoctrine from categorical logic, to a structure which we will call the hyperdoctrine (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Natural Factors of the Muchnik Lattice Capturing IPC.Rutger Kuyper - 2013 - Annals of Pure and Applied Logic 164 (10):1025-1036.
    We give natural examples of factors of the Muchnik lattice which capture intuitionistic propositional logic , arising from the concepts of lowness, 1-genericity, hyperimmune-freeness and computable traceability. This provides a purely computational semantics for IPC.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
    We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Effective Choice and Boundedness Principles in Computable Analysis.Vasco Brattka & Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (1):73-117.
    In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice (...)
    Download  
     
    Export citation  
     
    Bookmark   14 citations  
  • Π 1 0 Classes, L R Degrees and Turing Degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
    We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • Alonzo Church:His Life, His Work and Some of His Miracles.Maía Manzano - 1997 - History and Philosophy of Logic 18 (4):211-232.
    This paper is dedicated to Alonzo Church, who died in August 1995 after a long life devoted to logic. To Church we owe lambda calculus, the thesis bearing his name and the solution to the Entscheidungsproblem.His well-known book Introduction to Mathematical LogicI, defined the subject matter of mathematical logic, the approach to be taken and the basic topics addressed. Church was the creator of the Journal of Symbolic Logicthe best-known journal of the area, which he edited for several decades This (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Emil Post.Alasdair Urquhart - 2009 - In Dov Gabbay (ed.), The Handbook of the History of Logic. Elsevier. pp. 5--617.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Weihrauch Degrees, Omniscience Principles and Weak Computability.Vasco Brattka & Guido Gherardi - 2011 - Journal of Symbolic Logic 76 (1):143 - 176.
    In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...)
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • Some Structural Properties of Quasi-Degrees.Roland Sh Omanadze - 2018 - Logic Journal of the IGPL 26 (1):191-201.
    Download  
     
    Export citation  
     
    Bookmark  
  • The Isomorphism Problem for Ω-Automatic Trees.Dietrich Kuske, Jiamou Liu & Markus Lohrey - 2013 - Annals of Pure and Applied Logic 164 (1):30-48.
    The main result of this paper states that the isomorphism problem for ω-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies showing that the isomorphism problem for ω-automatic structures is not in . Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Universality of Functional Systems and Totality of Their Elements – the Limits of Conflict and Mutual Influence.Jerzy Mycka - 2017 - Philosophical Problems in Science 63:31-58.
    The article presents several examples of different mathematical structures and interprets their properties related to the existence of universal functions. In this context, relations between the problem of totality of elements and possible forms of universal functions are analyzed. Furthermore, some global and local aspects of the mentioned functional systems are distinguished and compared. In addition, the paper attempts to link universality and totality with the dynamic and static properties of mathematical objects and to consider the problem of limitations in (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Myhill's Work in Recursion Theory.J. C. E. Dekker & E. Ellentuck - 1992 - Annals of Pure and Applied Logic 56 (1-3):43-71.
    In this paper we discuss the following contributions to recursion theory made by John Myhill: two sets are recursively isomorphic iff they are one-one equivalent; two sets are recursively isomorphic iff they are recursively equivalent and their complements are also recursively equivalent; every two creative sets are recursively isomorphic; the recursive analogue of the Cantor–Bernstein theorem; the notion of a combinatorial function and its use in the theory of recursive equivalence types.
    Download  
     
    Export citation  
     
    Bookmark  
  • Equational Theories for Inductive Types.Ralph Loader - 1997 - Annals of Pure and Applied Logic 84 (2):175-217.
    This paper provides characterisations of the equational theory of the PER model of a typed lambda calculus with inductive types. The characterisation may be cast as a full abstraction result; in other words, we show that the equations between terms valid in this model coincides with a certain syntactically defined equivalence relation. Along the way we give other characterisations of this equivalence; from below, from above, and from a domain model, a version of the Kreisel-Lacombe-Shoenfield theorem allows us to transfer (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Bounded Immunity and Btt‐Reductions.Stephen Fenner & Marcus Schaefer - 1999 - Mathematical Logic Quarterly 45 (1):3-21.
    We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that θ does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - Mathematical Logic Quarterly 40 (2):224-236.
    The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...)
    Download  
     
    Export citation  
     
    Bookmark   10 citations  
  • Exact Pairs for Abstract Bounded Reducibilities.Wolfgang Merkle - 1999 - Mathematical Logic Quarterly 45 (3):343-360.
    In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤r between subsets of the natural numbers, where ≤r is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Degree Spectra of the Successor Relation of Computable Linear Orderings.Jennifer Chubb, Andrey Frolov & Valentina Harizanov - 2009 - Archive for Mathematical Logic 48 (1):7-13.
    We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • A Semantical Proof of De Jongh's Theorem.Jaap van Oosten - 1991 - Archive for Mathematical Logic 31 (2):105-114.
    In 1969, De Jongh proved the “maximality” of a fragment of intuitionistic predicate calculus forHA. Leivant strengthened the theorem in 1975, using proof-theoretical tools (normalisation of infinitary sequent calculi). By a refinement of De Jongh's original method (using Beth models instead of Kripke models and sheafs of partial combinatory algebras), a semantical proof is given of a result that is almost as good as Leivant's. Furthermore, it is shown thatHA can be extended to Higher Order Heyting Arithmetic+all trueΠ 2 0 (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • The Partial Orderings of the Computably Enumerable ibT-Degrees and Cl-Degrees Are Not Elementarily Equivalent.Klaus Ambos-Spies, Philipp Bodewig, Yun Fan & Thorsten Kräling - 2013 - Annals of Pure and Applied Logic 164 (5):577-588.
    We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1-shift a+1a+1 of a where a+1 (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Complete, Recursively Enumerable Relations in Arithmetic.Giovanna D'Agostino & Mario Magnago - 1995 - Mathematical Logic Quarterly 41 (1):65-72.
    Using only propositional connectives and the provability predicate of a Σ1-sound theory T containing Peano Arithmetic we define recursively enumerable relations that are complete for specific natural classes of relations, as the class of all r. e. relations, and the class of all strict partial orders. We apply these results to give representations of these classes in T by means of formulas.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Noncomputability, Unpredictability, and Financial Markets.Daniel S. Graça - 2012 - Complexity 17 (6):24-30.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Some Hierarchies of Primitive Recursive Functions on Term Algebras.Klaus-Hilmar Sprenger - 1997 - Mathematical Logic Quarterly 43 (2):251-286.
    Download  
     
    Export citation  
     
    Bookmark  
  • Effective Nonrecursiveness.Takeshi Yamaguchi - 1997 - Mathematical Logic Quarterly 43 (1):45-48.
    Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1].
    Download  
     
    Export citation  
     
    Bookmark  
  • Herbrand Semantics, the Potential Infinite, and Ontology-Free Logic.Theodore Hailperin - 1992 - History and Philosophy of Logic 13 (1):69-90.
    This paper investigates the ontological presuppositions of quantifier logic. It is seen that the actual infinite, although present in the usual completeness proofs, is not needed for a proper semantic foundation. Additionally, quantifier logic can be given an adequate formulation in which neither the notion of individual nor that of a predicate appears.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Goodness in the Enumeration and Singleton Degrees.Charles M. Harris - 2010 - Archive for Mathematical Logic 49 (6):673-691.
    We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}$ and singleton ${({\mathcal D}_{\rm s})}$ degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings ${\iota_s}$ and ${\hat{\iota}_s}$ of, respectively, ${{\mathcal D}_{\rm e}}$ and ${{\mathcal D}_{\rm T}}$ (the Turing degrees) into (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • On the Difficulty of Writing Out Formal Proofs in Arithmetic.Ryo Kashima & Takeshi Yamaguchi - 1997 - Mathematical Logic Quarterly 43 (3):328-332.
    Let ℸ be the set of Gödel numbers Gn of function symbols f such that PRA ⊢ and let γ be the function such that equation imageWe prove: The r. e. set ℸ is m-complete; the function γ is not primitive recursive in any class of functions {f1, f2, ⃛} so long as each fi has a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is recursive in ℸ.
    Download  
     
    Export citation  
     
    Bookmark