Computability Theory

132 Computability Theory

Proposition: 0

0

is the largest recursively enumerable degree. That is, a ≤ 0

0

for any

recursively enumerable degree a.

Proof. Take an r.e. set A in a. We saw in Chapter 4 that A ≤

m

K because K is a complete

r.e. set. Therefore A ≤

T

K. So a ≤ 0

0

. a

In 1944, Emil Post raised the question whether there were any r.e. degrees other than

0 and 0

0

. This question, which became known as “Post’s problem,” was finally answered

in 1956 (two years after Post’s death), independently by Richard Friedberg (in his

Harvard senior thesis) and by Albert A. Muchnik in Russia. They showed that inter-

mediate r.e. degrees do indeed exist, and in great