4.4: Una Ruta Alterna

Una segunda ruta hacia la incompletitud no se centra en fórmulas y deducciones, sino más bien en funciones que mapean los números naturales a los números naturales. Esta línea de razonamiento, desarrollada a finales de la década de 1930, tiene una clara conexión con la computación y la informática teórica. Al pensar cuidadosamente en lo que significa que una función sea computable y justo lo que es un cómputo, una vez más podremos mostrar la existencia de una fórmula que es verdadera y sin embargo no demostrable. Los detalles de este plan se exponen en el Capítulo 7.

¿Cuándo es computable una función? La idea es que decir que una función\(f\) es computable en entrada\(k\) significa que hay una secuencia de pasos fáciles que lleva a la salida correcta\(f \left( k \right)\). Haremos esto preciso en el Capítulo 7, pero aproximadamente significa que uno puede comenzar con algunas funciones fáciles y construir la función\(f\) mediante algunas operaciones relativamente simples en funciones previamente definidas.

Así parece que para definir cuidadosamente lo que significa calcular una función, se nos requerirá discutir secuencias de cálculos parciales, y una vez más será conveniente poder codificar estas secuencias como números naturales. Entonces, incluso si tomamos esta ruta basada funcionalmente hacia el Teorema de Incompletitud, necesitaremos estar familiarizados con algún aparato de codificación. Dado que nuestras dos rutas hacia el Teorema de Incompletitud requerirán que codifiquemos secuencias, tomaremos el resto de este capítulo para fijar nuestra notación y establecer un par de resultados fáciles.