Estrictamente, el teorema de Goedel se aplica a los sistemas de axiomas lógicos, y no a los dispositivos informáticos. El equivalente en términos informáticos es la tesis de Church-Turing, que se aplica a las máquinas de Turing. Eso traduce “verdaderos teoremas que no se pueden probar” en “programas cuya funcionalidad no se puede determinar en un tiempo de ejecución finito”.
Una máquina Turing es una versión idealizada de un dispositivo real. Un dispositivo real no puede hacer más que una máquina de Turing, computacionalmente hablando. De hecho, las computadoras reales están limitadas a una cantidad fija de memoria, mientras que una máquina Turing siempre tiene tanta memoria como necesita. No es estrictamente “infinito”, sino un número finito que siempre es lo suficientemente grande para cualquier tarea que establezca. Los problemas de computabilidad deben establecer fuertes distinciones entre “cosas que toman mucho, mucho tiempo” y “cosas que toman para siempre”.
Con una memoria de computadora real, está claro que hay problemas bastante comunes que no se pueden resolver, sin necesidad de invocar las rarezas que se tragan a sí mismos y que prueban los teoremas de Goedel y Turing-Church. Solo requieren demasiada memoria y no se pueden reducir.
- ¿De qué haremos qubits? ¿Ya tenemos?
- ¿Qué permitirá la computación cuántica lograr a la humanidad?
- ¿Cómo funcionan las uniones Josephson?
- ¿Cuál es el significado de 'cuantizado' cuando hablamos de física cuántica?
- ¿Qué son las fluctuaciones cuánticas?
Pero si considera una computadora “real” idealizada con “suficiente” memoria, todavía está atrapado en los teoremas. No pueden calcular nada más que una máquina de Turing. Las máquinas de Turing son simplistas, para facilitar la comprobación de las cosas sobre ellas, pero es fácil definir conceptualmente el funcionamiento de cualquier computadora real en términos de instrucciones de la máquina de Turing.
Es posible que una computadora analógica o cuántica sea literalmente diferente de una máquina Turing; la teoría no está tan bien desarrollada y requiere responder preguntas de física desconocidas. Pero los chips puramente binarios de una computadora real son solo versiones elegantes de una máquina Turing, y están sujetos a las mismas limitaciones.
