Degrees of unsolvability and the arithmetical hierarchy

Turing and many-one reducibility, Turing degrees and the jump, recursive isomorphism (Myhill), productive, creative, simple and immune sets, r.e.-completeness, and the arithmetical hierarchy.

• Productive, creative, simple and immune sets
• Recursive isomorphism and 1-equivalence
• Turing reducibility
• Arithmetical hierarchy
• Completeness of the halting set
• Turing degrees and the Turing jump

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.