12.4 Post’s Problem
12.4 Post’s Problem (Overview) The halting problem shows that some sets are not computable. Turing degrees refine this by measuring how hard such sets are. A natural question arises: is there any degree strictly between computable sets and the halting problem? Let: $$ \mathbf{0} $$ be the degree of computable sets, and: $$ \mathbf{0'} $$ be the degree of the halting problem. Post’s problem asks whether there exists a recursively...