Maquina De Turing

Maquina de Turing

Concepto

Proceso mediante el cual toda cuestión matemática pueda ser demostrada. Esta pregunta, llamada entscheidugsproblem, fue formulada por David Hilbert en el Congreso Internacional de Matemáticos de 1900.

Turing analizó que era lo que hacía una persona para transformar un proceso metódico, y buscar una forma de hacer esto mecánicamente. Expresó el análisis en términos de una máquina teórica que sería capaz de transformar con precisión operaciones elementales previamente definidas en símbolos en una cinta de papel. 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 Agosto de 1936 presenta el concepto final de la Maquina de Turing en su artículo On Computable Numbers.

La Máquina de Turing demostró que había problemas tales que una máquina no podía resolver y 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.

Funcionamiento

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. Ejemplo.

Una instrucción típica podría ser: 01110111

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

...