Alan Turing introdujo el concepto de Máquina de Turing en su trabajo «On computable numbers, with an aplicacation on the Entscheidungsproblem», publicado en 1936 por la Sociedad Matemática de Londres con el cual demostró que existían problemas que una máquina no podía resolver. El mismo es un modelo computacional que realiza una lectura/escritura de manera automática en una entrada llamada cinta generando una salida en esta cinta.
Add Normal tras corte
Estudiando la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, Alan Turing introdujo el concepto de Máquina de Turing en 1936. El científico inglés ideó el modelo formal de computador y demostró que existían problemas que una máquina no podía resolver.
Con este sencillo aparato es posible realizar cualquier cálculo que un computador digital sea capaz de realizar. Mediante este modelo teórico y el análisis de complejidad de los logaritmos, se puedo categorizar problemas de acuerdo a su complejidad.
¿Cómo funciona la Máquina de Turing?
La máquina de Turing consta de un cabezal de lectura y escritura y una cinta en la que el cabezal lee el contenido, borra lo anterior y escribe un nuevo valor. Las únicas operaciones que se pueden hacer en este modelo de Alan Turing son: Mover el cabezal hacia la derecha y Mover el cabezal hacia la izquierda.
El cómputo se origina a partir de una tabla de estados, la cual toma como parámetros el estado actual de la máquina y el carácter que se encuentra en la cinta, dando la dirección para mover, un nuevo estado y el valor a escribir.
La memoria de la Máquina de Touring es la cinta que se divide en espacios de trabajo denominados celdas. En un principio las celdas contienen un símbolo que está en blanco. Las instrucciones son las que determinan como debe actuar. Por ejemplo «si estamos en el estado x, leyendo la posición y donde está escrito el símbolo z, reemplazarlo por tal símbolo y leer la celda siguiente, sea esta a la izquierda o a la derecha».
Puede considerarse que la Máquina de Alan Turing es como un autómata que reconoce lenguajes formales. es capaz de reconocer lenguajes recursivamente enumerables de acuerdo a la jerarquía de Chomsky, por lo que su potencia es superior a otros tipos de autómatas como el finito, con pila.
Para conocer más sobre Alan Touring y Christopher Morcon puedes visitar su biografía.
Hoy en Dulces prejuicios: homenaje a Turing
Víctima del prejuicio