Maquina De Turing

MAQUINAS DE TURING
Inicios de la Máquina de Turing
En el año 1931, KurtGödel publicó su famoso artículo Sobre las proposiciones formalmente indecidibles en Principia mathematica y sistemas relacionados, el cual en síntesis demuestra que toda formulación axiomática consistente de la teoría de números contiene proposiciones indecidibles, es decir, siempre habrá en ella afirmaciones verdaderas queno se pueden demostrar.
En 1937, el matemático inglés Alan Turing publicó otro artículo famoso (sobre los Números Calculables), que desarrollo el teorema de Gödel y que puede considerarse el origen oficial de la informática teórica. En este artículo introdujo la Máquina de Turing, una entidad matemática abstracta que formalizó el concepto de algoritmo, convirtiéndose en la precursora de lascomputadoras digitales. Con la ayuda de su máquina, Turing pudo demostrar que existen problemas irresolubles, tales que ninguna máquina u ordenador serán capaces de obtener su solución. Por esta razón, Turing es considerado el padre de la teoría de la computabilidad.En forma general, una Máquina de Turing puede considerarse como una cinta infinita dividida en casillas, cada una de las cuales contieneun símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que, en cada instante, lee un símbolo de la casilla sobre la que está situado. En función del símbolo que ha leído y del estado en que se encuentra, realiza las tres acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del que acaba de leer y se desplaza a una posición hacia la izquierda,derecha, o se detiene.
Qué es una Máquina de Turing y cómo funciona.
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 estan 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 algunaoperació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.

Definición formal
Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla M={Q,Σ,Γ,s,b,F,δ}, donde:
• Q es un conjuntofinito de estados.
• Σ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
• Γ es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. Σ⊆Γ
• s∈ Q es el estado inicial.
• b∈ Γ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
• F⊆Q es el conjunto de estadosfinales de aceptación.
• δ:Q x Γ → Q x Γ x{L,R} 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.
Funcionamiento
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 puedenrealizar en esta máquina se limitan a:
• Avanzar el cabezal lector/escritor hacia la derecha.
• Avanzar el cabezal lector/escritor hacia la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) (nuevo estado, nuevo valor, dirección)
Estos valores toman como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la...