Gödel y Turing (Parte 2)

(A la parte 1 - A la parte 3)

El Entscheidungsproblem

En la conferencia inaugural del Congreso Internacional de Matemáticas celebrado en París en el año 1900 el ilustre David Hilbert planteó veintitrés problemas matemáticos abiertos que, él esperaba, podrían ser resueltos a lo largo del siglo XX. De todos ellos, el décimo problema planteaba la siguiente pregunta: ¿es posible diseñar un algoritmo que, dada una ecuación diofántica cualquiera, indique si admite o no alguna solución? (1)

Podemos transformar este pregunta en un problema más general, conocido como el Entscheidungsproblem, y cuyo enunciado es el siguiente: dada una teoría matemática no trivial ¿es posible diseñar un algoritmo que, dada una proposición cualquiera de esa teoría, nos indique si la misma es verdadera o falsa? Enunciado en términos más dramáticos, el Entscheidungsproblem nos pregunta ¿es posible, aunque sea en teoría, diseñar una computadora que reemplace a un matemático?

Tanto en el planteo del décimo problema de la conferencia de París, como en el Entscheidungsproblem, la palabra clave es algoritmo. ¿Qué es un algoritmo? Intuitivamente, un algoritmo es una receta, una serie de instrucciones que nos dice cómo trabajar mecánicamente con cierto conjunto de datos. La palabra “mecánicamente” alude al hecho de que la receta debe indicarnos sin ambigüedades qué debemos hacer en cada circunstancia.

Un algoritmo recibe entonces una entrada ó conjunto de datos iniciales (input, en inglés), procesa esos datos y, tras un tiempo finito, entrega como respuesta una salida ó resultado (output, en inglés). Como decíamos antes, la característica distintiva de un algoritmo es que el procesamiento de los datos se realiza en forma mecánica. Sin embargo, para tratar con el décimo problema o con el Entscheidungsproblem esta noción intuitiva no es suficiente. Necesitamos una definición matemáticamente precisa del concepto de algoritmo, pero eso quedará para la próxima entrada.

Nota:

(1) Una ecuación diofántica es una ecuación polinómica de una o varias variables con coeficientes enteros (es decir una ecuación en la que sólo aparecen números enteros y en la que las únicas operaciones permitidas son la suma, el producto y la potencia con exponente entero positivo) y de la cual se buscan exclusivamente soluciones enteras.

(A la parte 1 - A la parte 3)