Читать книгу Computación y programación funcional - Camilo Chacón Sartori - Страница 11

Un modelo de computación es un modelo matemático, es decir, un modelo formal con una sintaxis definida, no ambigua, y que nos permite representar un proceso computable, al cual conocemos como algoritmo.

Problema de decisión

¿De dónde nace el concepto de modelos de computación? En primer lugar, debemos volver al principio del siglo XX y fijarnos en una persona que es relevante en la historia de las matemáticas: David Hilbert (véase figura 1.1). Fue un eminente matemático que a comienzos del siglo XX dio una famosa conferencia² en la que presentó veintitrés problemas matemáticos que serían importantes e influyentes para el desarrollo de las matemáticas y, por eso mismo, él esperaba que se encontrara una solución para cada uno de ellos. (Hasta el día de hoy hay muchos de ellos que siguen sin solución.) Luego, en 1928, junto a William Ackermann (su alumno de doctorado), publicó un libro titulado Grundzüge der theoretischen Logik («Fundamentos de la lógica teórica») donde postularon lo que se conoce como problema de decisión (originalmente conocido como Entscheidungsproblem, en alemán), el cual se define como sigue:

Encontrar un procedimiento P que siempre encuentre la solución a un problema A según sus premisas y conclusiones.

A este «procedimiento» se le conoce, hoy en día, como «algoritmo». Por ejemplo, este problema plantea la pregunta de si es posible encontrar un algoritmo que siempre dé una respuesta («sí» o «no») a preguntas tales como: «dado un número natural, ¿es posible saber si es miembro de un conjunto?» o «dado un número natural, ¿puede responder si es un número primo o no?». Esto lleva a la siguiente cuestión, un problema de decisión es un problema de decidibilidad que busca responder a la pregunta de si existe un método efectivo (algoritmo) que demuestre si un objeto matemático (por ejemplo, un número) es miembro de un conjunto.

Un problema que demostró que no es posible encontrar un algoritmo para resolver un problema de decisión, es el conocido problema de la parada (halting problem en inglés). Este se puede definir de la siguiente forma:

Si existe un programa P que recibe como argumento un programa K con datos de entrada X; P debe devolver 1 si K con la entrada X termina en un número finito de pasos, mientras que devuelve un 0 si K con X cae en un bucle infinito.

Esto desembocó, casi en paralelo y de manera independiente, en que Alan Turing, con su máquina de Turing,³ y Alonzo Church, con el cálculo lambda, probaran que no existe un algoritmo para resolver el problema de la parada para cualquier valor de entrada (es decir, es «indecidible»), derrumbando, así, el sueño de Hilbert.

Figura 1.1 David Hilbert.