Posts etiquetados ‘Alonzo Church’

Ya comentamos cómo Turing define el concepto de algoritmo mediante las famosas máquinas que llevan su nombre. Así, habría Máquinas de Turing (MT) para encontrar el máximo común divisor entre dos números, resolver raíces cuadradas,ecuaciones de segundo grado… ¡para cualquier acción que pueda realizarse en un número finito de pasos! ¿Podría resolver alguno de los grandes enigmas de las matemáticas propuestos por Hilbert, tal como la peliaguda conjetura de Goldbach?

El genio de Turing se puso en acción: cualquier MT puede codificarse numéricamente. Simplemente se trata de establecer una función entre las instrucciones  de funcionamiento (lo que Turing llamaba la configuración-m) y números. Entonces cada MT tendrá un determinado número de identificación que la diferenciaría de las demás. A partir de aquí puede construirse una Máquina Universal de Turing, es decir, una máquina que pueda hacer lo que todas las demás MT hacen. Si cada MT tiene un código de identificación, podemos hacer una máquina tal que reciba como input tal código e, inmediatamente, devuelva lo que esa MT en concreto devuelve. Si, por ejemplo, le introducimos el código de identificación de la MT que genera la cadena de los números naturales, nuestra nueva máquina devolverá esa misma cadena de números. Esto es una Máquina Universal de Turing (MU), la cual, a su vez, tiene un número de identificación:

7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613

6323593656444434583822268832787676265561446928141177150178425517075540856576897533463569424

7848859704693472573998858228382779529468346052106116983594593879188554632644092552550582055

5989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234

1505698026273468642992183817215733348282307345371342147505974034518437235959309064002432107

7342178851492760079759763441512307958639635449226915947965461471134570014504816733756217257

3446452273105448298078496512698878896456976090663420447798902191443793283001949357096392170

3904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305

47104436869587640517812801194375308138706399427728231564252892375145654438990527807932411448

26142357286193118332610656122755531810207511085337633806031082361675045635852164214865423471

8742643754442879006248582709124042207653875426445413345174856629157429990950262300973373813

7724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006

70086896759034473417412787425581201549366393899690581773859165405535670409281332221631410978

7108145997866959970450968184190629944365601514549048809220844800348224920773040304318842989

93931355266882349662101947161910701461968523192847482034495897709553561107027581748733327296

6789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624

02937487668839751404451665707750060513883991668814072545544665222050724262392379211525318162

51253630509317286314220040645713052758023076651833519956891397481375049264296050100136519801

86945639498

Este es el número U según nos lo ofrece Roger Penrose en La nueva mente del emperador . Tiene 1.653 dígitos y, a priori, prometía ser la leche: en él, de algún modo, se encuentra la solución a todos los problemas matemáticos en tanto que todos los problemas matemáticos tengan solución en una serie de pasos finitos. Y, a pesar de lo que ahora veremos, lo fue: el ordenador desde el que estás leyendo esto es una muy refinada MU (No deja de ser fascinante que lo que en otras épocas fueron descubrimientos que sólo invitaban a soñar, son ahora realidades ordinarias).

Turing utiliza la MU para afrontar el gran problema de la decibilidad de las proposiciones de la matemática (el problema matemático de todos los problemas, el Entscheidungsproblem ): dado una proposición matemática cualquiera, ¿existe un método que nos digera si esa proposición es demostrable dentro del propio sistema? O dicho de otro modo: ¿existe un método que nos digera si la conjetura de Goldbach es demostrable? Turing fabula con la idea de que fuéramos introduciendo en la MU todas las cadenas numéricas posibles (ya que cada una de ellas representaría una MT concreta, aunque, lógicamente la inmensa mayoría darían máquinas absurdas que no funcionan o cuyo funcionamiento es circular). ¿Sería posible diseñar una nueva máquina que, dada una cadena numérica cualquiera, pudiera decidir si la MT que la genera no es circular, es decir, que es una MT perfectamente funcional? Turing llama a esta máquina D (MD). Si esta máquina fuera posible, el problema de la decibilidad (también llamado en este caso “problema de la parada”) se resolvería: la MD sería ese método para decidir, dada una proposición matemática cualquiera, si es demostrable dentro del propio sistema. ¡Las matemáticas serían completas y Hilbert sonreiría de felicidad! Todos los teoremas de las matemáticas estarían allí, como en un mundo platónico, esperando tranquilamente a que una nueva generación de matemáticos los resuelva…  ¡Todos los problemas matemáticos estarían dentro de U!

Pero nuestro gozo en un pozo: no es posible construir MD. Turing da dos pruebas: la primera se basa en la ingeniosa diagonalización de Cantor. Podemos ir agrupando en una tabla con filas y columnas toda la serie de cadenas numéricas que devuelve nuestra MU “cargada” con todas las MT concretas posibles que han sido seleccionadas como válidas por MD. Por ejemplo, tendríamos la secuencia de la MT que genera una serie infinita de unos, la que genera toda la serie de números naturales, etc. como mostramos en la tabla de aquí abajo. Podemos entonces dibujar una diagonal seleccionando el número que hay en la primera casilla de la primera fila, en la segunda casilla de la segunda, en la tercera de la tercera, etc. (en la tabla la marcamos en negrita).

1 1 1 1 1 1 1 1 etc
0 1 0 1 0 1 0 1 etc
1 2 3 4 5 6 7 8 etc
1 3 4 7 9 11 13 15 etc
2 4 6 8 10 12 14 16 etc
3 6 12 24 48 96 192 348 etc
2 3 5 7 11 13 17 19 etc
0 1 8 27 64 125 216 343 etc
1 4 9 16 25 36 49 64 etc

 

Podemos después agrupar los números de nuestra diagonal y hacer una nueva fila en la que, a cada número, le sumamos la unidad:

2 2 4 8 11 97 18 344 Etc+1

 

Realizar esta acción es un algoritmo, ya que seleccionar estas casillas y sumarles la unidad es un proceso que hemos hecho en un número finito de pasos (además corto, por lo que la MT necesaria para hacerla es trivial). Entonces, esta secuencia debería ser generada por nuestra MU “cargada” con todas las MT elegidas como correctas por MD, pero… ¡es imposible que la MU nos de esta secuencia! ¿Por qué? Porque al sumarle uno a una casilla de cada fila, todas las cadenas generadas diferirán en alguna de sus casillas, en una unidad con respecto a esta cadena. Es decir, nuestra MU podrá generar todas las cadenas correctas verificadas por MD, menos, como mínimo ésta… ¡Hay al menos, una cadena que no es decidible desde MU! ¡Se le ha escapado un preso a nuestro robótico vigilante de la corrección! Hilbert saca un pañuelo y se pone a llorar. La MD podría no reconocer la MT que resolviera la conjetura de Goldbach.

La segunda prueba (que a Turing le gusta más que la primera) se basa en la idea de que pudiéramos construir una máquina híbrida: una MU y una MD en la misma máquina (DU). Esta máquina se encontraría como input con una cadena cualquiera que la parte MD verificaría como correcta o no. Si fuera correcta, la parte MU replicaría el funcionamiento de la MT codificada y devolvería la cadena que la MT concreta devuelve. Bien, parece que no hay problema. Pero, ¿qué pasaría si le pasamos como input el mismo número de identificación de la propia DU? MD la verificaría como correcta y la pasaría a MU para que replicara su función, a saber, de nuevo verificar mediante DU si es circular para pasarla luego a MU, la cual activaría otra vez DU, que pasaría la cadena otra vez a MU… así sucesivamente hasta el infinito… ¡Al introducir su código en si misma DU se vuelve circular! ¿Pero no habíamos dicho que DU no era circular al pasar por la verificación de MD? ¿Qué pasa aquí? Una paradoja no muy diferente a la de Epiménides y los cretenses. Definitivamente, hay procesos algorítmicos indecidibles, como ya había mostrado Alonzo Church unos años antes que Turing. Pero no nos pongamos a llorar tan rápido, hay que tener en cuenta que Turing sólo había demostrado la indecibilidad de las matemáticas, no su incoherencia . Como el matemático André Weil dijo:

Dios existe, ya que las matemáticas son consistentes; el demonio también, ya que no podemos demostrarlo.

Si te ha gustado lee también sus precuelas: II y I.

¿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.

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.