Primero explicaré lo que ocurre en el lenguaje del documento de Friedberg. Pero quiero dejar claro que no creo que el documento de Friedberg sea el mejor lugar para aprender esta prueba. Estoy de acuerdo en que es sorprendentemente legible, pero eso no significa que no haya una exposición mejor en los últimos 60 años. Así que también intentaré explicar en un lenguaje más moderno (e informal) lo que ocurre en la prueba y señalar algunas otras referencias donde se puede aprender más sobre ella.
En el lenguaje del documento de Friedberg
En general, $T_1^{f}(e_a, x_1^a(e_a), y)$ sólo depende de la primera $y$ valores de $f$ . Y $T_2^{f_2^{a}}(e_a, x_1^a(e_a), y)$ se mantiene. Pero $f_2$ es sólo el límite puntual de $f_2^{a'}$ . Así que la única manera $T_1^{f_2}(e_a, x_1^a(e_a), y)$ puede fallar es si por alguna $a' > a$ , $f_2^{a'}$ no está de acuerdo con $f_2^a$ en alguna entrada $x\leq y$ . Esto ya lo has escrito en tu pregunta.
El siguiente punto es que la única vez en la construcción que $f_2^{a' + 1}(x)$ se puede hacer que no esté de acuerdo con $f_2^{a'}(x)$ es si el subcaso 2.1 ocurre en la etapa $a' + 1$ . Además, cuando el subcaso 2.1 se produce en la etapa $a' + 1$ El único desacuerdo entre $f_2^{a' + 1}$ y $f_2^{a'}$ estará en la entrada $x_2^{a'}(e_{a' + 1})$ . Supongamos por un momento que para todos los $a' \geq a$ de manera que el subcaso 2.1 se produzca en la etapa $a' + 1$ , $x_2^{a'}(e_{a' + 1}) > y$ . Entonces, para cualquier $x \leq y$ tendríamos: $$ f_2^a(x) = f_2^{a+1}(x) = f_2^{a+2}(x) = f_2^{a+3}(x) = \cdots $$
El último punto es el más importante y quizá el más fácil de pasar por alto al leer el documento. La cuestión es que en la etapa $a$ fijamos $x_2^a(e)$ sea mayor que $y$ para todos $e \geq e_a$ y en ningún momento de la construcción se $x^{a' + 1}_2(e)$ siempre menos que $x^{a'}_2(e)$ . Así que para todos $a' > a$ y todos $e \geq e_a$ , $x_2^{a'}(e)$ es mayor que $y$ . El hecho de que establezcamos $x_2^a(e)$ sea mayor que $y$ para todos $e \geq e_a$ en el escenario $a$ es fácil de pasar por alto porque el documento parece decir que fijamos $x_2^a(e)$ mayor que $a$ . Sin embargo, si lee con atención verá que $y$ es como máximo $a$ .
Ahora tenemos todas las piezas para explicar el comentario de Friedberg: $T_1^{f_2}(e_a, x_1^a(e_a), y)$ sólo puede estar en desacuerdo con $T_1^{f_2^a}(e_a, x_1^a(e_a), y)$ si para algunos $a' > a$ , $f_2^{a'}$ no está de acuerdo con $f_2^a$ en alguna entrada $x\leq y$ . Y esto sólo puede ocurrir si por alguna $a' \geq a$ El subcaso 2.1 se produce en la fase $a' + 1$ y $x_2{a'}(e_{a' + 1}) < y$ . Y esto sólo puede ocurrir cuando $e_{a' + 1} < e_a$ .
En un lenguaje más moderno e informal
La idea principal de la prueba de Freidberg es algo que ahora se llama argumento de la prioridad del perjuicio finito. Permítanme que intente explicar la idea. Queremos construir conjuntos r.e. y tenemos un montón de requisitos que cumplir. En este caso, queremos construir conjuntos e.r. $A_1$ y $A_2$ de tal manera que ninguno de ellos computa el otro. Así que los requisitos son que para cada $e$ El $e^\text{th}$ máquina con oráculo $A_2$ no computa $A_1$ y viceversa. Una forma de asegurar esto es encontrar algún $x_e$ y $y_e$ tal que $\Phi_e^{A_2}(x_e) \neq A_1(x_e)$ y $\Phi_e^{A_1}(y_e) \neq A_2(y_e)$ . Por cierto, estoy usando $\Phi_e^{A_2}(x_e)$ para denotar la salida del $e^\text{th}$ máquina con oráculo $A_2$ en la entrada $x_e$ y cuando digo que no es igual a $A_1(x_e)$ Me refiero a que o bien diverge o converge y no es igual a $A_1(x_e)$ (y por $A_1(x_e)$ Me refiero a la salida de la función indicadora de $A_1$ en la entrada $x_e$ ).
Una forma de intentar cumplir con uno de estos requisitos es simplemente poner $x_e = e$ y preguntar si hay alguna forma de modificar $A_2$ para hacer $\Phi_e^{A_2}(e)$ convergen. Si no es así, no hay ningún problema. Si es así, modifique $A_2$ para hacer $\Phi_e^{A_2}(e)$ convergen y fijan $A_1(e)$ para no estar de acuerdo con lo que has hecho $\Phi_e^{A_2}(e)$ convergen a.
El primer problema de esto es que no nos da un conjunto de e.r. Así que la primera modificación que podemos hacer a esta construcción es construir $A_1$ y $A_2$ por etapas. Al principio, $e$ no está en $A_1$ . Si en algún momento vemos una forma de añadir elementos a $A_2$ para hacer $\Phi_e^{A_2}(e)$ convergen entonces lo hacemos (recuerde que para asegurarse $A_2$ es decir, sólo podemos añadir elementos en una etapa, no eliminarlos). A continuación, añadimos esos elementos a $A_2$ . Si eso causó $\Phi_e^{A_2}(e)$ para converger a $1$ entonces nos aseguramos de no poner nunca $e$ en $A_1$ . Si por el contrario causara $\Phi_e^{A_2}(e)$ para converger a $0$ entonces ponemos $e$ en $A_1$ .
Eso funcionó para encontrar conjuntos de e.r. que satisficieran un de los requisitos, pero pronto nos encontramos con problemas si intentamos hacer una sola construcción utilizando esta estrategia para satisfacer varios requisitos a la vez. Supongamos que satisfacemos uno de los requisitos poniendo $e$ en $A_1$ porque vimos que $\Phi_e^{A_2}(e)$ convergió y fue igual a $0$ . Pero ahora supongamos que al tratar de satisfacer algún otro requisito queremos añadir algún $a$ a $A_2$ y una vez que añadimos $a$ a $A_2$ , $\Phi_e^{A_2}(e)$ converge a $1$ en lugar de $0$ . Entonces hemos destruido el desacuerdo entre $A_1$ y $\Phi_e^{A_2}$ . Así que tenemos algún conflicto entre diferentes tipos de requisitos.
¿Cómo decidimos qué requisito tiene prioridad? La idea básica del argumento de la prioridad de la lesión finita es que damos una prioridad a cada requisito al principio de la construcción y el requisito con la mejor prioridad siempre tendrá prioridad. Por tanto, incluso después de pensar que hemos satisfecho algún requisito, existe la posibilidad de que en una fase posterior lo estropeemos para satisfacer un requisito con mejor prioridad. La "lesión finita" en el "argumento de prioridad de lesión finita" proviene del hecho de que hemos configurado la construcción para garantizar que sólo estropeamos un requisito ("lo lesionamos") un número finito de veces. Para ello, nos aseguramos de que para cada requisito sólo hay un número finito de requisitos con mejor prioridad y cada requisito sólo estropeará los requisitos de mayor prioridad un número finito de veces (en el argumento de Friedberg, sólo una vez) a menos que él mismo se estropee de nuevo. Así que el requisito con la mejor prioridad estropea los requisitos de peor prioridad un número finito de veces y luego se detiene, después el segundo requisito de mejor prioridad estropea los requisitos de peor prioridad como máximo un número finito de veces más y luego se detiene, y así sucesivamente. Al final, cada requisito no se volverá a estropear.
En la demostración del teorema de Friedberg-Muchnik, supongamos que un requisito de la forma $\Phi_e^{A_2} \neq A_1$ se ve alterado por un requisito con mayor prioridad. Tal vez hayamos visto $\Phi_e^{A_2}(e)$ convergen a $0$ y luego poner $e$ en $A_1$ pero en una etapa posterior, una mejor exigencia de prioridad puso algo en $A_2$ y ahora $\Phi_e^{A_2}(e)$ converge a $1$ . No podemos tomar $e$ de $A_1$ (queremos mantener $A_1$ r.e.) por lo que puede que no haya forma de asegurar $\Phi_e^{A_2}(e) \neq A_1(e)$ . Sin embargo, podemos solucionar esto simplemente eligiendo un número mayor $x_e$ que aún no está en $A_1$ y ahora esperar a que $\Phi_e^{A_2}(x_e)$ para converger. Cada vez que la exigencia se vea perjudicada, es posible que tengamos que aumentar el tamaño de $x_e$ . Pero como el requisito sólo se lesiona finitamente muchas veces, finalmente no tendremos que aumentar $x_e$ más y entonces, una vez que satisfacemos el requisito, éste permanecerá satisfecho.
Por supuesto, esta no es una descripción completa de la construcción, pero esa es la idea principal.
¿Cómo se relaciona esto con la parte confusa del documento de Friedberg?
La parte del documento de Friedberg que te ha confundido es esencialmente la explicación de por qué sólo los requisitos con mejor prioridad pueden perjudicar al requisito que etapa $a$ estaba tratando de satisfacer.
Otras referencias
Como he dicho, creo que hay mejores lugares para leer sobre la demostración del teorema de Friedberg-Muchnik que lo explicarán de una manera más conceptual con una notación menos abrumadora y también explicarán el concepto general de los argumentos de prioridad de perjuicio finito y darán otros ejemplos de argumentos de prioridad de perjuicio finito para comparar. Hay muchas fuentes para esto, pero dos que creo que pueden ser útiles son:
- El libro de Soare Computabilidad de Turing: Teoría y aplicaciones
- El libro de Hirschfeldt y Downey Aleatoriedad y complejidad algorítmica , específicamente el capítulo 2, "Teoría de la Computabilidad"
