Computación ¿Qué puede hacer un ordenador?
El concepto de Computación apareció en torno a los años 30 del siglo XX. Ya para cuando la guerra hubo terminado estaban en marcha amplios programas para el desarrollo de computadores, como el famoso Colossus (en la imagen), creado en Reino Unido.
Lo que una máquina puede hacer
Esta entrada estará destinada a introducir los cimientos de la teoría de la computación. Vamos a estudiar una serie de conceptos muy vinculados entre sí. Nuestro objetivo final será proponer una definición que abarque lo que una máquina digital puede hacer, es decir, eso a lo que llamamos “computar”. De esta noción podremos extendernos a preguntas más amplias… ¿Qué es lo que una computadora puede hacer? ¿Cuáles son los límites de la computación, si es que los tiene?
Debemos recalcar que, por el momento, no nos interesará la puesta en práctica de la máquina. Todos los conceptos que aquí exploraremos serán abstractos: buscamos conocer de antemano cómo opera una máquina sin tener que construirla, sin tener que darle un correlato físico. Esto es posible porque el concepto de máquina que manejaremos será realmente un modelo matemático. Trabajaremos con símbolos, funciones y operaciones aritméticas que bien pueden representar el movimiento de tuercas, palancas o corrientes eléctricas, pero que son independientes del aparataje mecánico. Es por ello que muchas de las preocupaciones usuales en ingeniería informática, como, por ejemplo, la velocidad de procesamiento, no nos interesarán por el momento. Pero sí que podremos cuestionarnos… ¿Habrá problemas imposibles de solucionar para una máquina, aunque le demos un tiempo de procesamiento absurdamente grande?
Computación y algoritmo
Es asombroso como una disciplina en la que el formalismo matemático tenga tanto peso, en ocasiones recurra a conceptos que no están estrictamente definidos. ¿Qué significa “computar”? Una primera definición podría sería la de un procedimiento que pueda ser llevado a cabo por un ordenador.
Para muchos científicos computar es resolver un problema de la manera en que lo haría una máquina de Turing, puesto que, como veremos, esta no deja de ser una abstracción formal de un ordenador. Básicamente, la descripción formal de la máquina de Turing será lo que defina con precisión matemática la idea de “computadora” y, por tanto, la de “computación”. Sin embargo, la máquina de Turing es solo uno de los múltiples modelos que han resultado ser equivalentes en cuanto a los posibles problemas que son capaces de solucionar. Es evidente que debe existir alguna propiedad más general que agrupe todos esos procedimientos bajo un mismo principio.
Otro concepto podría ser “procedimiento llevado a cabo según reglas estrictas”. Esto nos introduce el concepto de algoritmo, o también procedimiento efectivo, bastante usual de ver y que lo trataremos en calidad de sinónimo. Ni que decir tiene que la idea de algoritmo es mucho más vieja que la de computadora. Es un recurso bien conocido en el ámbito matemático desde hace siglos, pero aquí le daremos nuestra propia definición adecuada a buscar la equivalencia con la ejecución de una máquina. Un algoritmo recibe un input o conjunto de datos de entrada, los procesa y nos ofrece un output o resultado. Nos quedamos por ahora con esta definición deliberadamente abierta. Ahora vamos a explorar cuales son sus límites. Intentaremos a partir de aquí que nuestro concepto de algoritmo sea mucho más limitado y preciso.
Tiempo de ejecución
Todo el mundo sabe que contar los números es un tarea que, potencialmente puede ser infinita. Ahora bien ¿Cómo sabemos eso? ¿En qué momento y bajo que procesos mentales hemos llegado a la conclusión que los números son infinitos? Evidentemente llegar a esta deducción no puede implicar contar los números hasta el infinito. Nunca acabaríamos y, por tanto, nunca llegaríamos a estar seguros de sí son infinitos o no. Para un humano la respuesta es tan simple como “ver” que el procedimiento seguido para generar números no tiene ninguna limitación teórica y que por tanto podría seguir indefinidamente.
Esto es algo evidente para la inteligencia humana…pero no lo es tanto para una máquina. Podemos programar un algoritmo para que, aplicado reiteradamente, nos muestre todos los números posibles, pero esto no demuestra por sí mismo la infinitud de los números naturales. Toda demostración formal debe darse en una serie de pasos discretos y terminar con un resultado. Por eso, cualquier problema algorítmico debe implicar un número finito de pasos y, por tanto, la resolución del problema en un tiempo finito. Esto es así incluso cuando ese tiempo finito sea inmenso. Contar hasta 1057 es un problema en principio viable para un algoritmo pues sabemos que su resolución llegará en algún momento, aunque el tiempo que tarde en ello supere a la edad del universo.
Computación analógica vs. digital
El tiempo finito es una limitación de nuestro concepto de algoritmo. Pero habrá más. ¿Qué entidades puede manipular el algoritmo?
Computación digital
Imaginémonos una neurona. La neurona tiene dos posibles estados: excitada o no excitada (1 y 0 si se quiere). No hay término medio, o todo o nada. Podremos describir el estado de un conjunto de neuronas simplemente con un número binario que exprese el estado de cada neurona. Un estado posible en un circuito de 5 neuronas será 01101. El número total de estados posibles será 25. Los estados de la neurona son pues, estados discretos. En vez de números se pueden utilizar también signos.
Es irrelevante, lo importante aquí es que todo algoritmo opera con un alfabeto, un conjunto de signos discretos que pueden combinarse. A esto lo llamamos computación digital. Dos fórmulas serán iguales si contienen los mismos signos en la misma posición. Esa posición es también un dato discreto. El estado de un circuito neuronal, por grande que sea, es un parámetro que puede ser manipulado por un algoritmo. Hasta aquí ningún problema.
Computación analógica
Ejemplo de dos funciones continuas. Los valores de la función discurren de forma continua, sin saltos. Muchos fenómenos naturales de la mecánica o el electromagnetismo se describen como funciones continuas.
El algoritmo frente a las variables continuas
Por el contrario, nuestro algoritmo digital es incapaz de operar con este tipo de variables continuas. A lo máximo a lo que podría aspirar es a aproximar el valor con un grado de precisión determinado. Pero si nuestro objetivo es modelizar el comportamiento de un fenómeno natural (como puede ser la excitabilidad de una neurona), las aproximaciones pueden no ser suficientemente precisas. Las matemáticas del caos nos advierten: una aproximación que diste mínimamente de los valores reales de un parámetro puede hacer que las consecuencias predichas por nuestro modelo algorítmico sean completamente diferentes del fenómeno real, haciendo que la predicción sea completamente inútil.
Las variables continuas siempre son un desafío para toda máquina computacional digital. Por el momento evitaremos enfrentarnos a ellas y propondremos una definición de algoritmo que opere con un conjunto de signos discretos.
Manipulación de signos
La tercera y última limitación atañe a las reglas que definen la operatividad del algoritmo. La definición sin más que hemos propuesto de algoritmo -procedimiento que opera siguiendo reglas-, bien puede valer para un recetario de cocina. Revolver, cocer y hornear funcionarían como reglas. Habrá que afinar un poco más nuestra definición si queremos que algoritmo sea equivalente al procedimiento de una máquina computadora.
Comprensión y manipulación
Vimos que el algoritmo digital opera con signos de un alfabeto. Las reglas se encargarán por tanto de manipular estos signos. Pero dicha manipulación no puede atender a los significados contextuales de esos signos. Veamos un ejemplo inspirado en el famoso experimento mental de la “habitación china” de John Searle.
Imagínese que tiene un manual de instrucciones para traducir cualquier palabra escrita del idioma urdu al hindi. Estas lenguas son muy parecidas entre ellas, pero usan alfabetos por completo distintos, así que, de un solo vistazo, una misma palabra puede tener dos grafías por completo diferentes. Aun así, ambas hacen referencia a un mismo contenido de la experiencia real. Sin embargo, eso al “traductor” le es indiferente. El manual contiene todas las instrucciones necesarias para hacer la sustitución sin que sea necesario entender ninguno de los dos idiomas. En cuanto reconoce la grafía de una palabra en urdu, nuestro traductor la busca en el manual donde se indica cuál es su equivalente en hindi.
Para el traductor no es necesario comprender la palabra puesto que es una información ya contenida en el manual de instrucciones. Aunque el traductor coja soltura con este procedimiento, creo que estaremos de acuerdo en que esa persona no comprende esos idiomas.
Operaciones sintácticas
Para los seres humanos los signos son marcas o grafías que socialmente han adquirido una conexión con un objeto o realidad a la que representan. Para un ordenador esa conexión no existe. Los signos son todo el universo que “conoce”. Operar con esos signos no puede depender de ninguna asociación con realidad externas al ordenador. Por tanto, a una máquina solo le queda manipular estos signos de forma sintáctica. Puede reconocerlos, cambiarlos de posición, combinarlos, sustituirlos o eliminarlos. Esas son las únicas reglas posibles que son válidas para nuestra definición de algoritmo, y, por tanto, de computabilidad.
Pero no subestimemos la potencia de lo que puede ser computable. Esas reglas pueden llegar a ser muy complejas. Al diseñar un algoritmo, podemos establecer que ciertos tipos de signos se combinen única y exclusivamente con otro tipo de signos y que además lo hagan de una forma específica. Nuestro algoritmo puede contener infinidad de variables, combinadas de formas abrumadoramente complejas. Para muchos científicos, la inteligencia humana, cuyas capacidades parecen superar con creces las de un ordenador en ciertos aspectos, no es más que un algoritmo extremadamente complejo, pero un algoritmo, después de todo.
Una definición más formal
Creo que esta definición de computabilidad que hemos perfilado sigue teniendo flecos sin cerrar, pero ha servido para contextualizar lo que vendrá en las próximas entradas. Ahora tocará explorar el modelo matemático que define formalmente lo que puede ser considerado como computación. Y este modelo no es otra cosa que la Máquina de Turing. Lo que esta máquina es capaz de hacer y la idea de algoritmo o procedimiento computable serán conceptos equivalentes.
Lecturas Recomendadas
– Minsky, M. (1967) Computation. Finite and Infinite Machines.
– Penrose, R. (1994) Las sombras de la mente.
– Feynman, R. P. (1996) Conferencias sobre computación.
