13.1: Introducción

Template:MathJaxZach

Puede parecer obvio que no todas las funciones, incluso todas las funciones aritméticas, pueden ser computables. Simplemente hay demasiados, cuyo comportamiento es demasiado complicado. Funciones definidas a partir de la desintegración de partículas radiactivas, por ejemplo, u otro comportamiento caótico o aleatorio. Supongamos que comenzamos a contar intervalos de 1 segundo a partir de un tiempo dado, y definimos la función\(f(n)\) como el número de partículas en el universo que decaen en el\(n\) -ésimo intervalo de 1 segundo después de ese momento inicial. Esto parece un candidato a una función que nunca podemos esperar calcular.

Pero una cosa es no poder imaginar cómo se computarían tales funciones, y otra muy distinta demostrar realmente que son incomputables. De hecho, incluso las funciones que parecen irremediablemente complicadas pueden, en un sentido abstracto, ser computables. Por ejemplo, supongamos que el universo es finito en el tiempo, algún día, en un futuro muy lejano el universo se contraerá en un solo punto, como predicen algunas teorías cosmológicas. Entonces sólo hay un número finito (pero increíblemente grande) de segundos a partir de ese momento inicial para el que\(f(n)\) se define. Y cualquier función que se defina solo para muchas entradas finitamente es computable: podríamos enumerar las salidas en una tabla grande, o codificarla en un diagrama de transición de estado de máquina Turing muy grande.

A menudo nos interesan casos especiales de funciones cuyos valores dan respuestas a preguntas de sí/no. Por ejemplo, la pregunta “¿es\(n\) un número primo?” se asocia con la función\[\fn{isprime}(n) = \begin{cases} 1 & \text{if $n$ is prime}\\ 0 & \text{otherwise.} \end{cases}\nonumber\] Decimos que una pregunta de sí/no puede decidirse efectivamente, si la función\(1/0\) valorada asociada es efectivamente computable.

Para demostrar matemáticamente que hay funciones que no se pueden computar de manera efectiva, o problemas que no pueden decidirse efectivamente, es esencial fijar un modelo específico de cálculo, y mostrar al respecto que hay funciones que no puede calcular o problemas que no puede decidir. Podemos demostrar, por ejemplo, que no todas las funciones pueden ser calculadas por las máquinas Turing, y no todos los problemas pueden ser decididos por las máquinas Turing. Entonces podemos apelar a la tesis de Church-Turing para concluir que no solo las máquinas Turing no son lo suficientemente poderosas como para computar todas las funciones, sino que ningún procedimiento efectivo puede hacerlo.

La clave para probar resultados tan negativos es el hecho de que podemos asignar números a las máquinas Turing ellos mismos. La forma más fácil de hacerlo es enumerarlos, tal vez fijando una forma específica de anotar las máquinas Turing y sus programas, y luego enumerarlos de manera sistemática. Una vez que vemos que esto se puede hacer, entonces la existencia de funciones Turing-incomputables sigue por simples consideraciones de cardinalidad: el conjunto de funciones de\(\Nat\) a\(\Nat\) (de hecho, incluso solo de\(\Nat\) a\(\{0, 1\}\)) son incontables, pero desde podemos enumerar todas las máquinas Turing, el conjunto de funciones de Turing-computable es solo contablemente infinito.

También podemos definir funciones y problemas específicos que podemos demostrar que son incomputables e indecibles, respectivamente. Uno de esos problemas es el llamado Problema de la Paralización. Las máquinas de Turing se pueden describir finitamente enumerando sus instrucciones. Tal descripción de una máquina Turing, es decir, un programa de máquina Turing, por supuesto, se puede usar como entrada a otra máquina Turing. Por lo que podemos considerar máquinas Turing que decidan preguntas sobre otras máquinas Turing. Una pregunta particularmente interesante es esta: “¿La máquina Turing dada finalmente se detiene cuando se inicia con entrada\(n\)?” Sería bueno si hubiera una máquina Turing que pudiera decidir esta pregunta: piense en ella como una máquina Turing de control de calidad que asegura que las máquinas Turing no queden atrapadas en bucles infinitos y tal. El dato interesante, que Turing demostró, es que no puede haber tal máquina Turing. No puede haber una sola máquina Turing que, cuando se inicia en la entrada que consiste en una descripción de una máquina Turing\(M\) y algún número\(n\), siempre se detendrá con la salida\(1\) o de\(0\) acuerdo a si \(M\)la máquina se habría detenido cuando se inició en la entrada\(n\) o no.

Una vez que tenemos ejemplos de problemas específicos indecibles podemos utilizarlos para demostrar que otros problemas también son indecibles. Por ejemplo, un problema célebre indecidible es la pregunta: “¿Es\(A\) válida la fórmula de primer orden?”. No hay ninguna máquina Turing que, dada como entrada una fórmula de primer orden\(A\), se garantice que se detenga con salida\(1\) o de\(0\) acuerdo a si\(A\) es válida o no. Históricamente, la cuestión de encontrar un procedimiento para resolver efectivamente este problema se denominó simplemente “el” problema de decisión; por lo que decimos que el problema de la decisión es irresoluble. Turing e Church probaron este resultado de forma independiente aproximadamente al mismo tiempo, por lo que también se le llama Teorema de Iglesia-Turing.