New answers tagged computability
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
