Computability - Volume 8, issue 2

Authors: Miller, Russell

Article Type: Research Article

Abstract: We introduce a topology on the space of all isomorphism types represented in a given class of countable models, and use this topology as an aid in classifying the isomorphism types. This mixes ideas from effective descriptive set theory and computable structure theory, extending concepts from the latter beyond computable structures to examine the isomorphism problem on arbitrary countable structures. We give examples using specific classes of fields and of trees, illustrating how the new concepts can yield classifications that reveal differences between seemingly similar classes. Finally, we use a computable homeomorphism to define a measure on the space of …isomorphism types of algebraic fields, and examine the prevalence of relative computable categoricity under this measure. Show more

Keywords: Algebraic fields, classification, computability, computable categoricity, computable structure theory, measure

DOI: 10.3233/COM-180095

Citation: Computability, vol. 8, no. 2, pp. 99-117, 2019

Authors: Longley, John

Article Type: Research Article

Abstract: We show that the bar recursion operators of Spector and Kohlenbach, considered as third-order functionals acting on total arguments, are not computable in Gödel’s System T plus minimization, which we show to be equivalent to a programming language with a higher-order iteration construct. The main result is formulated so as to imply the non-definability of bar recursion in T + min within a variety of partial and total models, for instance the Kleene–Kreisel continuous functionals. The paper thus supplies proofs of some results stated in the book by Longley and Normann. The proof of the …main theorem makes serious use of the theory of nested sequential procedures (also known as PCF Böhm trees), and proceeds by showing that bar recursion cannot be represented by any sequential procedure within which the tree of nested function applications is well-founded. Show more

Keywords: Computability, higher-order, non-definable, bar recursion, iteration

DOI: 10.3233/COM-180200

Citation: Computability, vol. 8, no. 2, pp. 119-153, 2019

Authors: Astor, Eric P. | Hirschfeldt, Denis R. | Jockusch Jr., Carl G.

Article Type: Research Article

Abstract: This paper concerns algorithms that give correct answers with (asymptotic) density 1. A dense description of a function g : ω → ω is a partial function f on ω such that { n : f ( n ) = g ( n ) } has density 1. We define g to be densely computable if it has a partial computable dense description f . Several previous authors have studied the stronger notions of generic computability and coarse computability, which correspond respectively to requiring in addition that g …and f agree on the domain of f , and to requiring that f be total. Strengthening these two notions, call a function g effectively densely computable if it has a partial computable dense description f such that the domain of f is a computable set and f and g agree on the domain of f . We compare these notions as well as asymptotic approximations to them that require for each ε > 0 the existence of an appropriate description that is correct on a set of lower density of at least 1 − ε . We show that certain implications hold among these various notions of approximate computability, and that no other implications between these notions hold, in the strong sense that any Boolean combination of these notions is satisfied by a c.e. set unless it is ruled out by the implications we describe. We define reducibilities corresponding to dense and effectively dense reducibility and show that their uniform and nonuniform versions are different. We show that there are natural embeddings of the Turing degrees into the corresponding degree structures, and that these embeddings are not surjective and indeed that sufficiently random sets have quasiminimal degree. We show that nontrivial upper cones in the generic, dense, and effective dense degrees are of measure 0 and use this fact to show that there are minimal pairs in the dense degrees. Show more

Keywords: Asymptotic density, dense computability, coarse computability, generic computability, reducibilities, quasiminimality

DOI: 10.3233/COM-180231

Citation: Computability, vol. 8, no. 2, pp. 155-177, 2019

Authors: McNicholl, Timothy H. | Stull, Donald M.

Article Type: Research Article

Abstract: When p is a computable real so that p ⩾ 1 , we define the isometry degree of a computable presentation of ℓ p to be the least powerful Turing degree d by which it is d -computably isometrically isomorphic to the standard presentation of ℓ p . We show that this degree always exists and that when p ≠ 2 these degrees are precisely the c.e. degrees.

Keywords: Computable analysis, functional analysis

DOI: 10.3233/COM-180214

Citation: Computability, vol. 8, no. 2, pp. 179-189, 2019