Page 169 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

revista Monatshefte für Mathematik and Physik en noviembre y apareció en el volumen 38 (1931),
una publicación cuya relevancia para la lógica es solo comparable con la Metafísica de Aristóteles.
La exposición de la demostración fue tan clara que no generó ni la más mínima controversia. Este
fue el embrión de las ciencias de la computación.

aNtecedeNteS de algorítMIca

La idea de disponer de un algoritmo o receta para efectuar alguna tarea ha existido durante miles
de años. También durante muchos años la gente creyó que si cualquier problema podía iniciarse de
manera precisa, entonces con suficiente esfuerzo sería posible encontrar una solución con el tiempo
(o tal vez una prueba de que no existe solución podría proporcionarse con el transcurso del tiempo).
En otras palabras, se creía que no había problema que fuera tan intrínsecamente difícil que en prin-
cipio nunca pudiera resolverse.

Se pensaba que las matemáticas eran un sistema consistente (es decir, que no era posible llegar a
contradicciones a partir de los axiomas iniciales), completo (existe una prueba para toda proposi-
ción matemática correcta) y decidible (existe un método efectivo que decide para cada proposición
posible, si es verdadera o falsa. A este se le conoció como el problema de la decisión o Entschei-
dungsproblem).

el proyecto de Hilbert

Uno de los principales promotores de esta creencia fue el famoso matemático David Hilbert (1862-
1943), quien creía que en matemáticas todo se podía y debía probarse a partir de los axiomas
básicos. El resultado de ello sería demostrar de manera concluyente los dos elementos básicos del
sistema matemático. En primer lugar, las matemáticas debían ser capaces, al menos en teoría, de
responder a cualquier interrogante concreto. En segundo lugar, las matemáticas deberían estar libres
de incongruencias; es decir, una vez demostrada la veracidad de una premisa a través de un méto-
do, no sería posible mediante otro método concluir que esa misma premisa era falsa. Hilbert estaba
convencido de que, asumiendo tan solo unos pocos axiomas, se podría responder a cualquier pre-
gunta matemática concebible sin temor a una contradicción.

El 8 de agosto de 1900, Hilbert pronunció una conferencia histórica en el Congreso Internacional de
Matemáticas en París. Allí planteó veintitrés problemas matemáticos sin resolver que él consideraba
de una perentoria importancia. Hilbert pretendía sacudir a la comunidad para que lo ayudaran a rea-
lizar su sueño de crear un sistema matemático libre de toda duda e incoherencia. Una ambición que
inscribió en su lápida:

163