Computability - Volume 5, issue 1

Authors: Brattka, Vasco | Bonizzoni, Paola | Bournez, Olivier | Mayordomo, Elvira

Article Type: Editorial

DOI: 10.3233/COM-160051

Citation: Computability, vol. 5, no. 1, pp. 1-1, 2016

Authors: Löwe, Benedikt

Article Type: Obituary

Abstract: This note is not to be misunderstood as a general obituary touching all of the many facets of Barry’s personality: the teacher, the researcher, the activist, and, in general, the enthusiastic supporter of good causes. Rather, it should be seen as the author’s personal recollection of the crucial role that Barry played in the transition of Computability in Europe from European network proposal via conference and conference series to association.

DOI: 10.3233/COM-160052

Citation: Computability, vol. 5, no. 1, pp. 3-11, 2016

Authors: Hirschfeldt, Denis R. | Jockusch Jr., Carl G. | McNicholl, Timothy H. | Schupp, Paul E.

Article Type: Research Article

Abstract: For r ∈ [ 0 , 1 ] we say that a set A ⊆ ω is coarsely computable at density r if there is a computable set C such that { n : C ( n ) = A ( n ) } has lower density at least r . Let γ ( A ) = sup { r : A   is coarsely computable at density   r } . We study the interactions of these concepts with Turing reducibility. For example, we show that …if r ∈ ( 0 , 1 ] there are sets A 0 , A 1 such that γ ( A 0 ) = γ ( A 1 ) = r where A 0 is coarsely computable at density r while A 1 is not coarsely computable at density r . We show that a real r ∈ [ 0 , 1 ] is equal to γ ( A ) for some c.e. set A if and only if r is left-Σ 3 0 . A surprising result is that if G is a Δ 2 0 1-generic set, and A ⩽ T G with γ ( A ) = 1 , then A is coarsely computable at density 1. Show more

Keywords: Asymptotic density, coarse computability, Turing degrees

DOI: 10.3233/COM-150035

Citation: Computability, vol. 5, no. 1, pp. 13-27, 2016

Authors: Basu, Sankha S. | Simpson, Stephen G.

Article Type: Research Article

Abstract: In this paper we study a model of intuitionistic higher-order logic which we call the Muchnik topos . The Muchnik topos may be defined briefly as the category of sheaves of sets over the topological space consisting of the Turing degrees, where the Turing cones form a base for the topology. We note that our Muchnik topos interpretation of intuitionistic mathematics is an extension of the well known Kolmogorov/Muchnik interpretation of intuitionistic propositional calculus via Muchnik degrees, i.e., mass problems under weak reducibility. We introduce a new sheaf representation of the intuitionistic real numbers, the Muchnik reals , which are …different from the Cauchy reals and the Dedekind reals. Within the Muchnik topos we obtain a choice principle ( ∀ x ∃ y A ( x , y ) ) ⇒ ∃ w ∀ x A ( x , w x ) and a bounding principle ( ∀ x ∃ y A ( x , y ) ) ⇒ ∃ z ∀ x ∃ y ( y ⩽ T ( x , z ) ∧ A ( x , y ) ) where x , y , z range over Muchnik reals, w ranges over functions from Muchnik reals to Muchnik reals, and A ( x , y ) is a formula not containing w or z . For the convenience of the reader, we explain all of the essential background material on intuitionism, sheaf theory, intuitionistic higher-order logic, Turing degrees, mass problems, Muchnik degrees, and Kolmogorov’s calculus of problems. In a separate document we provide an English translation of Muchnik’s 1963 paper on Muchnik degrees. Show more

Keywords: Degrees of unsolvability, Muchnik degrees, mass problems, intuitionism, computable analysis, higher-order logic, topos theory, sheaves, sheaf theory, Kolmogorov

DOI: 10.3233/COM-150041

Citation: Computability, vol. 5, no. 1, pp. 29-47, 2016

Authors: Muchnik, Albert A.

Article Type: Research Article

Keywords: M-problems, Ex-problems, weak reducibility, weak degrees

DOI: 10.3233/COM-150042

Citation: Computability, vol. 5, no. 1, pp. 49-59, 2016

Authors: Normann, Dag

Article Type: Research Article

Abstract: We prove that if a closed subset X of the Baire space is searchable in the sense of Escardó [Logical Methods in Computer Science 4 (3) (2008), 3], and by a functional definable in Gödel’s T , then X is countable, and the Cantor–Bendixson rank of X is bounded by the ordinal ε 0 . To this end we introduce evaluation trees , well founded decorated trees that induce operators from the full set-theoretical class N N → N to N N …. We prove that when a search operator for a set X is induced from an evaluation tree T , then the Cantor–Bendixson rank of X is bounded by the Kleene–Brouwer order type of T . Further we use a theorem due to Howard [Journal of Symbolic Logic 45 (3) (1980), 493–504], estimating the ordinal complexity of the reduction tree of a term in system T , to show that all functionals of type ( N N → N ) → N N definable in T can be computed using an evaluation tree of ordinal rank below ε 0 . Show more

Keywords: Searchable, Gödel’s T, Cantor–Bendixson rank

DOI: 10.3233/COM-150043

Citation: Computability, vol. 5, no. 1, pp. 61-74, 2016

Authors: de Brecht, Matthew | Schröder, Matthias | Selivanov, Victor

Article Type: Research Article

Abstract: We define and study new classifications of qcb0 -spaces based on the idea to measure the complexity of their bases. The new classifications complement those given by recently introduced hierarchies of qcb0 -spaces and provide new tools to investigate non-countably based qcb0 -spaces. As a by-product, we show that there is no universal qcb0 -space and establish several new properties of the Kleene–Kreisel continuous functionals of countable types.

Keywords: qcb0-spaces, Y-based spaces, hyperspaces, Scott topology, hyperprojective hierarchy, Kleene–Kreisel continuous functionals

DOI: 10.3233/COM-150044

Citation: Computability, vol. 5, no. 1, pp. 75-102, 2016