[Carlos Ivorra]

Ahora necesito que me aclaren algo. ¿El número n es:
a) el código de V
o
b) puede ser el código de una máquina cualquiera?

Pues depende en qué frase. El el punto 3), donde defino la máquina rebautizada como V, digo que V es una máquina que cuando empieza con una cinta en la que hay escritos m+1 unos, un cero y n+1 unos, entonces V hace los (hipotéticos) cálculos necesarios para determinar la la máquina de Turing de código m termina o no cuando su input son n unos. Aquí m es el código de una máquina cualquiera y n es un número natural cualquiera.

En la descripción de la máquina M, el número n es un número natural cualquiera, y lo que hace M cuando se encuentra n+1 unos escritos en la cinta es escribir otra serie de n+1 unos, luego hacer actuar a V y luego parar o no parar en función del resultado de V. Aquí n es en principio un número natural cualquiera, luego M duplica ese n y V interpreta el primero como el código de una máquina de Turing y el segundo como un número (no un código de nada, sino un mero número) que constituye el input de la máquina \( M_n \).

Por último, cuando se trata de probar que la máquina M es contradictoria, particularizamos el n que hasta aquí era arbitrario al código de la máquina M (OJO: no de V, sino de M) y vemos que cuando la hipotética máquina M se encuentra con el input n tenemos una situación imposible.

Sigo sin entender en qué punto concreto está tu objeción: ¿Estás de acuerdo al menos en que de lo que se trata es de probar que no puede existir una máquina V como la descrita en el punto 3) de mi post anterior (allí llamada U), o ahí ya discrepas?

[Elius]

Carlos,
estoy de acuerdo filosóficamente en la imposibilidad de construir una máquina como  la U del paso 3 de tu mensaje. Es la demostración de Turing, y en particular, la autoaplicación la que me parece dudosa (la aplicación de un código a su máquina), al igual que la autoreferencia, y la demostración por el absurdo abusada a rajatabla, que lleva a resultados como el de los modelos no standard, cuyos números "existen" pero no son computables ni siquiera con aproximaciones (paso 5 de tu mensaje).

Con la respuesta que me han dado tú y Óscar, estoy elaborando una exposición precisa de mi objeción a ese punto, que postearé más tarde.

Saludos!

[Elius]

Está claro que la máquina U no es una máquina universal de Turing (sigo usando U en vez de V para mantener la compatibilidad con los mensajes anteriores). Ahora bien, no usa su input como un número liso y llano: el primer input es el código de una MT, y U debe interpretarlo, para predecir si para o no con el segundo input. Puesto que el primer input es el cód de una MT que para o no dependiendo de su input, debe interpretar (ya que no emular o imitar) el comportamiento de esa MT, llamémosla Mn(in1, in2).

Puesto que el segundo input en el caso que nos ocupa es también el cód de Mn(in1, in2), V debe interpretar el comportamiento de Mn(cod(Mn(??, ??)), ??). Obviamente, no puede producir ningún output, porque carece de datos para sus máquinas-argumento.

Respecto a lo que dice Óscar:

... n sí es un número liso y llano. U toma dos números (lisos y llanos) como inputs, m y n, y te da como output un 1 si la máquina codificada por el natural m para cuando se inicia con input n, y un 0 si no para.

En particular, U(n,n)=1 si y sólo si la máquina de Turing con código n para cuando se le introduce como input el número n. Es decir, si \( M_n(n) \) para. Fíjate que hay una asimetría entre el papel del primer input de U y el segundo: el primero se interpreta como el código de una máquina de Turing, mientras que el segundo es un número sin más. Pero esto no depende del número en sí (que no es más que un número, 25 por ejemplo), sino del "programa" de U.
Tal vez lo veas más claro con un ejemplo concreto: \( U(25,25)=1 \) si y solo si \( M_{25}(25) \) para, y está claro que 25 es un input aceptable para la máquina de Turing \( M_{25} \), por tanto esta o bien parará o bien no parará.

es cierto que la máquina U interpreta el primer input como programa, y el segundo como número sin más. Pero al interpretar su primer input, éste requiere a su vez que su primer input sea un programa, y allí se produce una situación no prevista, porque no es una parada normal, ni es una ejecución interminable. Simplemente no se puede seguir interpretando por falta de input. Luego U no puede responder ni 1 ni 0.

Otra cosa sería si 25 fuera simplemente un subíndice. Pero no es el caso, pues la primera vez se toma como el código de la máquina: "Fíjate que hay una asimetría entre el papel del primer input de U y el segundo: el primero se interpreta como el código de una máquina de Turing, mientras que el segundo es un número sin más."
Esta asimetría se pierde cuando se debe interpretar el código que toma como primer input de Mn ese segundo input de U, y lo interpreta como programa.

El caso es asimilable a lo que sucede si en el Teorema de Indecibilidad de Gödel, no se usara la función de diagonalización:

\( \forall{y} - Dem \: y \: \alpha  \)

siendo \( \alpha  \) el nro. de Gödel de la fórmula

\( \forall{y} - Dem \: y \: x  \)


El nro. de Gödel corresponde a una fórmula con una variable libre, y en ese caso no hay nada incompleto.

Saludos!

[Carlos Ivorra]

Está claro que la máquina U no es una máquina universal de Turing (sigo usando U en vez de V para mantener la compatibilidad con los mensajes anteriores). Ahora bien, no usa su input como un número liso y llano: el primer input es el código de una MT, y U debe interpretarlo, para predecir si para o no con el segundo input. Puesto que el primer input es el cód de una MT que para o no dependiendo de su input, debe interpretar (ya que no emular o imitar) el comportamiento de esa MT, llamémosla Mn(in1, in2).

No. De acuerdo en todo salvo lo que te pongo en negrita. Cuando empieza a actuar U, lo que debe hacer es estudiar el comportamiento de la máquina \( M_n \) cuando se le da un único input, no dos. Creo que ya entiendo lo que te confunde:

Una máquina de Turing es un programa que puede empezar a actuar con una cinta marcada con unos y ceros (podríamos poner más signos, pero sería equivalente) con sólo un número finito de unos. En particular, la puedes poner a trabajar con una cinta en la que haya escrita una única sucesión de unos que codifique a un número n, o bien dos sucesiones consecutivas de unos separadas por un cero que codifiquen a dos números m y n, etc. Y siempre es la misma máquina actuando ante cintas con datos distintos. Tu error parece ser que crees que hay máquinas de Turing que requieren un argumento, y otras que requieren dos argumentos, etc., cuando en realidad cualquier máquina de Turing puede empezar a calcular con una cinta en la que haya cualquier conjunto finito de sucesiones de unos, separados por un cero, o incluso cualquier disposición caótica de unos y ceros que no codifique ninguna n-tupla de números naturales.

Así pues, aunque estamos considerando una máquina M descrita por su acción sobre dos argumentos, si su código es n, de modo que \( M=M_n \), y le damos a U la entrada n, n, lo que tiene que hacer U no es estudiar qué hara \( M = M_n \) cuando se le den dos argumentos (en cuyo caso tendrías razón tú, y faltaría uno) sino que su misión es estudiar qué hará \( M=M_n \) cuando se le dé un único argumento.

Lo que creo que te confunde es que no eres consciente de que M, como cualquier otra máquina de Turing, algo hará si se encuentra con una cinta con n+1 unos escritos, y el problema de U es determinar qué hará M en ese caso, y el hecho de que hayamos construido M pensando en hacerla actuar sobre pares de números naturales no implica que no tenga sentido ver qué le pasa a M cuando actúa sobre un único número natural.

Edito: Aquí me he liado yo mismo: de hecho, M ha sido diseñada pensando en hacerla actuar sobre un único argumento, con lo cual todavía tiene menos sentido lo que planteas, pues al tomar el código n que hace que \( M=M_n \) lo que tiene que hacer \( U \) es estudiar si \( M \) se para o no se para cuando se le da n como único argumento, con lo que no estamos cambiando "el número pretendido de argumentos", sino que éste era 1 desde el principio y 1 sigue siendo.


Ahora entiendo lo que decías sobre que una máquina de Turing puede no poder empezar a calcular porque le falte un argumento. Fíjate que eso es absurdo: Toda máquina de Turing se pone a actuar ante cualquier configuración de la cinta, en particular si en ella hay un único número natural escrito.

En resumen: aunque M ha sido definida como una máquina cuyo comportamiento ante dos argumentos es el que hemos descrito, lo que tiene que hacer U al estudiar M es ver qué le sucede (si se para o no) cuando se le da un único argumento (su propio código n), que, desde luego, no tendrá nada que ver con lo que hemos pensado a la hora de construirla, ni falta que hace. La máquina M puede actuar con la cinta en blanco, con un argumento, con dos, con tres o con los que sea. La hemos construido pensando en su posible actuación con dos argumentos, y luego U estudia su posible actuación con un argumento.

Bueno, creo que ya me estoy repitiendo como un loro. Piensa a ver si estás de acuerdo en que esto lo aclara todo.

[Elius]

Carlos,
gracias por la respuesta.
Disculpa mi insistencia, pero fíjate que al transformarla en una máquina con un solo input, lo único que se hace es duplicar su input (en el sentido de hacer una copia y no multiplicar el número por 2), y luego sigue actuando como antes.

Me sorprende lo que dices, que una MT actúa siempre. ¿No consideras el caso en que carece de instrucciones para un input determinado?

Claro que se podría dar instrucciones a una MT para que en caso de tener menos argumentos, actúe igualmente, pero es una modificación ad hoc, no el caso general.

Pero aún así, si toma un solo argumento sin duplicarlo, es una MT que para cuando no tiene más input. En ese caso, no hay dos posibilidades: pararía siempre, y U daría siempre 1 como output.

Saludos!

PD: no creo que te estés repitiendo, el argumento acerca de que una MT puede actuar aún si no se le proporciona el input estipulado es nuevo, y el de U estudiando a una MT con dos inputs como si tuviera uno solo, también.

[Carlos Ivorra]

Elius: tu último mensaje deja bien claro que tienes una confusión muy grave en torno al concepto de máquina de Turing. Veamos:

Disculpa mi insistencia, pero fíjate que al transformarla en una máquina con un solo input, lo único que se hace es duplicar su input, y luego sigue actuando como antes.

No, no. Nadie transforma nada. No hablo de tomar una máquina de Turing "de dos imputs" (esto ya es un sinsentido) y "transformarla" en una "de un input" duplicando el input. No tiene nada que ver con eso. Queda claro que piensas que hay máquinas de un input, máquinas de dos, etc. y eso es totalmente erróneo.

Me sorprende lo que dices, que una MT actúa siempre. ¿No consideras el caso en que carece de instrucciones para un input determinado?

Claro que se podría dar instrucciones a una MT para que en caso de tener menos argumentos, actúe igualmente, pero es una modificación ad hoc, no el caso general.

No, no, no y mil veces no. Para aclarar estas confusiones hay que ir a la propia definición de máquina de Turing. Una máquina de Turing está definida por un número finito de estados \( E_0,\ldots , E_n \), de los cuales uno de ellos es, por definición, el estado inicial \( E_0 \) y otro es por definición el estado final \( E_n \), tal que si la máquina llega a ese estado se para.

Para cualquier estado que no sea el final, la máquina dispone de unas instrucciones muy concretas, que le especifican qué debe hacer en el caso en que en la casilla que está leyendo en la cinta haya un 0 o un 1. Dichas instrucciones sólo especifican si, en cada uno de los casos, la máquina debe escribir un 0 o un 1 en la cinta, si debe moverse a la casilla anterior o posterior de la cinta y a qué nuevo estado debe pasar a continuación. Ya está. Eso es todo lo que determina una máquina de Turing.

Por lo tanto, si pones a una máquina de Turing en una casilla de la cinta en su estado inicial, la máquina hará algo: mirará si en la casilla hay un 0 o un 1, escribirá en la cinta el número que dicte el estado inicial según el caso, moverá la cinta una posición hacia adelante o hacia atrás y pasará al estado especificado por su estado inicial según que en la cinta hubiera un 0 o un 1. A continuación seguirá las instrucciones del estado correspondiente, y así sucesivamente hasta que llegue al estado final, si es que llega.

Por lo tanto, es absolutamente imposible que una máquina de Turing no pueda actuar por falta de datos. Y no es necesaria ninguna modificación ad hoc porque ese caso jamás puede darse.

En particular, no hay máquinas de Turing de un input, y de dos, y de tres, sino que a cualquier máquina de Turing la puedes poner en una cinta con un número, con dos, con tres, o con una configuración caótica, y hará lo que tenga que hacer según su programa.

Pero aún así, si toma un solo argumento sin duplicarlo, es una MT que para cuando no tiene más input. En ese caso, no hay dos posibilidades: pararía siempre, y U daría siempre 1 como output.

No, no. Si tienes una máquina de Turing y le das como input un número natural, hará algo, y si la misma máquina de Turing (sin transformarla de ninguna forma) la pones ante una cinta con dos números naturales, hará otra cosa que, en principio, no tiene nada que ver con lo que hace cuando le pones sólo uno. No puedes predecir lo que hará una máquina de Turing ante dos imputs a partir de que sepas lo que hace cuando le das uno, ni viceversa. El asunto no es trivial en absoluto.

Insisto en que debes asimilar que en un programa de una máquina de Turing no hay, ni puede haber, nada que especifique una configuración inicial de la cinta (en particular un número de argumentos) como condición necesaria para que el programa pueda actuar. Lo máximo que puedes hacer es programar una máquina de Turing para que se comporte de una forma deseada en el supuesto de que se encuentre con una cinta con un número prefijado de argumentos, pero has de tener presente que  la máquina que programes actuará de una forma u otra (que no es posible predecir a priori a partir del comportamiento conocido en el caso en el que los argumentos son los previstos) cuando en la cinta haya una configuración arbitraria.

[Carlos Ivorra]

Acabo de corregir mi penúltimo mensaje (antes de éste). Al final, yo mismo me había liado con el número de argumentos de cada máquina de Turing. La respuesta al mensaje anterior al que he rectificado era más fácil que la que yo te había dado, pues, al fin y al cabo, n no es el código de una máquina de Turing diseñada para actuar sobre dos argumentos, sino el código de una máquina diseñada para actuar sobre un único argumento.

De todos modos, creo que ha sido buena cosa mi confusión, porque ha sacado a la luz una confusión importante: una cosa es que se diseñe una máquina para actuar sobre un número pretendido de argumentos, y otra cosa que la máquina diseñada con tal fin no pueda actuar (de forma no previsible aunque podamos prever su comportamiento ante el número previsto de argumentos) sobre una cinta con cualquier número de argumentos. Este hecho no era necesario para refutar tu argumento, pero en cualquier caso es fundamental tenerlo claro.

[Elius]

Carlos,
creo que tenemos un problema de terminología. Es claro que la MT abstracta tiene un solo dispositivo de input, que es una cinta infinita dividida en celdillas.

Pero en él puede venir un número variable de números, que serán tomados como argumentos de partida para cada máquina en particular.

Lo importante es que nos pongamos de acuerdo en esto:

1) Cuando U recibe como input k, escribe 1 si Mk para con el input k, y 0 si no lo hace.

2) Si n es el código de la máquina H descripta antes, U interpreta el código de H con el input del código de H, para predecir si para o no.

Creo que en eso podemos estar de acuerdo, ¿no es así?

Saludos

[Carlos Ivorra]

Carlos,
creo que tenemos un problema de terminología. Es claro que la MT abstracta tiene un solo dispositivo de input, que es una cinta infinita dividida en celdillas.

Pero en él puede venir un número variable de números, que serán tomados como argumentos de partida para cada máquina en particular.

Sí, pero una misma máquina hará una cosa u otra según que en la cinta con un número, o con dos, o con tres.  No puedes decir "esta máquina sólo sabe calcular si se le dan dos números".

Lo importante es que nos pongamos de acuerdo en esto:

1) Cuando U recibe como input k, escribe 1 si Mk para con el input k, y 0 si no lo hace.

No, eso no es cierto. Cuando la máquina U recibe dos números como input, digamos k y m, escribe 1 si la máquina \( M_k \) para con input \( m \) y 0 en caso contrario. Si a la máquina U le suministras como input un único número k, su comportamiento es absolutamente impredecible. Podríamos estudiarlo analizando el código de U, pero como U es una máquina hipotética que no existe, no tenemos esa opción, por lo que no podemos afirmar absolutamente nada sobre lo que haría U en caso de empezar con una cinta con un único número como input. No podemos estar de acuerdo en lo que dices.

2) Si n es el código de la máquina H descripta antes, U interpreta el código de H con el input del código de H, para predecir si para o no.

Supongo que cuando dices H te refieres a la máquina que yo llamaba M. En tal caso, lo que dices es correcto entendiendo que, cuando  U actúa como parte del programa de M, en el momento en que empieza se encuentra con una cinta con dos números iguales, no con un único número.

[Elius]

Lo importante es que nos pongamos de acuerdo en esto:

1) Cuando U recibe como input k, escribe 1 si Mk para con el input k, y 0 si no lo hace.

No, eso no es cierto. Cuando la máquina U recibe dos números como input, digamos k y m, escribe 1 si la máquina \( M_k \) para con input \( m \) y 0 en caso contrario. Si a la máquina U le suministras como input un único número k, su comportamiento es absolutamente impredecible. Podríamos estudiarlo analizando el código de U, pero como U es una máquina hipotética que no existe, no tenemos esa opción, por lo que no podemos afirmar absolutamente nada sobre lo que haría U en caso de empezar con una cinta con un único número como input. No podemos estar de acuerdo en lo que dices.

2) Si n es el código de la máquina H descripta antes, U interpreta el código de H con el input del código de H, para predecir si para o no.

Supongo que cuando dices H te refieres a la máquina que yo llamaba M. En tal caso, lo que dices es correcto entendiendo que, cuando  U actúa como parte del programa de M, en el momento en que empieza se encuentra con una cinta con dos números iguales, no con un único número.

Rectifico errores de tipeo o interpretación que señalas:

1) Cuando U recibe como input el par (k, k) escribe 1 si Mk para con el input k, y 0 si no lo hace.

2) Si n es el código de la máquina M descripta antes, U interpreta el código de M con el input del código de M, para predecir si para o no.

Creo que estarás de acuerdo, porque he hecho las enmiendas según lo que has señalado.

En ese caso

1-U interpreta cod.M con input cod.M
2-Para predecir si M para con ese input, debe tomar en cuenta la predicción de M sobre si M para o no con input indeterminado.

En este punto es que disentimos, porque supongo que tú opinas que debería existir alguna operación incluso si no hay input. Mi opinión es que esa situación no es asimilable a parar o continuar indefinidamente, sino que rompe la dicotomía que permitía la contradicción.
En todo caso, para mantener el resultado, hay que postular que ante la falta de input, hay una operación de M para terminar o continuar indefinidamente. Pero eso le quitaría generalidad.

Saludos!