Friedberg and Muchnik's theorem

The set of Friedberg and Muchnik is a result of computability theory and mathematical logic , the 1956/1957 independently by Richard M. Friedberg and Albert Muchnik was proved. It says that there are recursively enumerable Turing degrees that lie between 0 and 0 ′ . So there are recursively enumerable sets that are not decidable , but easier than the holding problem in the sense of the Turing reduction . For their evidence Friedberg and Muchnik developed a new evidence technique calledPriority method or priority argument is known and which has become an important technique in computability theory.

history

Emil Post examined the Turing degrees in a work from 1944 and asked whether there are recursively enumerable Turing degrees between 0 and 0 ′ . This question became known as the Post's problem . Post defined the simple quantities and was able to show that under the many-one reduction these lie strictly between the decidable quantities and the holding problem, without being able to show this for the stronger Turing reduction as well. JCE Dekker showed in 1954 that this is impossible because there are simple sets in 0 ′ . The problem was solved independently by Friedberg and Muchnik in 1956/57 using the newly developed priority method. In 1986 Antonín Kučera published a new solution that did not need a priority argument.

proof

idea

The following proof follows Cooper's 2004 presentation and is based on the original proofs by Friedberg and Muchnik.

Simultaneously two recursively enumerable sets and are constructed, which are not Turing-reducible to one another: and . If these conditions are met, the statement of the sentence follows directly. Because if or were decidable , it could be Turing-reduced to the other set , and since all recursively enumerable sets are Turing-reducible to the holding problem , A and B cannot lie in 0 ′ either . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\not \leq _{T}B}$ ${\displaystyle B\not \leq _{T}A}$ ${\displaystyle A}$ ${\displaystyle B}$

These requirements are ensured by an infinite list of requirements. Be a calculable enumeration of the Oracle Turing machines . Then there are two requirements for each machine : ${\displaystyle \Phi _{0},\Phi _{1},\dotsc }$ ${\displaystyle \Phi _{i}}$

• ${\displaystyle R_{2i}}$: does not describe a Turing reduction from to . Formally: ${\displaystyle \Phi _{i}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\neq \Phi _{i}^{B}}$

• ${\displaystyle R_{2i+1}}$: does not describe a Turing reduction from to . Formally: ${\displaystyle \Phi _{i}}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B\neq \Phi _{i}^{A}}$

When all are satisfied there is no Turing reduction from to and it holds . The same applies if all are met. ${\displaystyle R_{2i}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\not \leq _{T}B}$ ${\displaystyle B\not \leq _{T}A}$ ${\displaystyle R_{2i+1}}$

The requirements are arranged according to their priority , so that the highest priority, the second highest, etc. ${\displaystyle R_{0}}$ ${\displaystyle R_{1}}$

There are predictable consequences of finite sets and constructed. A and B are then the infinite unions of these sequences: and . Since the consequences are computable, their associations and are recursively enumerable. ${\displaystyle A_{0}\subseteq A_{1}\subseteq A_{2}\subseteq \dotsb }$ ${\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \dotsb }$ ${\displaystyle A=\bigcup _{i\in \mathbb {N} }A_{i}}$ ${\displaystyle B=\bigcup _{i\in \mathbb {N} }B_{i}}$ ${\displaystyle A}$ ${\displaystyle B}$

It is . In the -th step of the construction from and the quantities and are constructed. The construction is done by strategies . Each of the requirements has a strategy that tries to meet that requirement. ${\displaystyle A_{0}=B_{0}=\emptyset }$ ${\displaystyle s+1}$ ${\displaystyle A_{s}}$ ${\displaystyle B_{s}}$ ${\displaystyle A_{s+1}\supseteq A_{s}}$ ${\displaystyle B_{s+1}\supseteq B_{s}}$

Strategies

intuition

Every strategy has to force an inequality to hold. There are two possibilities: either the strategy adds a witness to add that is not in lies or they will force it a witness out there in lies and never to come. There are two difficulties with this. For one, it is not always a total function and the question is therefore undecidable. This is solved by the fact that the strategy only carries out the first steps of the calculation in the -th step of the construction . If after steps holds, then the strategy will learn the value of in the -th step of the construction and can determine accordingly whether it gets after or not. Does not hold , then does not describe a total function and thus no Turing reduction. This is automatically fulfilled. ${\displaystyle R_{2i}}$ ${\displaystyle A\neq \Phi _{i}^{B}}$ ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle \Phi _{i}^{B}}$ ${\displaystyle x}$ ${\displaystyle \Phi _{i}^{B}}$ ${\displaystyle A}$ ${\displaystyle \Phi _{i}^{B}}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle t}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle t}$ ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle \Phi _{i}}$ ${\displaystyle R_{2i}}$

On the other hand, is not yet available during the construction of , since both sets are constructed simultaneously. Therefore the oracle machine receives as an oracle in the -th step instead of the finite set . An oracle ringing machine, if it holds, can only make a finite number of oracle requests. So it suffices to require that all later quantities on all numbers ( is the greatest oracle query in the computation of ) agree with to ensure that is. The strategy therefore stipulates a restriction, i.e. no strategy may add numbers in the future . ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle \Phi _{i}}$ ${\displaystyle s}$ ${\displaystyle B}$ ${\displaystyle B_{s}}$ ${\displaystyle B_{t}}$ ${\displaystyle x\leq k}$ ${\displaystyle k}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle B_{s}}$ ${\displaystyle \Phi _{i}^{B_{s}}(x)=\Phi _{i}^{B}(x)}$ ${\displaystyle k}$ ${\displaystyle B}$ ${\displaystyle R_{2i+1}}$ ${\displaystyle x\leq k}$ ${\displaystyle B}$

The strategies work completely analogously, with the roles of and reversed . These strategies can also introduce similar restrictions which restrict the strategies in the choice of witnesses. A restriction can now also make the witness of an already active strategy unusable if it is smaller than . The solution is that each strategy only respects those restrictions imposed by a higher priority strategy. If a strategy recognizes that it has been violated , that is, that a restriction it has set has been violated by a strategy of higher priority, it chooses a new witness and starts over. ${\displaystyle R_{2i+1}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle R_{2i}}$ ${\displaystyle k}$

Now it can be shown inductively as follows that every strategy is only violated a finite number of times, i.e. is finally fulfilled at some point. Since it has top priority, it is never hurt. Since there are only finitely many requirements with a higher priority for each , all of which are only violated finitely often according to the induction hypothesis, the violation is also only finitely often, since it can only be violated by strategies with higher priority. ${\displaystyle R_{0}}$ ${\displaystyle R_{s+1}}$ ${\displaystyle R_{s+1}}$

Formalization

Each requirement of the form has a strategy that can be procedurally represented as follows: ${\displaystyle R_{2i}}$

1. Pick a potential witness x for , where x is not yet in A, is above any higher priority A constraints, and has not already been elected as a witness. ${\displaystyle A\neq \Phi _{i}^{B}}$
2. In each later step , check if any of the following conditions apply: ${\displaystyle s}$
   1. x is under an A constraint with higher priority. In this case was injured and goes back to (1). ${\displaystyle R_{2i}}$
   2. ${\displaystyle A_{s}(x)=0=\Phi _{i}^{B_{s}}(x)[s]}$. In this case the strategy follows (3). It is the result of the first steps of calculating . ${\displaystyle \Phi _{i}^{B_{s}}(x)[s]}$ ${\displaystyle s}$ ${\displaystyle \Phi _{i}^{B_{s}}(x)}$
3. ${\displaystyle x}$is added to. ${\displaystyle A_{s+1}}$
4. Let z be the largest oracle query that was made while computing . Then the B constraint z is added. ${\displaystyle \Phi _{i}^{B_{s}}(x)}$
5. In each subsequent step , it is checked whether x is under an A constraint with higher priority. If so, the strategy goes back to (1). ${\displaystyle s}$

The requirements have analogous strategies in which A and B are swapped. ${\displaystyle R_{2i+1}}$

The strategy for the -th requirement begins its activity in the -th step of construction at (1). In each step, any strategy for running. This means that only a finite number of strategies have to be taken into account in each step. Because each strategy is predictable, therefore, as required of each and predictable. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle R_{k}}$ ${\displaystyle k\leq s}$ ${\displaystyle A_{s}}$ ${\displaystyle B_{s}}$

As shown above, each strategy is only violated a finite number of times. In addition, it must be shown that the requirement is met when the associated strategy is no longer violated. Since every strategy is only violated finitely often and goes back to (1), there are two possible results (shown here for , analogously for ): ${\displaystyle R_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{2i}}$ ${\displaystyle R_{2i+1}}$

• ${\displaystyle R_{2i}}$waits infinitely long at (2), d. H. is fulfilled for none . Then either is undefined or equal to 1. Since in is not in , is fulfilled in both cases . ${\displaystyle A_{s}(x)=0=\Phi _{i}^{B_{s}}(x)[s]}$ ${\displaystyle s}$ ${\displaystyle \Phi _{i}^{B}(x)}$ ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle R_{2i}}$
• ${\displaystyle R_{2i}}$achieved (5) without being injured again. Since in (3) was added to, is . On the other hand is . Because of the added B constraint, the relevant part of has not changed and . ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle A(x)=1}$ ${\displaystyle \Phi _{i}^{B_{s}}(x)=0}$ ${\displaystyle R_{2i}}$ ${\displaystyle B}$ ${\displaystyle \Phi _{i}^{B}(x)=\Phi _{i}^{B_{s}}(x)=0\neq A(x)}$

Similarly, it can be shown that all are fulfilled. ${\displaystyle R_{2i+1}}$

literature

• SB Cooper: Computability Theory . Chapman & Hall / CRC, 2004. ISBN 1-58-488237-9
• Richard M. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944) . In: Proceedings of the National Academy of Sciences . tape 43 , p. 236-238 ( pnas.org [PDF]).
• Antonín Kučera: An alternative, priority-free solution to Post's problem . In: Springer Lecture Notes in Computer Science . tape 233 , 1986, pp. 493-500 .
• AA Muchnik: On the unsolvability of the problem of reducibility in the theory of algorithms. (Russian) . In: Doklady Akademii Nauk SSSR (NS) . tape 108 , 1956, pp. 194-197 .

Individual evidence

1. ↑ JCEDekker: A theorem on hypersimple sets . In: Proceedings of the American Mathematical Society . tape 5 , 1954, pp. 791-796 .