Kitabı oku: «Computación y programación funcional», sayfa 2
Capítulo 1
¿QUÉ ES LA COMPUTACIÓN?
Si alguien me preguntara qué consejo le daría a un joven [...] Creo que una de las cosas que le diría es que no porque algo esté de moda significa que sea bueno. Probablemente iría más allá: si encuentro demasiada gente adoptando una cierta idea, probablemente pensaría que está mal o, ya sabes, si mi trabajo se hubiera vuelto demasiado popular, probablemente pensaría que tengo que cambiar.
Donald Knuth
Esta pregunta puede parecer simple en su formulación, pero nos puede llevar a confines que van desde aspectos técnicos hasta filosóficos. A su vez, la misma se ha vuelto relevante con el paso de los años y tuvo su mayor auge a comienzo del siglo XX, en particular, hacia la década de los treinta, cuando un grupo de científicos, matemáticos y lógicos buscaban comprender qué era la computación como tal, ya sea desde un punto de vista teórico o práctico.
Así como también sus posibilidades y limitaciones para tratar con diversos problemas. De esta manera, y producto de sus esfuerzos, fue como nació el concepto de «modelos de computación». Este concepto apareció antes de la existencia del primer ordenador digital (de nombre ENIAC, construido durante la segunda guerra mundial [1943]).
Pero ¿qué es un modelo de computación? Esta pregunta usa dos palabras relevantes: «modelo» y «computación». Primero, un «modelo» es una representación del funcionamiento de algo en particular (ya sea abstracto o concreto) que puede ser reproducible. Por otra parte, «computación» refiere a la capacidad de hacer tareas repetitivas que se puedan automatizar sin la intervención humana, de lo cual se desprenden dos cuestiones: (1) la acción de hacer estas tareas se llama computar y (2) si es posible realizar dichas tareas, entonces se suele decir que son computables.
Así, un «modelo de computación» es una representación abstracta que representa qué tareas son computables o no a través de computar operaciones. Dado que estos modelos son abstractos, podemos decir que un modelo de computación es equivalente a un modelo matemático. Con la salvedad de que el primero se enfoca en el contexto de la computación y hace uso de sus ventajas y desventajas.
Por ello la computación es en sí —al menos en su origen— es un área de las matemáticas. Por lo tanto, la computación es un conjunto de modelos de computación.
Sin embargo, la computación misma ha sufrido cambios en las últimas décadas, y decir que solo se trata de un conjunto de modelos de computación parece caer en un reduccionismo teórico. Más bien, tomaremos partido por ampliar esta definición a la siguiente: la computación es un conjunto de modelos de computación que se pueden expresar a través de artefactos abstractos (software) y concretos (hardware), mediante el uso de una metodología científica o ingenieril, teórica o práctica.
Objetivos de este capítulo:
• Conocer los principales modelos de computación.
• Conocer qué es la tesis de Church-Turing y cuáles son sus implicaciones en la computación.
• Comprender qué es la filosofía de la ciencia de la computación y cómo nos puede ayudar a ser mejores conocedores de nuestra propia área.
Nota:
Aún hoy, existe un debate sobre la naturaleza de la computación. ¿Es una ciencia? ¿Una ingeniería? ¿O algo totalmente nuevo? Son preguntas difíciles de responder que han suscitado libros, artículos y amplios debates en las últimas décadas. Pero tomaremos una postura. Creemos, como dicen Peter J. Denning y Peter A. Freeman en su interesante artículo «Computing’s Paradigm» («Paradigma de la computación») de 2009, que la computación es un «nuevo paradigma» que combina cuestiones de diversas disciplinas del saber: ciencias, ingeniería y matemáticas. Además, ellos dicen que la computación no trata sobre ordenadores, sino más bien sobre el procesamiento de la información, y los ordenadores son máquinas que implementan esos procesos.
Y no faltan motivos para creerlo, ya que la computación puede ser una herramienta muy útil para una innumerable cantidad de áreas, desde humanidades hasta ciencias, aparte de estudiarse a sí misma (procesos computacionales y sus límites teóricos). Algo que no se compara con nada hasta la fecha. Por tanto, deberíamos tratarla como algo nuevo, en desarrollo y en búsqueda de su propio significado.
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 conferencia2 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,3 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 fila), cuando el estado actual es E0 y tiene el símbolo de entrada «0», se mantiene en el estado E0 y lo cambia por el símbolo de salida «1», y el cabezal se mueve a la derecha. Esto ocurre sucesivamente hasta el tercer paso.
Ahora bien, si vamos al cuarto paso, que es donde encontramos un «1» en el cabezal, esto nos lleva a la segunda fila de la tabla. Si el estado actual es E0 y el símbolo de entrada es «1», entonces se mantienen el estado actual y el valor «1», y se mueve el cabezal a la derecha.
El proceso sigue ocurriendo hasta que se encuentra el estado E0 y el símbolo de entrada «#» (última fila de la tabla) devuelve un símbolo vacío «-» y detiene el procesamiento de la máquina de Turing (estado H). Por consiguiente, ya no hay ningún tipo de movimiento más por realizar. La computación se ha terminado.
Máquina de Turing universal
Una máquina de Turing universal U puede simular otra máquina de Turing T como una entrada. ¿Cómo lo logra? Leyendo (1) una descripción o tabla de instrucciones Dt de la máquina Et a ser simulada y (2) los valores de entrada de dicha máquina Et. Pues bien, con esto se puede, con una sola máquina, lograr «ejecutar» cualquier otra máquina de Turing.
Esto lo representamos con la figura 1.3, donde una máquina de Turing universal U puede simular otra máquina de Turing Et con (1) descripción, (2) contenido y (3) estados. Esto conlleva la idea de que una máquina de Turing universal puede simular cualquier otra máquina de Turing dándole la información requerida en otra «cinta».
Figura 1.3 Una máquina de Turing universal.
Una máquina de Turing universal, concretamente, según dice Martin Davis, inspiró a John von Neumann para crear la primera arquitectura de computadoras en 1945, en su documento «First Draft of a Report on EDVAC» («Primer borrador de un informe sobre EDVAC»). En este documento, von Neumann presenta las ventajas del sistema binario sobre el decimal para las operaciones aritméticas elementales (+, -, ×, ÷), y según sus propias palabras, esto se explica por lo siguiente:
La principal virtud del sistema binario, en contraposición con el decimal, reside en la mayor simplicidad y velocidad con que se pueden ejecutar las operaciones elementales. (von Neumann, 1945)
Igualmente, se incorporan los registros especiales de memoria cuyo objetivo es, antes que nada, tener un conjunto de funciones ya definidas en memoria (por ejemplo: √, ||, log10, log2, ln, sin, etc.). Esto significa que no es necesario redefinir dichas funciones y, por ello, como es de suponer, el tiempo de cómputo se vería disminuido.
Por otro lado, el trabajo de Turing tuvo notables implicaciones en los fundamentos de la teoría de la complejidad computacional. Por su misma naturaleza, la capacidad explícita de secuencialidad de cada instrucción hace más simple poder clasificar problemas computacionales de acuerdo con su dificultad. Por ejemplo, las diversas clases de complejidad.
Antes de eso, primero debemos diferenciar dos cuestiones fundamentales: tiempo polinomial y tiempo exponencial. El tiempo polinomial, o mejor dicho, el tiempo polinomial de un algoritmo, es aquel en el que el tiempo de cómputo crece según la cantidad de datos de entrada n, los cuales no son exponenciales. Esto significa que la computación es más rápida. En la tabla 1.2 se presentan varios algoritmos4 clásicos, que usan la notación Big O5 (en el peor de los casos):
| Tiempo polinomial | Tiempo exponencial | ||
| Búsqueda lineal | O(n) | Knapsack 0/1 | O(2n) |
| Búsqueda binaria | O(log n) | Travelling salesman problem | O(2n) |
| Quicksort | O(n2) | Graph coloring | O(2n) |
| Merge sort | O(n log n) | Hamylton cycle | O(2n) |
Tabla 1.2 Comparación de complejidad algorítmica entre tiempo polinomial y tiempo exponencial.
Cualquier algoritmo que tenga una complejidad elevada a la enésima potencia (como los que aparecen en la columna de la derecha) es computacionalmente demasiado complejo de solucionar en un tiempo de cómputo óptimo (polinomial). Esto se traduce en que se tarda demasiado tiempo en terminar la computación.
Pasemos a ver las principales clases de complejidad:
• P (polynomial en inglés). Es la clase de problema que es posible tratar, es decir, hay un algoritmo determinístico que lo resuelve de manera eficiente en un tiempo polinomial. Por ejemplo, los algoritmos de ordenamiento y de búsqueda de una subcadena dentro de un texto o del camino más corto entre dos nodos dentro de un grafo, entre otros.
• NP (non-deterministically polynomial en inglés). La clase de problemas que pueden ser resueltos en un tiempo polinomial por un algoritmo no determinístico. (Esto último significa que son algoritmos que tienen un componente de selección aleatorio en su comportamiento, es decir, cada ejecución con los mismos argumentos no asegura el mismo valor de devolución. Por ejemplo, el algoritmo de colonia de hormigas, algoritmos genéticos, etc.) Los problemas NP son problemas de decisión. De esta clase nace la siguiente pregunta: ¿estos problemas pueden resolverse de manera determinista en un tiempo polinomial? Es decir, ¿es P = NP? Esto no ha sido probado y es uno de los problemas del siglo que aún sigue abierto. Ejemplos de problemas de esta clase: la factorización de números enteros y el isomorfismo de grafos.
• NP-Completo. Problemas más difíciles que los NP y, obviamente, que los P. Son problemas de decisión que se diferencian de los NP en lo siguiente: representan el conjunto de todos los problemas X en NP que se pueden reducir a cualquier otro problema NP en tiempo polinomial, es decir, intuitivamente lo entendemos así: si tenemos la solución para el problema X, entonces podríamos encontrar rápidamente la solución al problema Z. Ejemplos de problemas de esta clase son: 3-SAT, el problema del vendedor viajero, camino hamiltoniano, etc.
• NP-Difícil (NP-hard en inglés). Son problemas de decisión tan complejos como los NP, pero no se sabe si existe un algoritmo verificable en tiempo polinomial para todos los casos. Esto último nunca ha sido demostrado, es decir, si P ≠ NP, entonces los problemas de esta categoría no pueden ser resueltos en tiempo polinomial. Un ejemplo de este tipo es el problema de la parada, que es NP-Difícil pero no NP-Completo.
La figura 1.4 resume la relación entre estas tres clases de complejidad:
Figura 1.4 Características de cada clase de problema de complejidad. El signo «|» significa «o».
Resumiendo, las clases de complejidad existen porque hay muchos tipos de problemas computacionales y una forma de tratarlos de mejor manera es clasificarlos por su dificultad. Con esto es posible diseñar técnicas algorítmicas más adecuadas según su clase.
1.1.2 Cálculo lambda
El cálculo lambda es un modelo de computación que está basado en funciones computables. Fue creado por Alonzo Church y lo veremos con mayor detalle en la parte II del libro (capítulo 4), pero aquí daremos un esbozo general del modelo. Al igual que Alan Turing con su máquina de Turing, el cálculo lambda de Alonzo Church probó negativamente el problema de decisión.
A diferencia de la máquina de Turing, que tiene un proceso secuencial, el cálculo lambda construye la computación a través de funciones computables que se forjan en una notación formal con una gran expresividad. El cálculo lambda es una máquina de recursividad que cuenta con operadores, variables y operaciones de reducción (conocida como reducción b). Por tanto, hace un uso asiduo de la recursividad y de mantener estados inmutables en cada una de sus fases de reducción o derivación.
Antes de presentar una función lambda, es fundamental entender qué es una función matemática. Una función se puede definir de la siguiente manera: f:a → b, donde la función f recibe un valor a y devuelve b. Además, a y b pueden ser representados como conjuntos de elementos. Así, la función es una relación entre elementos de dos conjuntos.
Para nuestro ejemplo, el conjunto a se llama «dominio» y el conjunto b «codominio»; representan al conjunto de entrada y salida respectivamente. En notación conjuntista esta misma función puede ser definida de la siguiente manera: f(a) = b. Un ejemplo puede ser una función f que recibe un número entero que incrementa en 1. En este caso, f(x) = x + 1. Si a x se le asigna el valor 5, o sea, f(5) = 5 + 1, devolvería 6.
Entonces, volviendo a las funciones lambda, estas tienen como mecanismo de operación la reducción hasta donde sea posible. A esto lo llamamos computación.
Un ejemplo de función lambda es la siguiente:
(λx.(λy.y)x) (λy.y)
donde la función lambda es (λx.(λy.y)x) y el argumento es (λy.y). Para derivar o reducir esta función se puede aplicar reducción β, que es una propiedad del cálculo lambda:
(λx.(λy.y)x) (λy.y)
= (λy.y) (λy.y)
= (λy.y)
Termina las operaciones cuando alcanza la función (λy.y), que es, dicho sea de paso, una función de identidad que no puede ser reducida porque ya no tiene argumentos a la derecha. Para comprender esta reducción, vea la figura 1.5, donde se indica el argumento (desde donde nace la flecha, a la derecha), junto con la variable «X» (fase 1), y la variable «y» (fase 2) vendría a ser la posición donde dicho argumento tendrá su lugar (sustitución).
Básicamente, el primer paso es aplicar el primer argumento, (λy.y), a la función de la derecha. Y, debido a que toda variable que se encuentra a la derecha del símbolo λ se asocia a un argumento, esto quedaría así: [x:= (λy.y)]. Por lo tanto, se aplica una sustitución. (Una función lambda solo acepta un argumento.)
Así, a cada paso de reducción se aplica una sustitución de términos, hasta donde sea posible. Esto conlleva que la primera función exhibida se reduzca a la expresión (λy.y), donde ya no es posible continuar derivando.
Figura 1.5 Reducción de una función lambda, donde el primer argumento es (λy . y) y sustituye a la variable «X» definida dentro de la función lambda. Así, en la fase 2, se crea una reducción y vuelve a sustituir la siguiente variable, hasta llegar a la fase 3, donde ya no es posible aplicar ninguna otra reducción.
Podríamos decir que el cálculo lambda es un pequeño lenguaje de programación que permite expresar la computación a través de una sintaxis simple, acotada, flexible y, a su vez, poderosa. Algo para tener en cuenta es que una función lambda como (λ x.x) tiene una variable «X» que no especifica nada sobre el tipo de dato que tiene, es decir, este cálculo lambda es no tipado o libre de tipos, porque así fue presentado por Alonzo Church para la primera versión del cálculo lambda. La idea central, entonces, es ver que podemos manejar una función lambda como un valor y usarla como argumento de otra función lambda.
Esto último trae consigo alcances que explican las características de los lenguajes de programación funcionales y su surgimiento.
