Para todos aquellos que no lo conozcáis aun, el padre de la informática moderna fue un Ingles llamado Alan Turing (1912-1954) que fue un matemático, criptógrafo y un teórico de la computación que, además de trabajar en el equipo que descifró los códigos Enigma en la segunda guerra mundial, y trabajo en el proyecto colosus que fuñe el primer ordenador con arquitectura Von Newman construido.
Además es uno de los padres de la inteligencia artificial, y en 1950 publico un articulo revolucionario sobre los límites de las maquina y la inteligencia artificial, su titulo era Computing Machinery and Intelligence y exponía el test que lleva su nombre que sirve para medir si una maquina piensa.
Pero hoy no os voy hablar del test de Turing, ni de su trabajo como criptógrafo, que de por si ambos temas dan para sendos apasionantes artículos, sino que os voy a contar de una forma ligera que es y cómo funcionan las maquinas de Turing.
Podemos definir una maquina de Turing como una cinta infinita, dividida en celdas consecutivas, cada una de estas celdas tiene un 1 o un 9, lenguaje binario. Además esta máquina tiene un dispositivo muy sencillo que puede leer o escribir un digito y desplazarse a lo largo de la cinta.
El comportamiento de esta máquina esta determinado por un conjunto finito de estados internos y el valor que se lee en la cinta.
Posee una función de transición que es la que define el comportamiento de la maquina.
Sin querer entrar en demasiados detalles técnicos os cuento como funciona un ciclo básico de ejecución de una maquina de Turing:
- Se lee el símbolo actual apuntado por el dispositivo.
- Se calcula el siguiente estado a partir del estado actual y del símbolo que hemos leído en el anterior paso. En caso de llegar a un punto en el que no haya una transición definida la maquina se para.
- Se escribe un símbolo en la posición en la cual se encontraba el símbolo actual, siguiendo la función de transición.
- El dispositivo se desplaza a la derecha o a la izquierda según el valor que le da la función de transición.
- Se vuelve al primer paso.
Esta máquina que parece tan sencilla no obstante nos marca el límite de la computación, cualquier cosa computable se puede procesar en una maquina de Turing.
Post relacionados:
