Computación y programación funcional. Camilo Chacón Sartori

      Este libro no intentará entrar en ese debate. Pero daremos una introducción clásica y teórica de lo que es la computación, con algunas pinceladas filosóficas. Para más información le recomendamos leer el libro Computational thinking («Pensamiento computacional») de Peter J. Denning y Matti Tedre.

       1.1 MODELOS DE COMPUTACIÓN

      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.

       1.1.1 Máquina de Turing

      En 1936, Alan Turing formularía en su artículo «On Computable Numbers, with an Application to the Entscheidungsproblem» («Sobre los números computables, con una aplicación al problema de la decisión») la prueba de que no es posible dar respuesta al problema de decisión.

      En este trabajo Turing presentaría lo que hoy en día llamamos máquina de Turing. Una abstracción matemática que representa la computación o, para ser más precisos, lo que es computable o no.

      Michael Sipser, importante teórico de la computación diría en su libro Introduction to the Theory of Computation («Introducción a la teoría de la computación») lo siguiente:

      Una máquina de Turing puede hacer todo lo que un ordenador de propósito general puede hacer. Sin embargo, hay algunos problemas que ni la máquina de Turing puede resolver. En concreto, estos problemas van más allá de los límites teóricos de la computación. (Sipser, 1997)

      Esto quiere decir que, de hecho, una máquina de Turing puede hacer todo lo que un ordenador digital puede hacer (teóricamente) y que, a su vez, posee las mismas limitaciones. Por ello, queda claro que existe una influencia en su nivel más subyacente y esencial. Los ordenadores digitales que usamos en la actualidad corresponden a la arquitectura propuesta por John von Neumann en su borrador sobre EDVAC, en el que presenta la organización y el mecanismo de cómo debería funcionar este. Pero ya volveremos a esto.

      Algunas características de una máquina de Turing son las que se presentan a continuación:

      • Existe una cinta infinita (que puede entenderse como una memoria).

      • Existe un cabezal que puede leer y escribir sobre cada celda de la cinta.

      • El cabezal se puede mover de izquierda a derecha o viceversa.

      • Existe una tabla de instrucciones; haciendo uso de ella, la máquina sabe qué valores puede reemplazar en cada operación y también cuándo detenerse.

      Intuitivamente podría ser vista como se muestra en la figura 1.2:

      Figura 1.2 Una representación visual de una máquina de Turing, donde el cabezal se posiciona en el símbolo 0. El símbolo al final (derecha) «#» significa que el procedimiento se va a parar (comúnmente conocido como halt, en inglés).

       Ejemplo

      Imaginemos que necesitamos realizar una operación muy simple: reemplazar cada aparición de cierto carácter en una secuencia de texto dada, por ejemplo, pasar de «00011010» a «11111111», o sea, reemplazar el carácter 0 por 1. Para ello, es necesario crear una máquina de Turing.

      Para esto necesitamos una tabla de instrucciones que contenga la mecánica de cómo se realizará cada cambio de estado:

      Tabla 1.1 Tabla de instrucciones de lo que debe realizar la máquina.

      Considere el siguiente texto de entrada:

      00011010#

      La secuencia comenzaría de izquierda a derecha. Se agrega el símbolo «*» para indicar la posición del cabezal junto al carácter actual, que estará a la izquierda. Así pues, los cambios de estado serían los siguientes:

      1. 0*0011010#

      2. 10*011010#

      3. 110*11010#

      4. 1111*1010#

      5. 11111*010#

      6. 111111*10#

      7. 1111111*0#

      8. 11111111*#

      9. 11111111#*

      10. 11111111

      En el primer paso, por ejemplo, el cabezal encuentra el carácter «0». Entonces, si vemos la tabla (primera