La máquina de Turing-La teoría de la computación y la Máquina de Turing.

• Alan Turing, establece la relación entre la lógica y la computación electrónica, plantea la famosa Máquina de Turing, la cual es la base de la Teoría de la Computación actual.

• Turing es, considerado El padre de la Teoría de la Computación. 
• El punto de partida de la teoría de la computación fueron las cuestiones fundamentales que David Hilbert (1845-1918) formuló en 1928, el "Entscheidungsproblem".

• Las primeras noticias en contra surgen en 1931 con Kurt Gödel (1906-1978) y su Teorema de Incompletitud (1931): "Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo".

• Los resultados de Gödel prueban que no sólo no existe un algoritmo que pueda demostrar todos los teoremas en matemáticas sino que además no todos los resultados son demostrables.

LA MÁQUINA DE TURING

• La máquina de Turing es una caja negra (Tan simple como una máquina de escribir y tan compleja como un ser humano) Capaz no sólo de leer y escribir un alfabeto de símbolos finito a partir de una cantidad finita pero muy grande de cinta de papel, sino de modificar su propia configuración o "Estado mental".

• La máquina de Turing se convirtió en un instrumento ideal para probar si un procedimiento es efectivamente computable o no.
• Es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos.

FUNCIONAMIENTO

• Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de una cinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1.

• 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: 01->11011i

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.