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 Ae and Be for each natural number e, where Ae requires that the oracle machine with index e does not compute 0′ from X and Be 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.
Read more about this topic: Turing Degree
Famous quotes containing the words post, problem, priority and/or method:
“To the old saying that man built the house but woman made of it a “home” might be added the modern supplement that woman accepted cooking as a chore but man has made of it a recreation.”
—Emily Post (1873–1960)
“The problem with marriage is that it ends every night after making love, and it must be rebuilt every morning before breakfast.”
—Gabriel García Márquez (b. 1928)
“It can be fairly argued that the highest priority for mankind is to save itself from extinction. However, it can also be argued that a society that neglects its children and robs them of their human potential can extinguish itself without an external enemy.”
—Selma Fraiberg (20th century)
““English! they are barbarians; they don’t believe in the great God.” I told him, “Excuse me, Sir. We do believe in God, and in Jesus Christ too.” “Um,” says he, “and in the Pope?” “No.” “And why?” This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, “Because we are too far off.” A very new argument against the universal infallibility of the Pope.”
—James Boswell (1740–1795)