MAQUINAS DE TURING
DEFINICIONES BASICAS.
La maquina de turing no es un objeto físico, sino un artificio matemático que nos proporciona un modelo de computación en el cual encuadramos el análisis de nuestros algoritmos. La máquina de Turing fue introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres en 1936, en el cual se estudiaba 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. Turing construyó un modelo formal de computador, la máquina de Turing, y …ver más…

Estas instrucciones representan en cierta forma el "programa" de la máquina. Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos: o Leer un carácter en la posición actual. o Escribir un nuevo símbolo en esta posición (puede ser el mismo que había). El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual. o Desplazar el cabezal una celda a derecha o izquierda (R/L); en algunos modelos el desplazamiento puede ser nulo (detener H). o Decidir cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual. Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento.
Para comprender mejor, vamos a ver un simple ejemplo: sea la máquina de Turing capaz de leer o escribir los símbolos 0 y 1 en la cinta (en la definición original de Turing, el número de símbolos a usar podía ser cualquiera, con la única condición de ser un número finito, y no tenían por qué ser números; sin embargo, en aplicaciones prácticas se suelen limitar a estos dos), y que puede tener los estados A, B y C (una máquina de Turing puede tener cualquier número de estados; la única condición es que sea un número finito). Supongamos que definimos la siguiente tabla:

La cual vamos a simplificar de