Some Results in Computability Theory

We consider the question of universality among computable ω-branching trees. To this end, we construct a computable ω-branching tree TKP whose paths compute the complete diagrams of the countable ω-models of Kripke-Platek set theory (KP). We show that, given a path f through TKP , representing a model M of KP, and another computable ill-founded ω-branching tree T, if f fails to compute a path through
T, then M assigns to T a nonstandard ordinal tree rank. Further, we indicate some circumstances in which, given computable ω-branching trees T0 and T1, a path through TKP helps the paths through T0 compute paths through T1.

In a different line of work, we consider effective forcing notions. In particular, we define a class of effective forcing notions that are similar to versions of Mathias forcing and Cohen forcing defined in the literature, and prove some results about how these notions relate. As a consequence, we see that the generics for an effective version of Mathias forcing compute generics for an effective version of Hechler forcing, and vice-versa. Later, we focus on a notion of Mathias forcing over a countable Turing ideal, defined by Cholak, Dzhafarov, and Soskova. We show that there are nested Turing ideals for which the Mathias generics for the larger ideal do not all compute Mathias generics for the smaller ideal.