UN POCO DE HISTORIA
En 1936, Alan Turing contestó al entscheidungsproblem, la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. En el artículo On Computable Numbers, Turing construyó un modelo formal de computador, la Máquina de Turing, y demostró que había problemas tales que una máquina no podía resolver. La máquina de Turing es el primer modelo teórico de lo que luego sería un computador programable. Con el tiempo a este tipo de máquina se la conoció como máquina de estado finito, debido a que en cada etapa de un cálculo, la siguiente acción de la máquina se contrastaba con una lista finita de instrucciones de estado posibles.
¿Cómo funciona la máquina de Turing?
Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario.
Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.
Una instrucción típica podría ser: 0111011i
La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moverá hacia la izquierda un paso (la cinta se moverá hacia la derecha).
A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza o acaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que contraer el binario expandido con la siguiente regla:
Empezamos a leer por la izquierda el bianrio expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y lo escribimos. Si encontramos que hay dos 0 seguidos, apuntaríamos un 0 porque no habría ningún 1.Veamos con el 13 cómo se haría. El primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101 que es el número original.
DEFINICION FORMAL DE UNA MAQUINA DE TURING La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a: avanzar el cabezal lector/escritor para la derecha; avanzar el cabezal lector/escritor para la izquierda. Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla M = (Q,Γ,s,b,F,δ), donde Q es un conjunto finito de estados Γ es un conjunto finito de símbolos de cinta, el alfabeto de cinta
es el estado inicial es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces es el conjunto de estados finales de aceptación es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha
