Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recursively-enumerable]

Used for questions about the recursively enumerable sets in computability theory/recursion theory. Should be pretty self-explanatory.

5
votes
1answer
101 views

Given B,C incomplete, incomparable r.e. sets must C compute low r.e. set avoiding cone below B? (ADDED: Uniformly?)

I feel like there must be a classical result answering this question (or easily modified to do so) but a quick flip through Soare didn't produce anything so rather than waste time I figured I'd just ...
2
votes
1answer
106 views

Correct Proof Of ZBC Theorem From Odifreddi? Also Extension Question

So I'm looking at the proof of the ZBC lemma in Odifreddi's Classical Recursion Theory volume 2 page 808 and I don't see why $ 0' \oplus C$ produced computes $B'$ as claimed. The positive ...