LA MAQUINA DE TURING

LA MAQUINA DE TURING

La máquina de Turing, como modelo matemático, consta de un cabezal lector/escritor y una cinta infinita en lo 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 por la izquierda o la derecha
La computación es determinada a partir de una tabla de estados de la forma:
(estado,valor) → (nuevo estado, nuevo valor, dirección)
Esta tabla toma como parametros el estado actual de la maquina y el caracter leido de la cinta, y da como resultado la dirección de movimiento del cabezal, el nuevo estado de la maquina y el valor a ser escrito en la cinta
la maquina de Turing.
La maquina de Turing puede considerarse un automata capaz de leer lenguajes formales (es un conjunto de palabras (Palabras son cadenas de caracteres) de longitud finita que se forman a partir de un alfabeto (_Conjunto de caracteres) finito.