Posts etiquetados ‘Alan Turing’

¿Es este brócoli una computadora?

Que algo sea computable quiere decir que podemos crear un modelo matemático, algorítmico de él. El crecimiento de un brócoli es fácilmente computado por un ordenador, sin embargo, eso no nos hace pensar que el brócoli mismo sea una computadora. Solemos entender que el computador es aquel que emula, del modo más realista posible, el comportamiento de algo real. Así, dividimos la realidad en dos, la platonizamos: lo real y su copia. Y así, nuestros ingenuos informáticos sólo pueden aspirar a diseñar buenas copias de la realidad, pero nunca “seres reales”. Nuestras computadoras podrán pasar el test de Turing, pero eso nunca será “realmente” hablar. Dividimos entre hardware (lo físico, el cuerpo) y software (el programa, el alma), creando sustancias independientes que no nos es imposible volver a casar luego (véase el problema de la comunicación entre sustancias en que se vio envuelto todo el racionalismo moderno) . Sospecho que la arquitectura de computadoras,  la de nuestro querido Von Neumann, basada en estas nociones dualistas resultará, a la larga, infructuosa para construir inteligencia “real”.

En primer lugar hay una objeción: si nuestras copias van siendo cada vez más y más realistas,  ¿no podría llegar el momento en el que el original y la copia sean indistinguibles? ¿No podríamos llegar a agotar la realidad mediante nuestros modelos? La respuesta es complicada, pero negarla implicaría aceptar que los originales tienen una propiedad metafísica que los diferencia de sus copias físicamente idénticas.

Y en segundo lugar, creo que se puede poner en duda la idea de que la realidad computada no sea realmente un computador. Si nos fijamos en nuestro ordenador, una serie de objetos físicos (microchips de silicio, circuitos integrados) hacen la función de puertas lógicas que sirven como base para las computaciones, es decir, que una serie de objetos físicos estructurados de una determinada manera producen cálculo. Asimismo, en el brócoli, al comprobar que el resultado de su crecimiento es una geometría fractal (un cálculo), podemos presuponer que, igualmente, posee una serie de objetos estructurados de una determinada manera tal que producen cálculo (a fin de cuentas, todos estamos formados por átomos). No habría entonces una diferencia sustancial, en este sentido, entre el helecho y el ordenador. La diferencia estaría en la versatilidad: mi ordenador es una Máquina Universal de Turing (capaz de realiza cualquier algoritmo según la tesis Church-Turing)  mientras que el brócoli sería una máquina de Turing particular, sólo capaz de realizar una única tarea.

Pero extendamos la metáfora a toda la realidad… ¿No nos llevaría esto a pensar que el universo podría ser una gran supercomputadora ? No nos haría falta ni demostrar que toda la realidad sea computable. Sólo con que gran parte de ella lo fuera (y creemos que así lo es), tendríamos un supercomputador cósmico.

A fin de cuentas, cualquier obra de arte es un conjunto de unidades discretas en número finito. Pensemos en un poema. Está formado por estrofas, versos, letras, por la combinación de las 28 letras (más signos de puntuación) que conforman nuestro alfabeto. Con suma facilidad, esas 28 letras pueden pasar a un código binario de ceros y unos. Igualmente, si pensamos en una pintura, podríamos hacerla computable si trasladamos al ordenador un plano bidimensional dividido en casillas muy pequeñas (píxeles) a cada una de las cuales se le asigna una intensidad de color.

Si imaginamos una biblioteca de Babel en la que se dieran todas las combinaciones posibles de letras (sería una biblioteca con infinitos libros) tendríamos todos los poemas posibles, tanto los ya escritos como los que  están por escribir. La inmensa mayoría serían amasijos de letras sin sentido, pero allí estarían Lorca, Byron, Neruda… es más, también estarían las obras que ellos imaginaron pero que no llegaron a escribir e, incluso, sus mismas obras mejoradas o enriquecidas, si  es que decir eso tiene sentido.

Sin embargo, esto es imposible. Esa biblioteca jamás podría existir en acto. Volvamos a la realidad y pensemos en un ordenador muy potente que trabaja incesantemente realizando combinaciones de letras. Trabaja a millones de operaciones por segundo, por lo que es cuestión de tiempo que produjera poemas con sentido. El gran problema estaría en cómo la máquina distinguiría buenos y malos poemas, por lo que la tarea de los programadores sería introducir los algoritmos de distinción adecuados. En primer lugar, podría tener un potente diccionario y ciertas reglas gramaticales que le hicieran descartar los batiburrillos de letras sin sentido. Así, no haría combinaciones de letras sino combinaciones de palabras con lo que las posibilidades combinatorias se reducen enormemente. Asimismo,  diferenciaría verbos, sustantivos, adverbios, etc. de tal modo que eliminaría conexiones gramaticalmente incorrectas. Del mismo modo sabría todos los aspectos técnicos de la elaboración de poemas (tipos de poema, estrofas, versos, métrica, rima, etc.).

¿Un Lord Byron mecanico?

Empero, la cosa sigue siendo pobre. ¿Cómo va a distinguir la máquina un buen poema si ni siquiera los humanos tenemos un criterio para hacerlo? Algún criterio hay. Un poema hecho por mí será seguramente peor que el Don Juan de Byron. La tarea del programador sería aquí introducir algoritmos para que la máquina diferenciara elementos estéticos. ¿Cómo conseguir eso? A priori, habría que determinar qué tipo de poema queremos generar pues el mundo de la poesía está lleno de corrientes, tendencias, escuelas. Por ejemplo, supongamos que quisiéramos, simplemente, hacer un poema que emocionara al lector. Sabemos que existen expresiones más emotivas que otras: la palabra lágrima es más emotiva que radiodespertador. Así, tendríamos un archivo jerarquizado con palabras y expresiones que consiguen emocionar, catalogadas también en función del tipo de emoción a conseguir (alegría, tristeza, melancolía, amor, etc.), y que el ordenador combinaría en busca del poema que se adecue mejor a los objetivos. Ésto, en principio, suena muy simple, pero sería ir añadiendo nuevos criterios , restricciones y algoritmos de búsqueda, de tal modo que, al final, seguro que conseguiríamos poemas que pasarían el test de Turing con sobresaliente: nadie diferenciaría si los ha escrito un humano experto o una máquina.

Creo que habitualmente negamos la posibilidad de un computador poético debido a que pensamos que el proceso de creación literaria no obedece a nada computable. Pensamos en cosas como la inspiración, la genialidad, las musas…  discurso tan bonito como místico y falto de racionalidad. El hecho de que no conozcamos con precisión la lógica de la creación artística no implica que no exista. Aquí tendríamos una especie de metafísica de los huecos: donde no entendemos bien, introducimos jerigonza mística.

Otra objeción podría ser afirmar que los artistas no siguen el mismo proceso de creación que nuestra máquina. Lord Byron no probó millones de combinaciones hasta que eligió el Don Juan como la mejor. Seguramente que, por muchas correcciones y variaciones que barajara, Byron lo escribió de una vez, sin ese exponencial proceso de selección, además de los múltiples factores vitales que , evidentemente, influyen en la creación poética: toda la experiencia vital previa del autor, su personalidad, intenciones, etc. Es cierto, pero esta objeción da píe a otra buena idea: ¿por qué nos obstinamos en que las máquinas emulen a los humanos? ¿No tendrán ellas que seguir su propio camino? Muchos proyectos de AI han fracasado por sus utópicas expectativas a la hora de imitar lo humano, mientras que otros, menos ambiciosos han tenido mucho éxito debido a que se ceñían a objetivos diferentes y más realistas (prácticamente todos los artefactos que tenemos por casa no pretender imitarnos).  Las máquinas avanzan, y quizá no hacia nosotros, sino hacia otras formas quizá más sorprendentes y geniales que lo que pueda ser el homo sapiens.

Alan Turing es uno de los padres de la informática

En 1947 el famoso matemático inglés Alan Turing pronunció su polémica conferencia “¿Puede pensar una máquina?“. Frente al dualismo imperante, Turing defendió que era posible que una máquina pudiese llegar a hacer exactamente lo mismo que hace un hombre, incluida la función de pensar. Resulta curioso que algo tan normalizado hoy en día como el hecho de que las máquinas realicen mucho mejor que nosotros ciertas actividades que calificaríamos como inteligentes, hace tan sólo cincuenta años sonara a despropósito irrelevante.

Unos años antes, Turing había publicado un artículo titulado On computable Numbers, with an Application to the Entscheidungsproblem en donde desarrolló la teoría de las máquinas que llevan su nombre y que supondrán un hito para la historia de la informática al suponer el fundamento teórico de los computadores digitales modernos. Bien, ¿y qué es una máquina de Turing?

Antes de nada nos tenemos que acercar al concepto de algoritmo. La palabra procede del matemático árabe Al-Khowarizm, quien escribió en el 825 un tratado de aritmética muy conocido durante la Edad Media. No obstante, antes de él ya se conocían ejemplos de algoritmos. Uno de ellos es el popular algoritmo de Euclides que constituye un procedimiento para encontrar el máximo común divisor de dos números. Se trata de dividir entre sí ambos,  formar una nueva pareja con el divisor y el resto y volverlos a dividir. Así, sucesivamente hasta que se consiga un resto cero. El divisor que quede entonces será el máximo común divisor de ambos números.  El algoritmo de Euclides supone una regla, unas instrucciones para conseguir un resultado, que se obtendrá siempre sean cuales sean ambos números. Si son muy altos, el procedimiento tendrá más pasos, nada más. De este modo, todas las operaciones aritméticas son algoritmos (sumar, multiplicar, raíces cuadradas, elevar a una potencia…). Todas consisten en realizar un pequeño número de instrucciones que se repetirán cuantas veces sean necesarias para llegar a una conclusión. Entonces, un algoritmo se podría definir como un conjunto de instrucciones para realizar una tarea con las siguientes características:

1) Precisión: un algoritmo ha de estar definido con suficiente precisión para no albergar dudas sobre qué paso seguir.

2) Simplicidad: las reglas son sencillas. Cuando se trata de algoritmo, en apariencia sencillo, se puede descomponer en algoritmos más elementales. El de Euclides, por ejemplo, se puede descomponer en divisiones y agrupamientos divisor-resto.

3) Finitud: el número de reglas ha de ser finito mientras que el número de operaciones que pueden realizarse debe ser infinito.

4) Carácter mecánico: es un procedimiento mecánico, automático. Un algoritmo no requiere ninguna agudeza mental ni ingenio creativo, es algo que cualquier persona puede hacer con sólo tener la capacidad de seguir y obedecer reglas.

5) Procedimiento general: los algortimos están orientados a la solución de problemas, pero no tendría mucho sentido diseñar uno para solucionar un único problema particular (imaginemos crear un algorítmo para multiplicar 45 por 678 y nada más). Está en la naturaleza del algoritmo ser un mecanismo lo más sencillo y económico posible para realizar correctamente muchas tareas. Sin embargo, como la dificultad para realizar muchas tareas diferentes por un mismo algoritmo es mucha, se los suele utilizar para resolver un tipo de problemas. Así, el algoritmo de Euclides soluciona todos los casos posibles del problema de encontrar el máximo común divisor.

En 1936 el matemático norteamericano Alonzo Church (1903-1995) va a plantear la primera definición Alonzo Church es el creador del Cálculo Lambdamatemática de algoritmo. Su tesis principal es que la clase de las funciones calculables por un algoritmo es idéntica a la clase de las funciones recursivas. Church demostró (bueno, no era del todo una demostración…) la imposibilidad de encontrar un algoritmo para la teoría elemental de la aritmética y, en consecuencia, para la lógica de predicados de primer orden: tanto la aritmética como la lógica de primer orden resultaban indecidibles. El mismo resultado fue obtenido al mismo tiempo por Turing con sus máquinas, utilizando el concepto de función computable: una función tal para la que existe una máquina de Turing que proporciona el valor de la función. Con estos conceptos Church, Turing y otros (Post, Markov) habían llegado a la misma conclusión que Kurt Gödel unos años antes: el programa de Hilbert había fracasado.

Bien, pero vayamos a lo que nos interesaba: ¿Qué es entonces una máquina de Turing? Bien, Turing quería abordar de una forma rigurosa la noción de algoritmo o procedimiento mecánico. Así, imaginó cómo podría formalizarse el concepto de una máquina descomponiendo su modo de operar en sus pasos más elementales. Así que una máquina de Turing (MT) no es algo físico, no es una máquina de verdad (por mucho que los actuales ordenadores se basen en ella), sino un constructo, un experimento mental. ¿Cuáles son las partes elementales de la MT?:

1) Unidad de control: el el conjunto finito de todos los posibles estados internos. Una MT puede asumir diferentes estados dependiendo de las circunstancias que tiene lugar en el estado de computación.

2) Cinta: se trata de una cinta de longitud intinita tanto por la izquierda como por la derecha, dividida en celdillas de forma que en cada celdilla sólo cabe un único símbolo. En la cinta aparecerán los caracteres de un alfabeto previamente definido agrupados en cadenas. Las cadenas serán siempre finitas a pesar de la infinitud de la cinta. Esa infinitud expresa que en ella podemos escribir tantas cadenas como queramos y de cualquier longitud.

3) Cabeza: la unidad de control está conectada a la cinta mediante la cabeza, cuya función es la de observar en cada momento una sola celdilla escrita con un único símbolo. La cabeza lee, escribe, sustituye y borra un símbolo cada vez, además de hacer que la cinta se desplace una celdilla a la izquierda o a la derecha, de acuerdo con las instrucciones correspondientes.

4) Instrucciones: una MT se dirige desde un número finito de instrucciones numeradas. Una instrucción está formada por un cuadruplete de símbolos, dividido en dos partes. La primera describe una situación condicional (Si pasa esto…) y la segunda el cambio a operar (…entonces lo otro). El primer símbolo y el último siempre son estados (S0, S1, S2,…, Sn), siendo los símbolos intermedios las acciones dadas y a realizar respectivamente. Por ejemplo, si nos encontramos la instrucción “1. S0, a, b, S1”, lo que hay que leer es: “Si la cabeza lee una a, entonces escribe una b y pasa al estado S1″.

Teniendo todos los componentes veamos algunos ejemplos. Vamos a construir una MT capaz de traducir de una lengua dada a otra (letra por letra). La máquina va a disponer de dos vocabularios:

A1={a,b,c} y A2={x,y,z}

Queremos que cuando la MT vea una a, la traduzca a una x, una b a una y y una c a una z. Las instrucciones serían las siguientes:

1. S0, a, x, S1

2. S1, x, I, S0

3. S0, b, y, S1

4. S1, y, I, S0

5. S0, c, z, S1

6. S1, z, I, S0

El estado inicial de la MT siempre es el So, siendo los restantes S1, S2, S3,…, Sn. Cuando la máquina se encuentra en la cinta con una a la traduce por una x y se va al estado S1. En S1, la MT lee x, avanza hacia la izquierda (las instrucciones de movimiento son I para la izquierda y D para la derecha. Borrar se escribe #) y vuelve al estado S0. Hay que tener en cuenta que cada estado es un condicional que si no se cumple, la máquina va bajando, estado por estado, hasta encontrar alguno que se cumpla. Por eso si la máquina vuelve a S0 pero en la cinta no hay una  a, irá bajando hasta encontrar un estado que represente lo que hay en la cinta.

Veamos otro ejemplo. Vamos a construir una MT que sea capaz de realizar sumas de dos sumandos utilizando un sistema numérico con base unaria. Es decir, vamos a hacer que nuestra máquina sume palitos. Las entradas que recibirá la MT serán de esta forma: “#///#//#”, lo cual significará suma tres más dos, de tal modo que la máquina responderá “#/////#”.  El lenguaje será entonces A={/,#} y las instrucciones:

1.S0, /, I, S0

2. S0, #, /, S1

3. S1, /, D, S1

4. S1, #, I, S2

5. S2, /, #, S2

Como vemos la numeración de los estados puede repetirse. Al construir esta MT hemos elaborado un algoritmo para sumar dos sumandos tal que puede sumar potencialmente cualquier cantidad de números que se agrupen de dos en dos. La máquina de Turing es equivalente al concepto de algoritmo, que es de lo que se trataba. Así hay que distinguir lo que se denomina una Máquina Universal de Turing, que es la formulación rigurosa de computación o algoritmo, de la de Máquina de Turing sin más, que es cualquier máquina para realizar una tarea cualquiera.

Cuando yo estaba en la facultad recuerdo haber diseñado una MT que era capaz de codificar y decodificar lenguajes en función de una clave numérica recibida (quería emular tontamente a la Enigma alemana, haciendo una máquina para escribir mensajes cifrados). Como el abecedario tenía demasiadas letras, y la MT trabaja de modo pesado y poco eficiente, sólo lo hice con las tres primeras. El número clave indicaba, emulando al método de cifrado Julio Cesar, las posiciones que había de rotar las letras (si la letra era a y la clave 2, la a se sustituía por la b). El profesor me puso un sobresaliente pero no me devolvió la máquina. Viendo retrospectivamente, ahora no me parece tan difícil de construir como cuando la hice y no entiendo por qué estuve tanto tiempo muy orgulloso por el logro.

Y para acabar y poneos un pequeño reto (es muy, muy fácil): teniendo un lenguaje similar al anterior A={/, #}, ¿sabriáis construir una MT capaz de responder S (Sí) o N (No) al hecho de encontrarse con un número divisible o no por dos?

P. D.: Los de LEGO han construido una MT real. Aquí la tenéis, con todas sus partes y aderezado el vídeo con la música del Equipo A.