Maquina de turing
Páginas: 3 (743 palabras)
Publicado: 5 de diciembre de 2010
Maquina de Turing
Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelomatemático abstracto que formaliza el concepto de algoritmo.
Máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entradallamada cinta, generando una salida en esta misma.
¿como funciona?
Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas.
el cabezal lee el contenido, borra elcontenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
* avanzar el cabezal lector/escritor hacia la derecha.
Visualizaciónde una Maquina de Turing, en la que se ve el cabezal y la cinta que se lee
* avanzar el cabezal lector/escritor hacia la izquierda.
Ejemplo:
Sea la máquina de Turing capaz de leer oescribir 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:
Ejemplo:
Hemos puesto los posibles estados en columna, y los posible símbolos en fila, y hemos expresadoel nuevo estado, símbolo y sentido todo junto. El sentido lo expresamos con la dirección en la que apunta el símbolo < o >.
Vamos a poner nuestra máquina sobre esta cinta
cabezalv
... 0 0 0 0 0 1 0 0 0 0 ...
Indicaremos el estado actual de la máquina encima del cabezal. Veamos los sucesivos pasos de esta máquina si partimos del estado A:
:
Las máquinas...
Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelomatemático abstracto que formaliza el concepto de algoritmo.
Máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entradallamada cinta, generando una salida en esta misma.
¿como funciona?
Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas.
el cabezal lee el contenido, borra elcontenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
* avanzar el cabezal lector/escritor hacia la derecha.
Visualizaciónde una Maquina de Turing, en la que se ve el cabezal y la cinta que se lee
* avanzar el cabezal lector/escritor hacia la izquierda.
Ejemplo:
Sea la máquina de Turing capaz de leer oescribir 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:
Ejemplo:
Hemos puesto los posibles estados en columna, y los posible símbolos en fila, y hemos expresadoel nuevo estado, símbolo y sentido todo junto. El sentido lo expresamos con la dirección en la que apunta el símbolo < o >.
Vamos a poner nuestra máquina sobre esta cinta
cabezalv
... 0 0 0 0 0 1 0 0 0 0 ...
Indicaremos el estado actual de la máquina encima del cabezal. Veamos los sucesivos pasos de esta máquina si partimos del estado A:
:
Las máquinas...
Leer documento completo
Regístrate para leer el documento completo.