There exist computably enumerable sets A and B that are Turing-incomparable and both strictly below the halting problem — solving Post's 1944 problem. Friedberg 1957 and Muchnik 1956, independently. Proof introduces the priority method:…
There exist computably enumerable sets A and B that are Turing-incomparable and both strictly below the halting problem — solving Post's 1944 problem. Friedberg 1957 and Muchnik 1956, independently. Proof introduces the priority method:…