We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipschitz functions is Σ20-complete. (Every regular function is pointwise linear-time Lipschitz.) We show that a function f:[0,1]→R is (binary) transducer if and only if it is continuous regular. As one of many consequences, our Σ20-completeness result covers the class of transducer functions as well. Finally, we show that the Banach space C[0,1] of real-valued continuous functions admits an arithmetical classification among separable Banach spaces. Our proofs combine methods of abstract computability theory, automata theory, and functional analysis.

Abstract We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

Abstract We define a real $A$ to be low for paths in Baire space (or Cantor space) if every $\varPi ^0_1$ class with an $A$-computable element has a computable element. We prove that lowness for paths in Baire space and lowness for paths in Cantor space are equivalent and, furthermore, that these notions are also equivalent to lowness for isomorphism.

for furthering research in logic and the exchange of ideas among mathematicians, computer scientists, linguists, and others interested in this fi eld.

Abstract In contrast with the notion of complexity, a setAis called anti-complex if the Kolmogorov complexity of the initial segments ofAchosen by a recursive function is always bounded by the identity function. We show that, as for complexity, the natural arena for examining anti-complexity is the weak-truth table degrees. In this context, we show the equivalence of anti-complexity and other lowness notions such as r.e. traceability or being weak truth-table reducible to a Schnorr trivial set. A setAis anti-complex if and only if it is reducible to another setBwithtiny use, whereby we mean that the use function for reducingAtoBcan be made to grow arbitrarily slowly, as gauged by unbounded nondecreasing recursive functions. This notion of reducibility is then studied in its own right, and we also investigate its range and the range of its uniform counterpart.

Abstract We study the connection between Schnorr triviality and genericity. We show that while no 2-generic is Turing equivalent to a Schnorr trivial and no 1-generic is tt-equivalent to a Schnorr trivial, there is a 1-generic that is Turing equivalent to a Schnorr trivial. However, every such 1-generic must be high. As a corollary, we prove that not all K-trivials are Schnorr trivial. We also use these techniques to extend a previous result and show that the bases of cones of Schnorr trivial Turing degrees are precisely those whose jumps are at least 0″.

Abstract We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey. Griffiths and LaForte.

Abstract We investigate the relationship between lowness for Schnorr randomness and Schnorr triviality. We show that a real is low for Schnorr randomness if and only if it is Schnorr trivial and hyperimmune free.