[Elius]

Hola,

voy a usar un recurso no muy ortodoxo en su apariencia, aunque yo creo que desde el punto de vista lógico no trae problemas. Usemos la fórmula entrecomillada y entre llaves con el símbolo "#", en representación del código de la fórmula.

Entonces si N es el código de

\( \varphi_n(n) \)

(atención, n es una variable sin un valor asignado)

tenemos que volver a la definición inicial de la función con dos argumentos iguales (voy numerando los puntos que pueden ser conflictivos así los podemos citar):

1) \( \varphi_n(n) \) equivale \( \varphi(n, n) \), con n variable libre

2) El código de

\( \varphi(n, n) \)

es

#{\( \varphi(n, n) \)}

cuya abreviatura es N.

3) Una variable libre es como un casillero vacío, marquémoslo como "?"

#{\( \varphi(?, ?) \)}


4) Cuando queremos calcular

\( \varphi_n(n) \) reemplazando n por N,

nos encontramos que es

\( \varphi(N, N) \)

igual a

\( \varphi(\#\{"\varphi(?, ?)"\}, \#\{"\varphi(?, ?)"\}) \)

En este punto, vemos que \( \varphi \) no es que esté indefinida para un número natural determinado (sería un caso normal) sino que, EN EL SEGUNDO PASO, cuando debe buscar la función de la función de la función, no se proporciona el código de la misma, ni tampoco su argumento.

Entonces no podemos decir que está simplemente indefinida, que sería cuando sabemos cuál es la función, e incluso el argumento, pero ese argumento no está en el dominio de la función.

Puesto que no podemos llegar a ninguna conclusión acerca de \( \varphi_N(N) \), tampoco respecto de \( g(N) \), que se define exclusivamente en base a la primera.

Mi intención por ahora es que se entienda lo que planteo, no necesariamente que estén de acuerdo con ello.

Saludos!

P.D.: Encontré varios sitios que ofrecen el libro de Odifreddi, pero para bajarlo me piden que baje un exe y lo ejecute. Eso es peligroso, por eso no lo intento.

[Elius]

Aclaración sobre qué se entiende por "que una función esté definida".

\( \varphi(m, n) \)

es una función que se define a partir del conjunto numerable de las funciones recursivas. En ese sentido está "definida como función".

Luego, según los argumentos que se le pasen, hay tres estados de indefinición:

1) Reconstruímos la fórmula de la función \( f_m_0 \) a partir de su código, y la función \( f_m_0 \) no tiene a \( n_0 \) en su dominio.

2) Reconstruímos la fórmula de la función \( f_m_0 \) a partir de su código, pero su argumento es una variable libre ("n" no tiene valor asignado), por lo que no podemos decidir nada sobre su definición o indefinición.

3) No podemos reconstruir la fórmula de la función, porque m no tiene un valor asignado.

En estos casos, hay por lo menos tres actitudes posibles:

a) la conservadora, que dice: "demonios, es todo lo mismo, \( \varphi \) está indefinida, y Santas Pascuas!". Queda todo como hasta ahora.

b) la inquisitiva: coincide con a), pero nota que ya no puede hacerse la pregunta "¿y qué pasa con \( g \) cuando \( \varphi \) sí está definida?" porque para N nunca lo está.

c) la crítica: para sostener la demostración, hay que hacer una fuerte hipótesis explícita acerca de la equivalencia de los tres estados de indefinición, o bien volver a dejar el Halting Problem como problema abierto.


Saludos!

[Óscar Matzerath]

Hola,

Aclaración sobre qué se entiende por "que una función esté definida".

\( \varphi(m, n) \)

es una función que se define a partir del conjunto numerable de las funciones recursivas. En ese sentido está "definida como función".

Luego, según los argumentos que se le pasen, hay tres estados de indefinición:

1) Reconstruímos la fórmula de la función \( f_m_0 \) a partir de su código, y la función \( f_m_0 \) no tiene a \( n_0 \) en su dominio.

2) Reconstruímos la fórmula de la función \( f_m_0 \) a partir de su código, pero su argumento es una variable libre ("n" no tiene valor asignado), por lo que no podemos decidir nada sobre su definición o indefinición.

3) No podemos reconstruir la fórmula de la función, porque m no tiene un valor asignado.

Pero aquí no se dan las situaciones 2 y 3 en ningún momento. Yo siempre que miro cosas con \( \varphi(m,n) \) le doy valores a sus argumentos, en este caso, a ambos valores les introduzco N, el número natural que es código de g.

En cualquier caso, no sé qué le ves de raro a la función g. En la definición de g en ningún momento aparece \( \varphi_n(n) \), g se define explícitamente a partir de la función f(x,y), que suponemos que es recursiva. Por ejemplo, así: \( g(n)=\mu y (f(n,n)=y \wedge y=0) \).

En todo caso aparece \( \varphi_m(n) \) en la definición de f(x,y), pero que si no te gusta usa la función universal de la que hablaba antes y de la que tienes la construcción explícita, la dada por el teorema de la forma normal, que es exactamente lo mismo. Define f(x,y) así: \( f(x,y)=1 \) si \( F(x,y) \downarrow \) y \( f(x,y)=0 \) si \( F(x,y) \uparrow \). ¿Qué problema le ves? ¿Qué problema le ves a g, definida exclusivamente a partir de f?

Sigo pensando que tu problema es tomarte \( \varphi_n(n) \) sólo como eso, sin tener en cuenta que realmente es una función recursiva (la misma que F(n,n)). Sustituye en todas partes \( \varphi_n(n) \) por \( F(n,n) \) si quieres. ¿También afirmas que hay algún natural N para el que F(N,N) no tiene sentido? Entonces, ¿también piensas que la función F(x,y) es una función que está indefinida (en tu sentido) o que no sabes cual es para algunos valores de sus argumentos? Porque si es así, estás afirmando que al aplicar recursión primitiva o minimización o composición a funciones recursivas puedes no obtener una función recursiva.

Sobre el libro de Odifreddi,

Spoiler

http://ifile.it/c6lba5/__Classical_Recursion_Theory__The_Theory_of_Functions_and_Sets_of_Natural_Numbers_Vol_1__Studies_in_Logic_and_the_Foundations_of_Mathematics_Vol_125_.l_58x2j6o18x18x41.pdf

[cerrar]

Saludos

[Elius]

Óscar,
es el viejo tema acerca de si N es el código de \( \varphi(n,n) \), es el código de una fórmula abierta. Si eso es legítimo para tí, bueno, me parece bien, pero mi posición es la crítica, y no me parece aceptable. No creo que podamos llegar más lejos que eso.

Saludos!

[Óscar Matzerath]

Hola,

Pero, ¿si sustituyes en todas partes \( \varphi_n(n) \) por F(n,n) te parece bien ya, o todavía no?

Saludos

[Elius]

Ante todo te agradezco que pongas a prueba todo esto, es muy fatigoso, lo sé, y me resulta muy valioso no sólo para saber cómo exponer mejor lo que pienso, sino también para aclararme las ideas.

Sea F(n, n) la función universal de Kleene.

Sea \( N_0 \) el código de la fórmula que expresa F(n, n) (le agrego el subíndice para indicar que ya no es una variable, sino un número natural).

F(n, n) CALCULA el valor de la función cuyo código se le da en la variable "n", mientras que g(n) DECIDE (con algún artificio no especificado) si la función fn(n) para o no para.

Dime si hasta aquí (punto 1) estamos de acuerdo.

Cuando la función universal recibe \( N_0 \) como valor de su argumento, se produce la siguiente secuencia de operaciones:

operación N°     Función      Argumento 1     Argumento 2       Significado de la operación

1                F      cod(F(n, n))   cod(F(n, n))   Decodifica el primer argumento,
                           y lo usa para ubicar la función
                           que debe emular, y le pasa como
                           primer argumento el segundo recibido
2                F              cod(F(n, n))   ?            Igual que en 1, encuentra que la función
                           que debe emular, emula a su vez a otra
                           que está en el primer argumento
3                F      ?          ?          Igual que en 2, pero cuando
                           va a ubicar la función a emular,
                           no tiene cómo hacerlo porque
                           los argumentos no tienen valor asignado
4            ?              ?              ?              Situación no prevista por la definición
                           de la función

Esto es lo que veo.

Dime si por lo menos se entiende, aunque no estés de acuerdo, y en su caso, a partir de dónde dejas de estar de acuerdo.

Saludos!

[Óscar Matzerath]

Hola,

En lo de que una calcula y la otra decide... puedo estar de acuerdo, pero no es que una función calcule, la función es la que es, lo que pasa es que tienes un procedimiento para calcular la función F(n,n), (que consiste en descodificar las instrucciones para la función \( \varphi_n \) e imitar su algoritmo con entrada n). Mientras que de la g, aunque hay un algoritmo para calcularla (por hipótesis de ser recursiva) no sabemos nada sobre ella.

Sobre lo otro no, no estoy de acuerdo, y dejo de estarlo en el punto 2. \( h(n)=F(n,n) \) es una función de 1 variable con su código \( N_0 \).

Entonces la secuencia es:\(  h(N_0)=F(N_0,N_0) \) (este es el punto 1), pero como \( F(N_0,m)=h(m) \) para todo natural m, en particular \( F(N_0,N_0)=h(N_0)=F(N_0,N_0) \) y has vuelto al punto de partida. Si lo piensas computacionalmente, se entra en un bucle infinito, a nivel de funciones recursivas, una minimización que nunca termina (es lo mismo que ya discutimos en un hilo, pero ahora es en versión función recursiva). Lo que no le pasa nunca es quedarse sin argumentos, porque siempre es \( N_0 \). De todas maneras, lo que pretendes afirmar es cuestionable ya a un nivel de funciones (de teoría de conjuntos si quieres), pues me estás diciendo que hay una función recursiva de una variable, con una construcción explícita, que sin embargo está mal definida, sea lo que sea que eso signifique. Porque la pregunta aquí, sería si \( (N_0,N_0) \) está en el dominio de \( F \) o no, y sobre eso poca duda hay.

Saludos

PD: Es posible que esté algunos días sin entrar al foro. Ya seguiremos cuando vuelva, si no participa nadie más en el hilo.

[Elius]

Entonces la secuencia es:\(  h(N_0)=F(N_0,N_0) \) (este es el punto 1), pero como \( F(N_0,m)=h(m) \) para todo natural m, en particular \( F(N_0,N_0)=h(N_0)=F(N_0,N_0) \) y has vuelto al punto de partida. Si lo piensas computacionalmente, se entra en un bucle infinito, a nivel de funciones recursivas, una minimización que nunca termina (es lo mismo que ya discutimos en un hilo, pero ahora es en versión función recursiva). Lo que no le pasa nunca es quedarse sin argumentos, porque siempre es \( N_0 \).

Bien, te tomo la palabra, y acepto que \(  h(N_0)=F(N_0,N_0) \) esté bien definida como tal función, pero su valor es indefinido (una minimización que nunca termina).

Entonces ya tienes la mitad del teorema de Turing:

\( F(N_0,N_0)\uparrow \Longrightarrow{} h(N_0)\uparrow \)

por ser

\( F(N_0,N_0) \approx{} h(N_0) \)

Pero por definición de h(n),

\( F(N_0,N_0)\uparrow \Longleftrightarrow{} h(N_0)\downarrow \)

por lo tanto

\( h(N_0)\uparrow \Longrightarrow{} h(N_0)\downarrow \)

Es decir, NO SE PUEDE SUPONER QUE h no pare con su propio código sin entrar en contradicción.

Pero, ¿cómo obtenemos la dirección inversa de la contradicción? Es decir ¿qué pasa si suponemos que h para con su propio código? No podemos recurrir a \( F(N_0, N_0)\downarrow \) pues ya sabemos que no para con \( N_0 \).

Sólo quedaría como conclusión, que, si existe, h para con su propio código.

PD: Es posible que esté algunos días sin entrar al foro. Ya seguiremos cuando vuelva, si no participa nadie más en el hilo.

Buen descanso.

Saludos!