La Incomputabilidad del Problema de la Parada en Programas de Ábacos

Introducción a la Incomputabilidad

En este documento, definiremos una función específica, h, y demostraremos que ningún programa de ábacos es capaz de computarla. Esta demostración es fundamental para comprender los límites inherentes de la computación.

Enumeración de Funciones y Programas

La definición de la función h se basa en una enumeración sistemática de todas las funciones de una variable que son computables por ábacos. Esta enumeración, denotada como f₀, f₁, f₂, …, se deriva de una enumeración previa de todos los programas de ábacos, A₀, A₁, A₂, ….

Los detalles precisos sobre cómo se realiza esta enumeración de programas de ábacos no son cruciales para la demostración. Lo esencial es que todos los programas de ábacos posibles deben aparecer en esta lista.

Definición de la Función h

La función h(m,n) se define de la siguiente manera:

h(m,n) = { 0  si fm(n) está definido
         { 1  si fm(n) no está definido

• m: Representa el número que ocupa una función específica (f_m) en la enumeración previamente mencionada.
• n: Es el número al que se aplica la función f_m.

Es importante destacar que la función h siempre está definida; su valor solo puede ser 0 o 1.

El Problema de la Parada

El Problema de la Parada consiste en diseñar un programa de ábacos que sea capaz de computar la función h. A continuación, demostraremos que este problema es inherentemente insoluble.

Suposición de Computabilidad: El Programa H

Si la función h fuera computable, entonces debería existir un programa de ábacos – al que llamaremos H – que, al iniciarse con el valor m en el registro 1, el valor n en el registro 2, y todos los demás registros vacíos, se detendría en algún momento, dejando el valor de la función h(m,n) en el registro 1.

Construcción del Programa H'

A partir del programa H, es posible definir de manera inmediata otro programa, al que denominaremos H'. Su funcionamiento es el siguiente:

Cuando el programa H' comienza con un número en el registro 1 y todos los demás registros vacíos, los primeros cinco "nudos" (instrucciones) tienen el efecto de duplicar el número del registro 1 en el registro 2. Inmediatamente después, se ejecuta el programa H. Finalmente, se ejecuta el siguiente "nudo": (círculo con un 1- y flecha que vuelve, flecha hacia arriba y flecha que viene). Este último nudo representa un bucle infinito si el registro 1 está vacío al salir de H.

Análisis de Casos: La Contradicción

Si asumimos que el programa H existe, entonces el programa H' también debe existir. Este último programa H' computaría alguna función, f_m, que está incluida en nuestra enumeración de funciones de una variable computables mediante ábacos.

Ahora, consideremos el valor que f_m asigna (si es que lo hace) a m mismo. Tenemos dos posibilidades:

Caso 1: f_m(m) está definido

Si f_m(m) está definido, significa que en algún momento el programa H' alcanza su "flecha de salida" (termina), después de haber comenzado con m en el registro 1 y los demás registros vacíos.

Esto solo puede ocurrir si el registro 1 no estaba vacío cuando se llegó a él por una de las flechas de salida del subprograma H (es decir, H se detuvo y dejó un valor en el registro 1).

Sin embargo, por la definición de la función h, si H se detuvo y dejó un valor (lo que implica que f_m(m) está definido), el valor h(m,m) debería ser 0. Pero si H' termina, significa que H dejó un valor en el registro 1, lo que por la lógica de H' (el bucle final) implica que h(m,m) debería ser 1 (para evitar el bucle). Esto es una contradicción.

Según la definición de h, si h(m,m) es 1, entonces f_m(m) no está definido. Esto contradice nuestra suposición inicial de que f_m(m) está definido.

Por lo tanto, el Caso 1 es imposible.

Caso 2: f_m(m) está indefinido

Si f_m(m) está indefinido, significa que el programa H' nunca deja de "dar vueltas" por la flecha de bucle al final del programa H'.

Esto implica que el registro 1 debía estar vacío cuando se salió del subprograma H (es decir, H se detuvo y dejó el registro 1 vacío, o no se detuvo en absoluto). Si el registro 1 estaba vacío, entonces, por la definición de la función h, h(m,m) debería ser 0.

Pero, por la definición de la función h, si h(m,m) es 0, esto significa que f_m(m) está definido. Esto contradice nuestra suposición inicial de que f_m(m) está indefinido.

Por lo tanto, el Caso 2 también es imposible.

Conclusión: La Insolubilidad del Problema de la Parada

Hemos demostrado que si la función h fuera computable por ábacos, entonces existirían los programas H y H', y se daría necesariamente el Caso 1 o el Caso 2. Sin embargo, ambos casos han demostrado ser imposibles, lo que nos lleva a una contradicción.

La única conclusión lógica es que la función h no es computable por ábacos.

En otras palabras, el Problema de la Parada de programas de ábacos no es soluble por ábacos.

Si aceptamos la Tesis de Church-Turing (que postula que cualquier función computable por un algoritmo puede ser computada por una máquina de Turing, y viceversa), entonces la demostración anterior revela que el Problema de la Parada de programas es absolutamente insoluble. Esto significa que no solo es insoluble para programas de ábacos, sino para cualquier tipo de rutina mecánica o algoritmo computacional.