Post’s Degrees of Unsolvability

Post [42] does it by comparing the complexity of two sets A, B c N using several methods of reducing effectively the relation of membership in A to that of membership in B. The strongest of these is one-one reducibility,

close to the mildly weaker many-one reducibility A <m B where it is not required that ve be an injection. The weakest and most important is Turing reducibility,

We will also use the strict and symmetric versions of these reducibilities,

and similarly for <m, =m, <T, =T.

The symmetric relations induce natural notions of degrees, e.g.,

the 1 -1 degree of A = di (A) ={B : B = A},

the Turing degree of A = d(A) = {B : B =T A};

and the central objects of study are these sets of degrees with their natural partial orders, most significantly the poset of Turing degrees (D, <T) where

Post focusses on the study of the degrees of recursively enumerable sets (App 7). He introduces the “self-referential” version of Turing’s Halting Problem

and proves that it is r.e. complete, i.e., it is r.e. and every r.e. set is 1-1 reducible to it. In particular K is not recursive, and then the natural question is whether there are r.e. sets intermediate in complexity between the recursive sets and K. Post proves this for all of his reducibilities except for Turing’s and asks what became known as Post’s Problem: is there an r.e. set A such that 0 <T A <T K? Friedberg and Muchnik proved that there is, some ten years later, and this initiated a research program in the theory of degrees and r.e. degrees which is still vibrant today.

< Prev   CONTENTS   Source   Next >