New answers tagged

3

In this context, uniformity usually means that there exists an algorithm/Turing machine computing the thing that is being called uniform. That is, in this case, that there is a Turing machine that will compute $i,j$ from (Turing machines for) $f,g$. More formally (in the context of the paper), it means: There is a Turing machine $B$ such that, for any total ...


12

Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable (c.e.) subset $S \subseteq \mathbb{N}$ contains either finitely many elements of $L$ or all but finitely many elements of $L$. Let $f : \mathbb{N} \to \mathbb{...


Top 50 recent answers are included