Computability

We show that natural structures related to the so called homomorphism preorder (or h -preorder) on the iterated labeled forests have isomorphic copies computable in polynomial time. Moreover, the polynomials in the upper bounds are of low degree which makes the computational content of the whole theory feasible. We discuss possible applications of these results to relevant questions of automata and computability theory.

Computability theory is a discipline in the intersection of computer science and mathematical logic where the fundamental question is:

Given two mathematical objects X and Y, does X compute Y in principle?

In case X and Y are real numbers, Turing’s famous ‘machine’ model provides the standard interpretation of ‘computation’ for this question. To formalise computation involving (total) abstract objects, Kleene introduced his S1–S9 computation schemes. In turn, Dag Normann and the author have introduced a version of the lambda calculus involving fixed point operators that exactly captures S1–S9 and accommodates partial objects. In this paper, we use this new model to develop the computability theory of various well-known theorems due to Baire and Volterra and related results; these theorems only require basic mathematical notions such as continuity, open sets, and density. We show that these theorems due to Baire and Volterra are computationally equivalent from the point of view of our new model, sometimes working in rather tame fragments of Gödel’s T .

We show that, in general, there is no degree corresponding to the composition of two problems in the computable reducibility lattice. We show the same in the strong computable reducibility setting.

In a recent article, we introduced and studied a precise class of dynamical systems called solvable systems that present a dynamic ruled by discontinuous ordinary differential equations with solvable right-hand terms. These systems are interesting because, when they exhibit a unique evolution, a transfinite method always exists to define such evolution as a limit of a sequence of continuous functions. We also presented several examples including a nontrivial one whose solution yields, at an integer time, a real encoding of the halting set for Turing machines; therefore showcasing that the behavior of solvable systems might describe ordinal Turing computations. In the current article, we study in more depth solvable systems, using tools from descriptive set theory. By establishing a correspondence with the class of well-founded trees, we construct a coanalytic ranking over the set of real functions with bounded, solvable derivatives and discuss its relation with other existing rankings for differentiable functions, in particular with the Kechris–Woodin, Denjoy, and Zalcwasser ranking. We prove that our ranking is unbounded below the first uncountable ordinal.