Turing Degree - Post's Problem and The Priority Method

Post's Problem and The Priority Method

Emil Post studied the r.e. Turing degrees and asked whether there is any r.e. degree strictly between 0 and 0′. The problem of constructing such a degree (or showing that none exist) became known as Post's problem. This problem was solved independently by Friedberg and Muchnik in the 1950s, who showed that these intermediate r.e. degrees do exist. Their proofs each developed the same new method for constructing r.e degrees which came to be known as the priority method. The priority method is now the main technique for establishing results about r.e. sets.

The idea of the priority method for constructing an r.e. set X is to list a countable sequence of requirements that X must satisfy. For example, to construct an r.e. set X between 0 and 0′ it is enough to satisfy the requirements A_e and B_e for each natural number e, where A_e requires that the oracle machine with index e does not compute 0′ from X and B_e requires that the Turing machine with index e (and no oracle) does not compute X. These requirements are put into a priority ordering, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set X is enumerated. At each stage, numbers may put into X or forever prevented from entering X in an attempt to satisfy requirements (that is, force them to hold once all of X has been enumerated). Sometimes, a number can be enumerated into X to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be injured). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set X is r.e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r.e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result.