Posts etiquetados ‘Máquina de Turing’

El funcionalismo es la postura filosófica de la actual psicología cognitiva. Por ende, también lo es de la mayoría de los ingenieros en Inteligencia Artificial. Es, por tanto, una postura compartida por gran parte de la comunidad científica dedicada al tema de la mente, el stablishment contemporáneo (donde más disidencias hay es entre los neurólogos y, como no podría ser de otra manera, entre los filósofos). Vamos a elaborar un pequeño análisis crítico viendo sus ventajas pero, sobre todo, los inconvenientes que hacen de esta posición algo inviable y subrayando como conclusión la disyuntiva entre abandonarla por completo o reparar algunas de sus partes.

Todo surge con el problema epistemológico de la mente. Si la psicología pretendía ser una disciplina científica, tenía que hacer de la mente un objeto de estudio claro y preciso, algo cuantificable, observable empíricamente. Como no podía, decidió hacer como si la mente no existiera. Eso es el conductismo: entender la psicología como la ciencia de la conducta (algo que sí puede observarse), por lo que intentó explicarlo todo mediante el binomio estímulo-respuesta (sin nada entre ellos). El fracaso fue rotundo, por lo que surgieron alternativas: una es la teoría de la identidad en sus distintas vertientes. Los defensores de la identidad sostienen que los estados mentales son idénticos a procesos neuronales. Un estado mental es exactamente lo mismo que una red neuronal concreta en funcionamiento. La virtud de esta perspectiva es que es perfectamente monista y materialista y casa a la perfección con los avances de las neurociencias. Además, su negación, parece absurda: ¿qué si no van a ser los pensamientos que sucesos neuroquímicos? Sin embargo, tiene dos problemas bastante graves:

1. Que sepamos, no hay nada en las reacciones físico-químicas de una red neuronal que pueda explicar, ni remotamente, un pensamiento o  una sensación. Las descargas eléctricas de los potenciales de acción que recorren los axones de las neuronas o las reacciones químicas que se dan en las sinapsis no son estados mentales.

2. Ponemos en problemas a los ingenieros de IA. Si un estado mental es idéntico a un estado neuronal, no es idéntico al proceso computacional que se da en un ordenador. Únicamente los seres con un sistema nervioso similar al humano podrían tener estados mentales. Las máquinas no.

HilaryPutnam

Y entonces llegó el funcionalismo, como una reacción al conductismo y como una solución a los problemas de la teoría de la identidad.  La clave está en definir los estados mentales como estados funcionales. ¿Qué quiere decir esto? Que un estado mental es siempre algo que causa un efecto o que es efecto de una causa, y se define exclusivamente por su función. Por ejemplo, un dolor de muelas es un estado mental porque es la causa de que yo me tome un analgésico. Uno de los fundadores del funcionalismo (si bien luego se retractó y se volvió muy crítico con su criatura) fue Hilary Putnam, quien entendió lo que era un estado mental a través de la tablatura de programa de una máquina de Turing. Este tipo de máquina, además de una definición de computabilidad, es un ordenador primitivo, una máquina capaz de hacer cálculos. Putnam afirmaba que las diversas órdenes que el programa da a la máquina son estados mentales (ya que tienen poderes causales). Esta concepción podría parecernos extraña a priori, pero soluciona un montón de problemas:

1. Para el funcionalismo, la relación entre estados físicos y mentales no es de equivalencia sino de superveniencia. Dos entes físicamente idénticos tienen los mismos poderes causales (realizan las mismas funciones), pero una misma función puede ser realizada por diferentes entes físicos. Dicho de otro modo: misma materia implica misma función pero misma función no implica misma materia. El funcionalismo con su superveniencia parece una gran idea: incluye la mente olvidada por el conductismo, salva la objeción de la teoría de la identidad hacia la Inteligencia Artificial, a la vez que no se lleva mal con la misma teoría de la identidad. Veamos eso más despacio:

a) El conductismo tenía un embarazoso problema con lo que llamamos estados intencionales o actitudes proposicionales (por ejemplo, las creencias o los deseos). Como prescindía de todo lo que no fuera conductual, no podía explicar el poder causal de una creencia. Por ejemplo, si yo creo que va a llover y por eso me pongo un chubasquero, una creencia causa mi conducta. Para el conductismo, como una conducta (respuesta) solo podía ser causada por otra conducta (estímulo) las creencias no podían causar nada, así que los conductistas no podían dar cuenta de algo tan sencillo y habitual como ponerse un chubasquero porque va a llover. El funcionalismo no tiene problemas con las creencias: una creencia es causa de un efecto, por lo tanto, es un estado mental.

b) El funcionalismo permite que los ingenieros de IA construyan máquinas con estados mentales. Siguiendo a Putnam, la orden que da un programa a un computador es un estado mental que puede ser idéntico al de un humano si cumple la misma función, a pesar de que el sistema físico que los genera es diferente (uno de silicio y otro de carbono). Es la gran virtud de la relación de superveniencia.

c) El funcionalismo permite cierta independencia a la psicología sobre la neurología. Como lo explica todo en términos funcionales, permite que no tengamos que hablar siempre en términos neuroquímicos. Por ejemplo, para explicar que la creencia de que llueva ha causado que me ponga un chubasquero, no es preciso que hable en términos de axones y dendritas. Puedo decir que la creencia causa mi conducta con funciones claramente adaptativas: si me mojo puedo ponerme enfermo y morir. Predecir el clima tiene una clara función adaptativa. Así, el funcionalismo se lleva fantásticamente bien con la psicología evolucionista, ya que ésta, igualmente, explica la mente en términos adaptativos, es decir, de funcionalidad biológica. Los funcionalistas permiten que la psicología pueda hablar en un lenguaje que no se reduce al fisicalista, lo cual es fantástico para los psicólogos, ya que no tienen que estar constantemente mirando por el microscopio y hablando de neuronas.

d) El funcionalismo es perfectamente compatible con la neurología. No tiene problema alguno en admitir que un estado mental es idéntico a un estado neuronal, sencillamente, puede hablar de él sin que la ciencia haya descubierto aún tal identidad. Podemos decir que la creencia en que va a llover causa que yo me ponga un chubasquero, aceptando que la creencia en que va llover es idéntica a un estado neuronal concreto y reconociendo que aún la neurología no ha descubierto tal estado neuronal. Incluso si la neurología descubriera cada correlato neural de todos nuestros estados mentales, el funcionalismo podría seguir hablando en términos funcionales sin contradicción alguna. Simplemente diría que mi creencia es un estado neuronal x que, igualmente, causa que yo me ponga mi chubasquero, lo cual tiene una función claramente adaptativa.

e) Incluso el funcionalismo no tiene ningún compromiso ontológico con el monismo materialista. Podríamos ser funcionalistas y dualistas. Un estado mental podría no ser algo material y tener, igualmente, poderes causales sobre mi conducta. Algunos dualistas que, por ejemplo, para explicar la mente se basan en la distinción informática entre hardware (base física) y software (programas), sosteniendo que mientras el hardware es material, el software no lo es, pueden ser perfectamente funcionalistas. Por el contrario, si un funcionalista quiere ser materialista, solo tiene que añadir otra condición a la tesis de que los estados mentales son funcionales, a saber, que toda relación causal es material, que una causa y un efecto siempre son dos entes materiales. ¡El funcionalismo vale para todos los gustos!

Comprobamos que el funcionalismo es una gran teoría debido a sus grandes ventajas. De aquí su éxito en la actualidad. Sin embargo, tiene dos serios problemas, a los que a día de hoy, nadie ha encontrado una solución satisfactoria:

1. El problema de la conciencia fenomenológica o de los qualia. El funcionalismo no puede explicar de ninguna manera el hecho de que tengamos sensaciones conscientes (sentience). Cuando me duelen las muelas y, debido a ello, me tomo un analgésico, siento conscientemente el dolor de muelas. Una computadora no siente ningún dolor cuando algo falla en su sistema, aunque lo detecte y tome medidas para repararlo. Una computadora, a pesar de que pudiese tener una conducta muy similar a la humana, no siente que hace lo que hace, no desea hacerlo, no se enfada ni se pone nerviosa cuando se equivoca… ¡Una máquina no es consciente de absolutamente nada! No poder dar cuenta de la distinción entre estados conscientes e inconscientes es un gravísimo problema del funcionalismo: ¿por que la selección natural ha gastado tantos recursos en hacer que sintamos cuando podría haber conseguido lo mismo generando organismos totalmente inconscientes? Es la objeción de los zombis de Chalmers ante la que el funcionalismo calla.

2. El problema semántico expuesto por John Searle.  Estamos ante el archiconocidísimo argumento de la caja china que no voy a entrar a explicar. La idea tiene como trasfondo el concepto de intencionalidad de Franz Brentano: los estados mentales tienen la cualidad de siempre referirse a algo que no son ellos mismos. Su contenido siempre es otra cosa diferente a ellos, siempre apuntan a otra cosa. En este sentido, los estados mentales son simbólicos. Si analizamos el funcionamiento de un ordenador, la máquina trata todo con lo que trabaja como objetos físicos y no como símbolos. Un computador que traduce del español al chino, no entiende realmente ninguno de los dos idiomas. Trata las palabras como objetos físicos que intercambia siguiendo unas pautas sin entender nada de lo que está haciendo. La conclusión de Searle es que las máquinas no tienen semántica sino tan solo sintaxis. Es un argumento bastante fuerte y aunque se han hecho muchos intentos de refutarlo, ninguno lo ha conseguido del todo.

FranzBrentano

No he conocido ninguna teoría que, ya desde su comienzo, no haya tenido serios problemas. El funcionalismo no es diferente, pero debe resultarnos chocante que el sustrato filosófico que hay debajo de la psicología actual más comúnmente aceptada por la comunidad científica sea deficiente. A mí no deja de resultarme difícil de digerir como conocidos científicos cometen errores garrafales por no tener ni idea de lo que están hablando cuando hablan de la mente. Entre otros, me refiero al popular Ray Kurzweil, el cual ignora completamente la filosofía de la mente a la vez que habla constantemente de temas por ella tratados (y además, tiene el atrevimiento de decir que muy pronto vamos a construir una mente indistinguible de la humana). Nos quedan dos alternativas: o lo abandonamos completamente y pensamos algo radicalmente nuevo (o volvemos a otras posturas más viejas), o intentamos arreglar los desperfectos. Hay algunos intentos: por un lado está el interesante materialismo anómalo de Donald Davidson o, el mismo David Chalmers de los zombis, quien intenta una especie de compatibilismo entre los qualia y el funcionalismo. Hablaremos de ellos otro día.

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.

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.