Guía de aunmas.com sobre Inteligencia Artificial - La Máquina de Turing

 
Home Webmaster Support References
I-Websites
I-DB's
I-Graphic
I-Maps
I-PC & Networks
I-Program
System Design



La Máquina de Turing
Juan Chamero, Editor Jefe de aunmas.com
Revisado y corregido a Junio del 2008




La Tabla de Acciones de la Máquina de Turing "El castor laborioso"
con su correspondiente grafo direccionado


Primeros razonamientos

Conceptualmente la Máquina de Turing puede imaginarse como un autómata muy elemental con capacidad de lectura y grabación de unos pocos símbolos pertenecientes a un conjunto de símbolos sobre una cinta de longitud ilimitada. A fin de mecanizar el proceso se lo hace por pasos secuenciales, medidos en unidades de tiempo, por ejemplo, un segundo. un micro segundo, un nanosegundo. En cada paso el autómata podrá leer el contenido de un "pedacito" de cinta, siempre de longitud fija, por lo que podemos decir que la cinta está dividida en celdas.

La "programación" del autómata será también muy limitada, en términos lógicos reducida al manejo de unos pocos silogismos hipotéticos del tipo SI (x) ENTONCES (z), donde (x) será una las posibles ocurrencias y (z) una de las posibles acciones. Las ocurrencias más simples imaginables serían "leer un 0" o "leer un 1" o dos símbolos cualesquiera: 0, 1 o blanco, negro. Ahora bien, un mecanismo de esta naturaleza no nos sería de mucha utilidad pues las posibles acciones (z) serían solo dos, una para la ocurrencia x=0 y la otra para la ocurrencia x=1.

La genialidad de Turing

Acá es donde aparece el genio humano. Para poder hacer algo útil y no caer en un círculo vicioso creando una máquina que no hace nada se necesita una mayor diversidad de acciones posibles y que intente emular nuestro "libre albedrío". En una cinta que se mueve de a una celda por vez (paso) las acciones básicas, independientemente de la lectura-grabación, son dos: ir un paso hacia la izquierda o uno hacia la derecha (o no hacer nada, quedándose en el mismo lugar).

Pero para hacer algo trascendente habría que transformar el "contenido" de la cinta, ¿no es así?. Y para cambiar el contenido de la cinta habría que poder, como mínimo, cambiar al cero por un 1 y viceversa. Aún así, y ya hemos progresado bastante en nuestro razonamiento, todavía nuestra máquina no puede ser calificada de muy inteligente como podrán comnrobar fácilmente haciendo algunos ensayos. Lo ideal sería que la máquina no siempre hiciera lo mismo y que al menos aparentemente no fuera demasiado predecible, sino que tuviera algo asimilable al "humor" y que dependiendo de ese humor cambiara su accionar.

Turing piensa entonces (¡o suponemos que lo pesnó!) en un autómata que tuviera estados, asimilables a estados mentales y que en cada uno de esos estados "reacionara", dentro de sus posibilidades mecánicas, de acuerdo a lo que ve y de acuerdo "adonde está parado" como suele decirse. Si la variedad de símbolos fuera dos y la máquina tuviera (n) estados habría (2n) acciones posibles. Pero no cantemos victoria, aún nuestra máquina no funciona, al menos en forma inteligente. El ser humano cambia de estado por las "circunstancias", por lo que el medio le exige, por "donde y cómo está parado" y, a la larga, por su historia acumulada.

Supongamos tener 4 estados. ¿Cómo transitaríamos por los cuatro estados, al menos una vez por cada uno de ellos?. Maneras hay varias, por ejemplo podemos salir siempre del estado 1 y pasar al estado 2 solo si vemos un 0. ¿Y del estado 2 al 3?. Pues por un mecanismo similar, por ejemplo si vemos un 1. Siguiendo este razonamiento podrísamos crear una máquina cuya actuación dependa de lo que ve y del estado en el que se encuentra, algo muy adecuado al comportamiento de los seres sintientes como nosotros.

Tratemos de captar en el tiempo una acción humana en respuesta a un estímulo dado, por ejemplo interceptar una pelota en una partida de tenis. La ación de intercepción de la pelota va a depender de lo que vemos (una pelota de tenis que se nos aproxima a una velocidad estimada en 140 kilómetros por hora) y de nuestra posición y estado biomecánico del cuerpo al momento estimado de la intercepción. El medio segundo que media entre la percepción y la respuesta podríamos descomponerlo en mil pasos y resulta evidente que nuestro cuerpo irá sincronizadamente pasando por una secuencia de mil pasos y que el estado del paso 150 es determinante del estado del paso 151 y en función de cómo nuestro programa interno -afortunadamente autónomo- nos diga cómo viene el proyectil.

Estamos ya en condiciones de apreciar la iluminación de Turing (a la distancia cai diríamos micro-iluminación ¿no?) que crea su máquina de forma tal que ¡el estado próximo va a depender del estado que teníamos y de lo único que ha cambiado, es decir lo que "vemos" en un momento dado!. Después de todo Einstein tuvo una micro-iluminación parecida cuando se dió cuenta que solo podía hablarse de "simultaneidad" de fenómenos "locales", es decir, detectados y medidos como simultáneos con un mismo reloj local. La ciencia avanza justamente en base a estas microgenialidades de muy baja probabilidad. Luego de estas iluminaciones como las de Von Neumann cuando se le ocurre dividir el tiempo de las máquinas secuenciales en dos fases, la de análisis de lo que hay que hacer y la de ejecución, parece ¿tonto no?.

Componentes de una Máquina de Turing

veamos ya los componentes de ésta máquina elemental pero inteligente.
  • Una CINTA de longitud ilimitada dividida en celdas que pueden contener un símbolo de un conjunto finito de símbolos, un "alfabeto", como mínimo dos símbolos, uno para designar "no-contenido" o B, por blanco, y un símbolo activo, por ejemplo un 1. A máuinas de Turing de un solo símbolo activo se las denomina "Unarias".

  • Una CABEZA de lectura-grabación (se puede concebir la máquina moviéndose ya la cinta o la cabeza) que puede leer o grabar sobre la celda enfrentada y dentro del mismo intervalo unitario de tiempo (paso) moverse una posición a la derecha o a la izquierda.

  • Una TABLA de acciones con instrucciones que en función del estado actual de la máquina y el símbolo que la cabeza ve en la cinta instruye a la máquina en ese paso:
    • 1. borrar o grabar un símbolo;
    • 2. Mover la cabeza (o la cinta) hacia la izquierda (L) o hacia la derecha (R) una posición;
    • 3. permanecer en el mismo estado o cambiar a otro.
    • Las entradas de esta tabla son 5-uplas o 4-uplas dependiendo del tipo de máquina, de uno o dos ciclos por paso.

  • Un REGISTRO DE ESTADOS que guarda el estado activo en cada momento. En las máquinas de Turing se define un "estado incial".


Lo importante es que esta simple máquina puede realizar cualquier operación lógica y matemática de las computadores actuales. ¡Todo es cuestión de tiempo!.

Interpretación del programa

Estamos ahora en condiciones de interpretar el “programa” esquematizado arriba?. Por supuesto que sí. Procedamos a “leer” lo que dice el “grafo diseccionado” ayudándonos ahora con la tabla de acciones.

Comenzamos (start) yendo a estado A. Si vemos un 0 pues grabamos un 1 y nos corremos una posición a la derecha (R). Esto se representa como [0/P,R], donde por P vamos a entender siempre grabar un 1. Si en lugar de un 0 estando en estado A viéramos un 1 sería aparentemente una excepción pues nos vamos a estado C.

Estando en B adonde llegamos siempre que la máquina vea un 0, ya sea desde A o desde C, si vemos un 0 grabamos un 1, y retrocedemos yendo hacia la izquierda L) cambiando a estado A [0/P,L]; si en cambio vemos un 1, grabamos un 1, seguimos avanzando un paso a la derecha, pero en cambio permenecemos en el mismo estado B;

Estando en C adonde solo llegamos desde A “retrocediendo” (L), continuamos el proceso –ya a esta altura nos hemos dado cuenta que como autómatas estamos inmersos en un proceso de tipo recursivo-simpre que veamos un 0 y nos detenemos si_y_solo_si, después de este retroceso vemos nuevamente un 1 y continuamos en caso contrario.

Ejecución del programa




La cabeza está en el medio, celda 8 a partir de la izquierda. Está máquina de dos símbolos y tres estados genera 6 "troncos" (1) en 14 pasos, como veremos a continuación.

1. está en A, ve un 0, graba un 1 y lo desplaza a la derecha: pasa a B; [1]
2. está en B, ve un 0, graba un 1 y retrocede: pasa a A; [11]
3. está en A, ve un 1 (ya había un 1), lo confirma, se desplaza a la izquierda y pasa a C; [11] 4. está en C, ve un 0, graba un 1 y retrocede: retorna a B; [111]
5. esta en B, ve un 0, lo convierte en 1 y sigue el retroceso, pasa a A; [1111]
6. esta en A, ve un 0, lo concvierte en 1, avanza un paso, se queda en B; [11111]
7. ve un 1, lo regraba y sigue avanzando, queda en B; [11111]
En pasos 8, 9 y 10 la máquina sigue quedando en B pues ve unos, hasta el paso 11; [11111]
11. ve un 0, luego lo convierte en el sexto 1, retrocede una posición y pasa a A; [111111]
12. esta en A, ve un 1, lo confirma, retrocede y pasa a C; [111111]
13. está en C, ve un 1, lo confirma, avanza y PARA (H); [111111]
14. Máquina detenida.



   Home   Contact us   References   Webmaster 
    Copyright © 2002-2007 Intag! Inc. All rights reserved.