Results for 'Turing reducibility'

958 found
Order:
  1.  26
    Turing reducibility in the fine hierarchy.Alexander G. Melnikov, Victor L. Selivanov & Mars M. Yamaleev - 2020 - Annals of Pure and Applied Logic 171 (7):102766.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2.  21
    (1 other version)Bounds in the Turing reducibility of functions.Karol Habart & K. Habart - 1992 - Mathematical Logic Quarterly 38 (1):423-430.
    A hierarchy of functions with respect to their role as bounds in the Turing reducibility of functions is introduced and studied. This hierarchy leads to a certain notion of incompressibility of sets which is also investigated.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  3. that B is Turing reducible to A and write B≤ T A. We say that B≡ T A if B≤ T A and A≤ T B.≡ T is an equivalence relation, and≤ T induces a par-tial ordering on the corresponding equivalence classes; the poset obtained in this way is called the degrees of unsolvability, and elements of this poset are called degrees. [REVIEW]J. Knight, A. Kucera & R. Shore - 1995 - Bulletin of Symbolic Logic 1 (2).
  4.  22
    A New Reducibility between Turing‐ and wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
    The project was partially supported by a NSF grant of China. The author was grateful to Professor S. Lempp for his encouragement and suggestion while the author was visiting the Department of Mathematics at the University of Wisconsin.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  5.  22
    Post's Problem for Reducibilities of Bounded Complexity.Valeriy K. Bulitko - 2002 - Mathematical Logic Quarterly 48 (3):367-373.
    In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤m, ≤btt, ≤tt and ≤T and solved the problem for al of them except ≤T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub-Turing reducibilities what were (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  6.  34
    Turing computable embeddings.F. Knight Julia, Miller Sara & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.
    In [3], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. While [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  7.  34
    The Logic of Interactive Turing Reduction.Giorgi Japaridze - 2007 - Journal of Symbolic Logic 72 (1):243 - 276.
    The paper gives a soundness and completeness proof for the implicative fragment of intuitionistic calculus with respect to the semantics of computability logic, which understands intuitionistic implication as interactive algorithmic reduction. This concept — more precisely, the associated concept of reducibility — is a generalization of Turing reducibility from the traditional, input/output sorts of problems to computational tasks of arbitrary degrees of interactivity.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  8.  49
    Beyond Turing equivalence.Aaron Sloman - 1996 - In Peter Millican & Andy Clark (eds.), Machines and Thought: The Legacy of Alan Turing. Oxford, England: Oxford University Press. pp. 1--179.
    What is the relation between intelligence and computation? Although the difficulty of defining `intelligence' is widely recognized, many are unaware that it is hard to give a satisfactory definition of `computational' if computation is supposed to provide a non-circular explanation for intelligent abilities. The only well-defined notion of `computation' is what can be generated by a Turing machine or a formally equivalent mechanism. This is not adequate for the key role in explaining the nature of mental processes, because it (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  9.  13
    Turing's Test vs the Moral Turing Test.Diane Proudfoot - 2024 - Philosophy and Technology 37 (4):1-14.
    Given actual autonomous systems with capacities for harm and the public’s apparent willingness to take moral advice from large language models (LLMs), Einar Duenger Bohn’s (2024) renewed discussion of the Moral Turing Test (MTT) is timely. Bohn’s aim is to defend an unequivocally behavioural test. In this paper, I argue against this direction. Interpreted as testing mere behaviour, the Turing test is a poor test of either intelligence or moral agency, and neither Bohn’s version of the test nor (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  10.  71
    Turing oracle machines, online computing, and three displacements in computability theory.Robert I. Soare - 2009 - Annals of Pure and Applied Logic 160 (3):368-399.
    We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  11. Post-Turing Methodology: Breaking the Wall on the Way to Artificial General Intelligence.Albert Efimov - 2020 - Lecture Notes in Computer Science 12177.
    This article offers comprehensive criticism of the Turing test and develops quality criteria for new artificial general intelligence (AGI) assessment tests. It is shown that the prerequisites A. Turing drew upon when reducing personality and human consciousness to “suitable branches of thought” re-flected the engineering level of his time. In fact, the Turing “imitation game” employed only symbolic communication and ignored the physical world. This paper suggests that by restricting thinking ability to symbolic systems alone Turing (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  12.  26
    Embeddings in the Strong Reducibilities Between 1 and npm.Phil Watson - 1997 - Mathematical Logic Quarterly 43 (4):559-568.
    We consider the strongest forms of enumeration reducibility, those that occur between 1- and npm-reducibility inclusive. By defining two new reducibilities which are counterparts to 1- and i-reducibility, respectively, in the same way that nm- and npm-reducibility are counterparts to m- and pm-reducibility, respectively, we bring out the structure of the strong reducibilities. By further restricting n1- and nm-reducibility we are able to define infinite families of reducibilities which isomorphically embed the r. e. (...) degrees. Thus the many well-known results in the theory of the r. e. Turing degrees have counterparts in the theory of strong reducibilities. We are also able to positively answer the question of whether there exist distinct reducibilities ≤y and ≤a between ≤e and ≤m such that there exists a non-trivial ≤y-contiguous ≤z degree. (shrink)
    Direct download  
     
    Export citation  
     
    Bookmark  
  13.  16
    About Segment Complexity of Turing Reductions.Valeriy K. Bulitko - 1999 - Mathematical Logic Quarterly 45 (4):561-571.
  14.  8
    Turing’s Test vs the Moral Turing Test.Diane Proudfoot - 2024 - Philosophy and Technology 37 (4):1-14.
    Given actual autonomous systems with capacities for harm and the public’s apparent willingness to take moral advice from large language models (LLMs), Einar Duenger Bohn’s (2024) renewed discussion of the Moral Turing Test (MTT) is timely. Bohn’s aim is to defend an unequivocally behavioural test. In this paper, I argue against this direction. Interpreted as testing mere behaviour, the Turing test is a poor test of either intelligence or moral agency, and neither Bohn’s version of the test nor (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  46
    Automorphisms in the PTIME-Turing degrees of recursive sets.Christine Ann Haught & Theodore A. Slaman - 1997 - Annals of Pure and Applied Logic 84 (1):139-152.
    We consider questions related to the rigidity of the structure R, the PTIME-Turing degrees of recursive sets of strings together with PTIME-Turing reducibility, pT, and related structures; do these structures have nontrivial automorphisms? We prove that there is a nontrivial automorphism of an ideal of R. This can be rephrased in terms of partial relativizations. We consider the sets which are PTIME-Turing computable from a set A, and call this class PTIMEA. Our result can be stated (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  26
    On subcreative sets and S-reducibility.John T. Gill & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669-677.
    Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  17.  26
    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} (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  18.  41
    Π 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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  19. Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
    A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   20 citations  
  20. (1 other version)Church-Turing Thesis, in Practice.Luca San Mauro - 2018 - In John Baldwin (ed.), Truth, Existence and Explanation. Springer Verlag. pp. 225-248.
    We aim at providing a philosophical analysis of the notion of “proof by Church’s Thesis”, which is – in a nutshell – the conceptual device that permits to rely on informal methods when working in Computability Theory. This notion allows, in most cases, to not specify the background model of computation in which a given algorithm – or a construction – is framed. In pursuing such analysis, we carefully reconstruct the development of this notion (from Post to Rogers, to the (...)
     
    Export citation  
     
    Bookmark  
  21.  37
    On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
    Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  22.  87
    The existential theory of the poset of R.e. Degrees with a predicate for single jump reducibility.Steffen Lempp & Manuel Lerman - 1992 - Journal of Symbolic Logic 57 (3):1120-1130.
    We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  23.  98
    Reflections on gödel's and Gandy's reflections on Turing's thesis.David Israel - 2002 - Minds and Machines 12 (2):181-201.
    We sketch the historical and conceptual context of Turing's analysis of algorithmic or mechanical computation. We then discuss two responses to that analysis, by Gödel and by Gandy, both of which raise, though in very different ways. The possibility of computation procedures that cannot be reduced to the basic procedures into which Turing decomposed computation. Along the way, we touch on some of Cleland's views.
    Direct download (14 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  24.  36
    Computably enumerable sets and quasi-reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
    We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  25.  9
    Minimal weak truth table degrees and computably enumerable Turing degrees.R. G. Downey - 2020 - Providence, RI: American Mathematical Society. Edited by Keng Meng Ng & Reed Solomon.
    Informal construction -- Formal construction -- Limiting results.
    Direct download  
     
    Export citation  
     
    Bookmark  
  26.  65
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  27.  34
    Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities.Y. Wang & W. Merkle - 2001 - Mathematical Logic Quarterly 47 (2):249-270.
    Let ≤r and ≤sbe two binary relations on 2ℕ which are meant as reducibilities. Let both relations be closed under finite variation and consider the uniform distribution on 2ℕ, which is obtained by choosing elements of 2ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤r-cone of a randomly chosen set X, that is, the class of all sets A with A ≤rX, differs from the lower ≤s-cone of X. By c osure (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  28.  64
    Contiguity and Distributivity in the Enumerable Turing Degrees.Rodney G. Downey & Steffen Lempp - 1997 - Journal of Symbolic Logic 62 (4):1215-1240.
    We prove that a enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no $m$-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  29.  16
    A $ \prod _{2}^{0}$ SINGLETON OF MINIMAL ARITHMETIC DEGREE.Peter M. Gerdes - forthcoming - Journal of Symbolic Logic:1-33.
    In the study of the arithmetic degrees the $\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. However, much less is known about the arithmetic degrees and the role of the $\omega \text {-REA}$ sets in that structure than about the Turing degrees. Indeed, even basic questions such as the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree are open. This paper makes (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  41
    Does truth-table of linear norm reduce the one-query tautologies to a random oracle?Masahiro Kumabe, Toshio Suzuki & Takeshi Yamazaki - 2008 - Archive for Mathematical Logic 47 (2):159-180.
    In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  31.  65
    Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
    A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let [Formula: see text] be the lattice of weak degrees of mass problems associated with nonempty [Formula: see text] subsets (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  32.  58
    Elementary differences between the degrees of unsolvability and degrees of compressibility.George Barmpalias - 2010 - Annals of Pure and Applied Logic 161 (7):923-934.
    Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  33. (1 other version)Definability, automorphisms, and dynamic properties of computably enumerable sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
    We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  34.  37
    Propagation of partial randomness.Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama - 2014 - Annals of Pure and Applied Logic 165 (2):742-758.
    Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  35.  71
    Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
    We use some simple facts about the wtt-degrees of r.e. sets together with a construction to answer some questions concerning the join and meet operators in the r.e. degrees. The construction is that of an r.e. Turing degree a with just one wtt-degree in a such that a is the join of a minimal pair of r.e. degrees. We hope to illustrate the usefulness of studying the stronger reducibility orderings of r.e. sets for providing information about Turing (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  36.  43
    A General Form of Relative Recursion.Jaap van Oosten - 2006 - Notre Dame Journal of Formal Logic 47 (3):311-318.
    The purpose of this note is to observe a generalization of the concept "computable in..." to arbitrary partial combinatory algebras. For every partial combinatory algebra (pca) A and every partial endofunction on A, a pca A[f] is constructed such that in A[f], the function f is representable by an element; a universal property of the construction is formulated in terms of Longley's 2-category of pcas and decidable applicative morphisms. It is proved that there is always a geometric inclusion from the (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  37.  31
    Continuity of capping in C bT.Paul Brodhead, Angsheng Li & Weilin Li - 2008 - Annals of Pure and Applied Logic 155 (1):1-15.
    A set Asubset of or equal toω is called computably enumerable , if there is an algorithm to enumerate the elements of it. For sets A,Bsubset of or equal toω, we say that A is bounded Turing reducible to reducible to) B if there is a Turing functional, Φ say, with a computable bound of oracle query bits such that A is computed by Φ equipped with an oracle B, written image. Let image be the structure of the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  38.  16
    Degree Spectra of Homeomorphism Type of Compact Polish Spaces.Mathieu Hoyrup, Takayuki Kihara & Victor Selivanov - forthcoming - Journal of Symbolic Logic:1-32.
    A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $\mathbf {0}'$ -computable low $_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$, there exists a Polish space $X_n$ such that exactly the high $_{n}$ -degrees are required to present the homeomorphism type of $X_n$. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  39.  35
    Complexity of equivalence relations and preorders from computability theory.Egor Ianovski, Russell Miller, Keng Meng Ng & André Nies - 2014 - Journal of Symbolic Logic 79 (3):859-881.
    We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem- (...) on exponential time sets, which is${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is${\rm{\Sigma }}_4^0$. (shrink)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  40.  51
    Almost everywhere domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
    A Turing degree a is said to be almost everywhere dominating if, for almost all $X \in 2^{\omega}$ with respect to the "fair coin" probability measure on $2^{\omega}$ , and for all g: $\omega \rightarrow \omega$ Turing reducible to X, there exists f: $\omega \rightarrow \omega$ of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  41.  2
    Many problems, different frameworks: classification of problems in computable analysis and algorithmic learning theory.Vittorio Cipriani - 2024 - Bulletin of Symbolic Logic 30 (2):287-288.
    In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.After giving the necessary preliminaries, we first study the uniform computational strength of the Cantor–Bendixson theorem in (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42.  34
    Finding the limit of incompleteness I.Yong Cheng - 2020 - Bulletin of Symbolic Logic 26 (3-4):268-286.
    In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem. We first define the notion “$\textsf {G1}$ holds for the theory $T$”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $\textsf {G1}$ holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s $\mathbf {R}$ interprets T but T does not interpret $\mathbf {R}$ and $\textsf (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  43.  60
    Maximal pairs of c.e. reals in the computably Lipschitz degrees.Yun Fan & Liang Yu - 2011 - Annals of Pure and Applied Logic 162 (5):357-366.
    Computably Lipschitz reducibility , was suggested as a measure of relative randomness. We say α≤clβ if α is Turing reducible to β with oracle use on x bounded by x+c. In this paper, we prove that for any non-computable real, there exists a c.e. real so that no c.e. real can cl-compute both of them. So every non-computable c.e. real is the half of a cl-maximal pair of c.e. reals.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  44.  98
    Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
    A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  45.  30
    Bounded low and high sets.Bernard A. Anderson, Barbara F. Csima & Karen M. Lange - 2017 - Archive for Mathematical Logic 56 (5-6):507-521.
    Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  46.  31
    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 (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  47.  42
    Continuous higher randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
    We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Löf randomness. We also characterize computing higher [Formula: see text]-trivial sets (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  48.  20
    Degrees of randomized computability.Rupert Hölzl & Christopher P. Porter - 2022 - Bulletin of Symbolic Logic 28 (1):27-70.
    In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  49.  46
    On the convergence of query-bounded computations and logical closure properties of C.e. Sets.Timothy Mcnicholl - 2001 - Journal of Symbolic Logic 66 (4):1543-1560.
    Call a set A n-correctable if every set Turing reducible to A via a Turing machine that on any input makes at most n queries is Turing reducible to A via a Turing machine that on any input makes at most n-queries and on any input halts no matter what answers are given to its queries. We show that if a c.e. set A is n-correctable for some n ≥ 2, then it is n-correctable for all (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  50.  99
    On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
    Let P 0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P 0 whose domain we suppose to be the standard integers. Let T be a recursively enumerable extension of Peano arithmetic all of whose existential consequences are satisfied in the standard model. Then there is an initial segment M ' of M which is a model of T such that the complete diagram of M ' (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   11 citations  
1 — 50 / 958