Computability - Volume 7, issue 2-3

Authors: Löwe, Benedikt

Article Type: Editorial

DOI: 10.3233/COM-180091

Citation: Computability, vol. 7, no. 2-3, pp. 101-101, 2018

Authors: Elwes, Richard | Lewis-Pye, Andy | Löwe, Benedikt | Macpherson, Dugald | Normann, Dag | Sorbi, Andrea | Soskova, Alexandra A. | Soskova, Mariya I. | van Emde Boas, Peter | Wainer, Stan

Article Type: Obituary

DOI: 10.3233/COM-180092

Citation: Computability, vol. 7, no. 2-3, pp. 103-131, 2018

Authors: Cooper, S. Barry | Li, Angsheng | Xia, Mingji

Article Type: Research Article

Abstract: It is shown that for any computably enumerable degree a ≠ 0 , and any Turing degree s , if s ⩾ 0 ′ , and c.e. in a , then there exists a c.e. degree x with the following properties: x < a , a is splittable over x , and x ′ = s .

Keywords: Turing degrees, jump inversion, splitting, computably enumerable degree

DOI: 10.3233/COM-180083

Citation: Computability, vol. 7, no. 2-3, pp. 133-142, 2018

Authors: Cooper, S. Barry | Gay, James | Harris, Charles M. | Lee, Kyung Il | Morphett, Anthony

Article Type: Research Article

Abstract: A partial order is computably well founded if it does not computably embed a copy of ω ∗ , the order type of the negative integers. It is computably scattered if it does not computably embed a copy of η , the order type of Q . It is known that, for each of these properties, there are computable partial orders satisfying the property which do not have a computable linear extension with the same property. Rosenstein showed, however, that for both of these properties, every computable partial order satisfying the property has …a Δ 2 0 linear extension also satisfying the property. Thus, linear extensions of a computable order preserving the properties of computable well foundedness or computable scatteredness can always be found at the Δ 2 0 level of the arithmetical hierarchy, but not at the Δ 1 0 level. In this paper, we investigate at which level of the Ershov hierarchy such linear extensions can be found. We show that, for both properties, every computable partial order satisfying the property has an ω -c.e. linear extension with the same property. We establish that this is the best possible result within the Ershov hierarchy by constructing, respectively, computably well founded and computably scattered orders which do not have n -c.e. linear extensions which are computably well founded and computably scattered respectively, for any n < ω . In a strengthening of Rosenstein’s theorems in another direction, we show that a linear extension preserving each of these properties can be computed using any oracle satisfying an escape property, which includes the class of non-generalised low2 sets. Finally, we show that the analogue of Rosenstein’s theorems do not hold for the property of not computably embedding a copy of ζ , the order type of the integers, by constructing a computable partial ordering which does not embed ζ , but such that every Δ 2 0 linear extension of the ordering does admit a computable embedding of ζ . Show more

Keywords: Computable, partial order, linear extension, well founded, scattered, Ershov hierarchy, arithmetical hierarchy

DOI: 10.3233/COM-170080

Citation: Computability, vol. 7, no. 2-3, pp. 143-169, 2018

Authors: Barmpalias, George | Lewis-Pye, Andrew | Li, Angsheng

Article Type: Research Article

Abstract: Schnorr showed that a real X is Martin-Löf random if and only if K ( X ↾ n ) ⩾ n − c for some constant c and all n , where K denotes the prefix-free complexity function. Fortnow (unpublished) and Nies, Stephan and Terwijn [J. Symbolic Logic 70 (2005 ), 515–535] observed that the condition K ( X ↾ n ) ⩾ n − c can be replaced with K ( X ↾ r n ) …⩾ r n − c , for any fixed increasing computable sequence ( r n ) , in this characterization. The purpose of this note is to establish the following generalisation of this fact. We show that X is Martin-Löf random if and only if ∃ c ∀ n K ( X ↾ r n ) ⩾ r n − c , where ( r n ) is any fixed pointedly X-computable sequence, in the sense that r n is computable from X in a self-delimiting way, so that at most the first r n bits of X are queried in the computation of r n . On the other hand, we also show that there are reals X which are very far from being Martin-Löf random, but for which there exists some X -computable sequence ( r n ) such that ∀ n K ( X ↾ r n ) ⩾ r n . Show more

Keywords: Computability, algorithmic randomness, Kolmogorov complexity

DOI: 10.3233/COM-170076

Citation: Computability, vol. 7, no. 2-3, pp. 171-177, 2018

Authors: Ganchev, Hristo A. | Soskova, Mariya I.

Article Type: Research Article

Abstract: We show that all levels of the jump hierarchy are first order definable in the local structure of the enumeration degrees.

Keywords: Enumeration degrees, definability, jump classes

DOI: 10.3233/COM-170072

Citation: Computability, vol. 7, no. 2-3, pp. 179-188, 2018

Authors: Lewis-Pye, Andrew E.M.

Article Type: Research Article

Abstract: We give an introduction to the Turing degrees, aimed principally at those who have some experience with computability theory, but not necessarily with techniques specific to the study of the local degrees. The focus is on establishing which definable properties are satisfied by the degrees in the various jump classes, as introduced by Cooper and Soare in the 1970s. Along the way, we also point to a good number of open problems.

Keywords: Computability, degrees, Turing, jump classes, definability

DOI: 10.3233/COM-170068

Citation: Computability, vol. 7, no. 2-3, pp. 189-235, 2018

Authors: Ambos-Spies, Klaus

Article Type: Research Article

Abstract: We give various examples of automorphism bases for the recursively enumerable (r.e.) degrees. In particular, we show that any nontrivial initial segment of the r.e. degrees is an automorphism base.

Keywords: Recursively enumerable sets, degrees, automorphisms, automorphism bases

DOI: 10.3233/COM-180088

Citation: Computability, vol. 7, no. 2-3, pp. 237-258, 2018

Authors: Calude, Cristian S. | Dumitrescu, Monica

Article Type: Research Article

Abstract: The Halting Problem, the most (in)famous undecidable problem, has important applications in theoretical and applied computer science and beyond, hence the interest in its approximate solutions. Experimental results reported on various models of computation suggest that halting programs are not uniformly distributed – running times play an important role. A reason is that a program which eventually stops but does not halt “quickly”, stops at a time which is algorithmically compressible. In this paper we work with running times to define a class of computable probability distributions on the set of halting programs in order to construct an anytime …algorithm for the Halting problem with a probabilistic evaluation of the error of the decision. Show more

Keywords: Halting Problem, anytime algorithm, running time distribution

DOI: 10.3233/COM-170073

Citation: Computability, vol. 7, no. 2-3, pp. 259-271, 2018

Authors: Jain, Sanjay | Khoussainov, Bakhadyr | Stephan, Frank

Article Type: Research Article

Abstract: The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups; as a consequence, various undecidability results for Cayley automatic groups hold also for finitely generated semiautomatic groups. However, in spite of their generality, the word problem of finitely generated semiautomatic groups is still solvable in quadratic time. Furthermore, the present work establishes that every finitely generated group of nilpotency class three is semiautomatic. It remains open whether the finitely generated semiautomatic groups are a strict superclass of the Cayley automatic groups.

Keywords: Nilpotent groups, automatic groups, automatic structures, semiautomatic structures, Cayley automatic groups, semigroups, finitely generated groups

DOI: 10.3233/COM-180089

Citation: Computability, vol. 7, no. 2-3, pp. 273-287, 2018

Authors: Selivanov, Victor L. | Yamaleev, Mars M.

Article Type: Research Article

Abstract: In 1971 B. Cooper proved that there exists a 2-c.e. Turing degree which doesn’t contain a c.e. set. Thus, he showed that the second level of the Ershov hierarchy is proper. In this paper we investigate proper levels of some extensions of the Ershov hierarchy to higher levels of the arithmetical hierarchy. Thus we contribute to the theory of Δ 3 0 -degrees by extending Cooper’s theorem to some levels of the fine hierarchy within Δ 3 0 -sets.

Keywords: Ershov’s hierarchy, fine hierarchy, arithmetical hierarchy, Turing degrees, Σ20-sets

DOI: 10.3233/COM-180085

Citation: Computability, vol. 7, no. 2-3, pp. 289-300, 2018