Return to Question

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. (The result proven is that there are two recursively enumerable sets neither of which is Turing reducible to the other.) The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

• Definitions: $\Omega \left( x \right) $ denotes the number of prime factors of $x$. If $h:\mathbb{N}\rightarrow\mathbb{N}$ is a function, then $\phi^h_i(x)$ denotes the output (if it exists) of the $i^{th}$ Turing machine having access to $h$ as an oracle running on input $x$. And $\phi^h_{i,t}(x)$ denotes th output (if it exists) of the same Turing machine running for only $t$ steps and having access to only the first $t$ values of $h$.

• Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

• Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e > \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$ And the theorem is that the set of all $x$ such that $f(x)=1$ and the set of all $x$ such that $g(x)=1$ are recursively enumerable sets neither of which is Turing reducible to the other.

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\phi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?

EDIT: The specific part of the proof of Lemma II I can’t make sense of is the sentence beginning with “No occurrence beginning with...”. I posted a question related to this on Math.SE But an alternate proof of this Lemma would also be fine with me.

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. (The result proven is that there are two recursively enumerable sets neither of which is Turing reducible to the other.) The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

• Definitions: $\Omega \left( x \right) $ denotes the number of prime factors of $x$. If $h:\mathbb{N}\rightarrow\mathbb{N}$ is a function, then $\varphi^h_i(x)$ denotes the output (if it exists) of the $i^{th}$ Turing machine having access to $h$ as an oracle running on input $x$. And $\varphi^h_{i,t}(x)$ denotes th output (if it exists) of the same Turing machine running for only $t$ steps and having access to only the first $t$ values of $h$.

• Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

• Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e > \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$ And the theorem is that the set of all $x$ such that $f(x)=1$ and the set of all $x$ such that $g(x)=1$ are recursively enumerable sets neither of which is Turing reducible to the other.

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\varphi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?

EDIT: The specific part of the proof of Lemma II I can’t make sense of is the sentence beginning with “No occurrence beginning with...”. I posted a question related to this on Math.SE But an alternate proof of this Lemma would also be fine with me.

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

• Definition: $\Omega \left( x \right) $ denotes the number of prime factors of $x$

• Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

• Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e > \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\phi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. (The result proven is that there are two recursively enumerable sets neither of which is Turing reducible to the other.) The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

• Definitions: $\Omega \left( x \right) $ denotes the number of prime factors of $x$. If $h:\mathbb{N}\rightarrow\mathbb{N}$ is a function, then $\phi^h_i(x)$ denotes the output (if it exists) of the $i^{th}$ Turing machine having access to $h$ as an oracle running on input $x$. And $\phi^h_{i,t}(x)$ denotes th output (if it exists) of the same Turing machine running for only $t$ steps and having access to only the first $t$ values of $h$.

• Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

• Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e > \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$ And the theorem is that the set of all $x$ such that $f(x)=1$ and the set of all $x$ such that $g(x)=1$ are recursively enumerable sets neither of which is Turing reducible to the other.

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\phi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?

EDIT: The specific part of the proof of Lemma II I can’t make sense of is the sentence beginning with “No occurrence beginning with...”. I posted a question related to this on Math.SE But an alternate proof of this Lemma would also be fine with me.

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

• Definition: $\Omega \left( x \right) $ denotes the number of prime factors of $x$

• Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

• Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\phi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. The paper is actually surprisingly understandable once you get past the notation, except for one part that I can’t quite make sense of. But first, let me write the construction in modern notation:

• Definition: $\Omega \left( x \right) $ denotes the number of prime factors of $x$

• Stage $s=0$: Let $ f_{0} \left( x \right) =g_{0} \left( x \right) =1$ and $u_{0}(e) =v_{0}(e) =2^{e} $.

• Stage $s=2n+1$: If $f_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{g_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ f_{s-1}(x)& otherwise \\ \end{cases}, g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right), v_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e \geq \Omega \left( n \right) \\ v_{s-1}(e)& otherwise \\ \end{cases} $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left( e \right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• Stage $s=2n+2$: If $g_{s-1} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1$ and $ \varphi _{ \Omega \left( n \right) ,s}^{f_{s-1}} \left( u_{s-1} \left( \Omega \left( n \right) \right) \right) =1 $, then let $$f_{s} \left( x \right) =f_{s-1} \left( x \right), g_s(x)=\begin{cases} 0 & x= u_{s-1} ( \Omega ( n ) ) \\ g_{s-1}(x)& otherwise \\ \end{cases}, u_s(e)=\begin{cases} 2^{e} \left( 2s+1 \right) & e > \Omega \left( n \right) \\ u_{s-1}(e)& otherwise \\ \end{cases}, v_{s} \left( e \right) =v_{s-1} \left( e \right) $$ If not, let $$f_{s} \left( x \right) =f_{s-1} \left( x \right) ,g_{s} \left( x \right) =g_{s-1} \left( x \right) ,u_{s} \left(e\right) =u_{s-1} \left( e \right) , v_{s} \left( e \right) =v_{s-1} \left( e \right)$$

• End Result: Let $$ f \left( x \right) =\lim_{s \rightarrow \infty}f_{s} \left( x \right) ,g \left( x \right) =\lim_{s \rightarrow \infty}g_{s} \left( x \right) ,u \left( x \right) =\lim_{s \rightarrow \infty}u_{s} \left( x \right) ,v \left( x \right) =\lim_{s \rightarrow \infty}v_{s} \left( x \right) $$

Now the part I don’t understand is the proof of the following Lemma that Friedberg proves:

If $f(u(e))=0$, then $\phi^g_e(u(e))=1$

(If you look at the paper, it’s one direction of Lemma II.) So can anyone explain how to prove this result, either explaining Friedberg’s proof of it or proving it some other way?