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

485 found
Order:
1 — 50 / 485
  1. A Contradiction and P=NP Problem.Farzad Didehvar - manuscript
    Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  2. 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  
  3. 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 (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4. Halting Problem Undecidability and Infinitely Nested Simulation (V3).P. Olcott - manuscript
    By making a slight refinement to the halt status criterion measure that remains consistent with the original a halt decider may be defined that correctly determines the halt status of the conventional halting problem proof counter-examples. This refinement overcomes the pathological self-reference issue that previously prevented halting decidability.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  5. Halting Problem Undecidability and Infinitely Nested Simulation (V4).P. Olcott - manuscript
    A Simulating Halt Decider (SHD) computes the mapping from its input to its own accept or reject state based on whether or not the input simulated by a UTM would reach its final state in a finite number of simulated steps. -/- A halt decider (because it is a decider) must report on the behavior specified by its finite string input. This is its actual behavior when it is simulated by the UTM contained within its simulating halt decider while this (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  6. Halting Problem Undecidability and Infinitely Nested Simulation (V5).P. Olcott - manuscript
    This is an explanation of a key new insight into the halting problem provided in the language of software engineering. Technical computer science terms are explained using software engineering terms. -/- To fully understand this paper a software engineer must be an expert in the C programming language, the x86 programming language, exactly how C translates into x86 and what an x86 process emulator is. No knowledge of the halting problem is required.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  7. Halting Problem Undecidability and Infinitely Nested Simulation.P. Olcott -
    The halting theorem counter-examples present infinitely nested simulation (non-halting) behavior to every simulating halt decider. The pathological self-reference of the conventional halting problem proof counter-examples is overcome. The halt status of these examples is correctly determined. A simulating halt decider remains in pure simulation mode until after it determines that its input will never reach its final state. This eliminates the conventional feedback loop where the behavior of the halt decider effects the behavior of its input.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  8. Rebutting the Sipser Halting Problem Proof.P. Olcott - manuscript
    MIT Professor Michael Sipser has agreed that the following verbatim paragraph is correct (he has not agreed to anything else in this paper) -------> -/- If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  9. Halting Problem Proofs Refuted on the Basis of Software Engineering ?P. Olcott - manuscript
    This is an explanation of a possible new insight into the halting problem provided in the language of software engineering. Technical computer science terms are explained using software engineering terms. No knowledge of the halting problem is required. -/- It is based on fully operational software executed in the x86utm operating system. The x86utm operating system (based on an excellent open source x86 emulator) was created to study the details of the halting problem proof counter-examples at the much higher level (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  10. Randomness is Unpredictability.Jon Williamson - manuscript
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  11. Evolutionary Scenarios for the Emergence of Recursion.Lluís Barceló-Coblijn - forthcoming - Theoria Et Historia Scientiarum 9:171-199.
    Remove from this list  
     
    Export citation  
     
    Bookmark   3 citations  
  12. Computability: Gödel, Turing, Church, and Beyond.B. J. Copeland, C. Posy & O. Shagrir (eds.) - forthcoming - MIT Press.
  13. Explaining Experience In Nature: The Foundations Of Logic And Apprehension.Steven Ericsson-Zenith - forthcoming - Institute for Advanced Science & Engineering.
    At its core this book is concerned with logic and computation with respect to the mathematical characterization of sentient biophysical structure and its behavior. -/- Three related theories are presented: The first of these provides an explanation of how sentient individuals come to be in the world. The second describes how these individuals operate. And the third proposes a method for reasoning about the behavior of individuals in groups. -/- These theories are based upon a new explanation of experience in (...)
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  14. Reviewed Work(S): Lowness Properties and Randomness. Advances in Mathematics, Vol. 197 by André Nies; Lowness for the Class of Schnorr Random Reals. SIAM Journal on Computing, Vol. 35 by Bjørn Kjos-Hanssen; André Nies; Frank Stephan; Lowness for Kurtz Randomness. The Journal of Symbolic Logic, Vol. 74 by Noam Greenberg; Joseph S. Miller; Randomness and Lowness Notions Via Open Covers. Annals of Pure and Applied Logic, Vol. 163 by Laurent Bienvenu; Joseph S. Miller; Relativizations of Randomness and Genericity Notions. The Bulletin of the London Mathematical Society, Vol. 43 by Johanna N. Y. Franklin; Frank Stephan; Liang Yu; Randomness Notions and Partial Relativization. Israel Journal of Mathematics, Vol. 191 by George Barmpalias; Joseph S. Miller; André Nies. [REVIEW]Johanna N. Y. Franklin - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Review by: Johanna N. Y. Franklin The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 115-118, March 2013.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  15. Computability as a Physical Modality.Tamara Horowitz - forthcoming - Unpublished Ms Held in the Casimir Lewy Library, Cambridge.
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  16. Expression de la Recursion Primitive Dans le Calcul-XK.J. Ladriere - forthcoming - Logique Et Analyse.
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  17. Maximal Towers and Ultrafilter Bases in Computability Theory.Steffen Lempp, Joseph S. Miller, André Nies & Mariya I. Soskova - forthcoming - Journal of Symbolic Logic:1-20.
  18. Conference on Computability, Complexity and Randomness: Isaac Newton Institute, Cambridge, Uk July 2-6, 2012.Elvira Mayordomo & Wolfgang Merkle - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Elvira Mayordomo and Wolfgang Merkle The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 135-136, March 2013.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  19. Variations on Determinacy And.Ramez L. Sami - forthcoming - Journal of Symbolic Logic:1-10.
  20. Primitive Recursive Equivalence Relations and Their Primitive Recursive Complexity.Luca San Mauro, Nikolay Bazhenov, Keng Meng Ng & Andrea Sorbi - forthcoming - Computability.
    The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  21. A Note on the Learning-Theoretic Characterizations of Randomness and Convergence.Tomasz Steifer - forthcoming - Review of Symbolic Logic:1-15.
    Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the problem of convergence on random (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22. Computability and the Symmetric Difference Operator.Uri Andrews, Peter M. Gerdes, Steffen Lempp, Joseph S. Miller & Noah D. Schweber - 2022 - Logic Journal of the IGPL 30 (3):499-518.
    Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  23. Revolutions and Revelations in Computability.Ulrich Berger, Johanna N. Y. Franklin, Florin Manea & Arno Pauly (eds.) - 2022
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  24. Taming Koepke's Zoo II: Register Machines.Merlin Carl - 2022 - Annals of Pure and Applied Logic 173 (3):103041.
  25. Why AI Will Never Rule the World (Interview).Luke Dormehl, Jobst Landgrebe & Barry Smith - 2022 - Digital Trends.
    Call it the Skynet hypothesis, Artificial General Intelligence, or the advent of the Singularity — for years, AI experts and non-experts alike have fretted (and, for a small group, celebrated) the idea that artificial intelligence may one day become smarter than humans. -/- According to the theory, advances in AI — specifically of the machine learning type that’s able to take on new information and rewrite its code accordingly — will eventually catch up with the wetware of the biological brain. (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26. Relationships Between Computability-Theoretic Properties of Problems.Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey & Dan Turetsky - 2022 - Journal of Symbolic Logic 87 (1):47-71.
    A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  27. 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 associated (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  28. Why Machines Will Never Rule the World: Artificial Intelligence Without Fear.Jobst Landgrebe & Barry Smith - 2022 - Abingdon, England: Routledge.
    The book’s core argument is that an artificial intelligence that could equal or exceed human intelligence—sometimes called artificial general intelligence (AGI)—is for mathematical reasons impossible. It offers two specific reasons for this claim: Human intelligence is a capability of a complex dynamic system—the human brain and central nervous system. Systems of this sort cannot be modelled mathematically in a way that allows them to operate inside a computer. In supporting their claim, the authors, Jobst Landgrebe and Barry Smith, marshal evidence (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  29. Calculating the Mind-Change Complexity of Learning Algebraic Structures.Luca San Mauro, Nikolay Bazhenov & Vittorio Cipriani - 2022 - In Ulrich Berger, Johanna N. Y. Franklin, Florin Manea & Arno Pauly (eds.), Revolutions and Revelations in Computability. Cham, Svizzera: pp. 1-12.
    This paper studies algorithmic learning theory applied to algebraic structures. In previous papers, we have defined our framework, where a learner, given a family of structures, receives larger and larger pieces of an arbitrary copy of a structure in the family and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if there is a learner that eventually stabilizes to a correct conjecture. Here, we analyze the number of (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  30. Computability, Notation, and de Re Knowledge of Numbers.Stewart Shapiro, Eric Snyder & Richard Samuels - 2022 - Philosophies 1 (7).
    Saul Kripke once noted that there is a tight connection between computation and de re knowledge of whatever the computation acts upon. For example, the Euclidean algorithm can produce knowledge of which number is the greatest common divisor of two numbers. Arguably, algorithms operate directly on syntactic items, such as strings, and on numbers and the like only via how the numbers are represented. So we broach matters of notation. The purpose of this article is to explore the relationship between (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  31. Computability, Notation, and de Re Knowledge of Numbers.Stewart Shapiro, Eric Snyder & Richard Samuels - 2022 - Philosophies 7 (20):20.
    Saul Kripke once noted that there is a tight connection between computation and de re knowledge of whatever the computation acts upon. For example, the Euclidean algorithm can produce knowledge of _which number_ is the greatest common divisor of two numbers. Arguably, algorithms operate directly on syntactic items, such as strings, and on numbers and the like only via how the numbers are represented. So we broach matters of _notation_. The purpose of this article is to explore the relationship between (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  32. Computability and the game of cops and robbers on graphs.Rachel D. Stahl - 2022 - Archive for Mathematical Logic 61 (3):373-397.
    Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are explored. The (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  33. On Characterizations of Learnability with Computable Learners.Tom F. Sterkenburg - 2022 - Proceedings of Machine Learning Research 178:3365-3379.
    We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of strong CPAC learning, and provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  34. A Journey Through Computability, Topology and Analysis.Manlio Valenti - 2022 - Bulletin of Symbolic Logic 28 (2):266-267.
    This thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and descriptive set theory. We will especially focus on Weihrauch reducibility as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of problems arising from theorems that lie at the higher levels of the reverse mathematics hierarchy.We first analyze the strength of the open and (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35. Foundations of Logic: Completeness, Incompleteness, Computability.Dag Westerståhl - 2022 - Beijing: CSLI Publications & Tsinghua University.
    This book covers completeness of first-order logic, some model theory, Gödel's incompleteness theorems and related results, and a smattering of computability theory. The text is self-contained and provides full proofs of the main facts. Ideally, the reader of this work has already taken at least one introductory logic course; however, everything needed to understand the syntax and semantics of first-order logic is presented herein. Students from philosophy, linguistics, computer science, physics, and other related subjects will find this work useful and (...)
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  36. Complexity of Syntactical Tree Fragments of Independence-Friendly Logic.Fausto Barbero - 2021 - Annals of Pure and Applied Logic 172 (1):102859.
    A dichotomy result of Sevenster (2014) [29] completely classified the quantifier prefixes of regular Independence-Friendly (IF) logic according to the patterns of quantifier dependence they contain. On one hand, prefixes that contain “Henkin” or “signalling” patterns were shown to characterize fragments of IF logic that capture NP-complete problems; all the remaining prefixes were shown instead to be essentially first-order. In the present paper we develop the machinery which is needed in order to extend the results of Sevenster to non-prenex, regular (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  37. Completion of Choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.
    We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  38. Incompleteness and the Halting Problem.Cristian S. Calude - 2021 - Studia Logica 109 (5):1159-1169.
    We present an abstract framework in which we give simple proofs for Gödel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’, Chaitin’s and Kritchman-Raz’s Theorems.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  39. Connecting with Computability. CiE 2021. Lecture Notes in Computer Science, Vol 12813.L. De Mol, A. Weiermann, F. Manea & D. Fernández-Duque (eds.) - 2021
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  40. Connecting with Computability. Proceedings of Computability in Europe.Liesbeth De Mol, Andreas Weiermann, Florin Manea & David Fernández-Duque (eds.) - 2021
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  41. Computable Irrational Numbers with Representations of Surprising Complexity.Ivan Georgiev, Lars Kristiansen & Frank Stephan - 2021 - Annals of Pure and Applied Logic 172 (2):102893.
  42. Intrinsic Density, Asymptotic Computability, and Stochasticity.Justin Miller - 2021 - Bulletin of Symbolic Logic 27 (2):220-220.
    There are many computational problems which are generally “easy” to solve but have certain rare examples which are much more difficult to solve. One approach to studying these problems is to ignore the difficult edge cases. Asymptotic computability is one of the formal tools that uses this approach to study these problems. Asymptotically computable sets can be thought of as almost computable sets, however every set is computationally equivalent to an almost computable set. Intrinsic density was introduced as a way (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  43. Intrinsic Smallness.Justin Miller - 2021 - Journal of Symbolic Logic 86 (2):558-576.
    Recent work in computability theory has focused on various notions of asymptotic computability, which capture the idea of a set being “almost computable.” One potentially upsetting result is that all four notions of asymptotic computability admit “almost computable” sets in every Turing degree via coding tricks, contradicting the notion that “almost computable” sets should be computationally close to the computable sets. In response, Astor introduced the notion of intrinsic density: a set has defined intrinsic density if its image under any (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  44. Computable Analogs of Cardinal Characteristics: Prediction and Rearrangement.Iván Ongay-Valverde & Paul Tveite - 2021 - Annals of Pure and Applied Logic 172 (1):102872.
    There has recently been work by multiple groups in extracting the properties associated with cardinal invariants of the continuum and translating these properties into similar analogous combinatorial properties of computational oracles. Each property yields a highness notion in the Turing degrees. In this paper we study the highness notions that result from the translation of the evasion number and its dual, the prediction number, as well as two versions of the rearrangement number. When translated appropriately, these yield four new highness (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  45. The Characterization of Weihrauch Reducibility in Systems Containing.Patrick Uftring - 2021 - Journal of Symbolic Logic 86 (1):224-261.
    We characterize Weihrauch reducibility in $ \operatorname {\mathrm {E-PA^{\omega }}} + \operatorname {\mathrm {QF-AC^{0,0}}}$ and all systems containing it by the provability in a linear variant of the same calculus using modifications of Gödel’s Dialectica interpretation that incorporate ideas from linear logic, nonstandard arithmetic, higher-order computability, and phase semantics.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46. Strengthening Weak Emergence.Nora Berenstain - 2020 - Erkenntnis 87 (5):2457-2474.
    Bedau's influential (1997) account analyzes weak emergence in terms of the non-derivability of a system’s macrostates from its microstates except by simulation. I offer an improved version of Bedau’s account of weak emergence in light of insights from information theory. Non-derivability alone does not guarantee that a system’s macrostates are weakly emergent. Rather, it is non-derivability plus the algorithmic compressibility of the system’s macrostates that makes them weakly emergent. I argue that the resulting information-theoretic picture provides a metaphysical account of (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  47. Weaker Variants of Infinite Time Turing Machines.Matteo Bianchetti - 2020 - Archive for Mathematical Logic 59 (3-4):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 (4 more)  
     
    Export citation  
     
    Bookmark  
  48. Computability, Orders, and Solvable Groups.Arman Darbinyan - 2020 - Journal of Symbolic Logic 85 (4):1588-1598.
    The main objective of this paper is the following two results. There exists a computable bi-orderable group that does not have a computable bi-ordering; there exists a bi-orderable, two-generated computably presented solvable group with undecidable word problem. Both of the groups can be found among two-generated solvable groups of derived length $3$. [a]nswers a question posed by Downey and Kurtz; answers a question posed by Bludov and Glass in Kourovka Notebook.One of the technical tools used to obtain the main results (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  49. Computable Linear Orders and Products.Andrey N. Frolov, Steffen Lempp, Keng Meng Ng & Guohua Wu - 2020 - Journal of Symbolic Logic 85 (2):605-623.
    We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  50. Cupping and Jump Classes in the Computably Enumerable Degrees.Noam Greenberg, Keng Meng Ng & Guohua Wu - 2020 - Journal of Symbolic Logic 85 (4):1499-1545.
    We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are ${\operatorname {\mathrm {low}}}_3$-cuppable, or indeed ${\operatorname {\mathrm {low}}}_n$ cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the ${\operatorname {\mathrm {low}}}_2$-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 485