Maquina de turing
Páginas: 16 (3814 palabras)
Publicado: 22 de septiembre de 2009
UNIDAD IV. MAQUINA DE TURING
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 pueden realizar en esta máquina se limitan a:
* avanzar el cabezal lector/escritor para la derecha.
* avanzar el cabezal lector/escritor para la izquierda.
Elcómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) (\nuevo estado, \nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquiercómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de lamáquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.
La idea subyacente en el concepto de que una máquina de Turing es una persona ejecutando unprocedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de lamáquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha”. La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajesrecursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.
4.1. Definición formal de una máquina de turing.
El modelo básico, tiene un control finito, una cinta de entrada que está dividida en celdas y una cabeza de cintaque barre una celda de la cinta a la vez. La cinta tiene una celda que está más a la izquierda, pero se extiende de manera infinita hacia la derecha. Cada celda de la cinta puede contener exactamente un símbolo de un número infinito de símbolos de la cinta. Inicialmente, las n celdas que están más a la izquierda, para alguna n0 finita, sujetan la entrada, que es una cadena de símbolos escogidos deun subconjunto de los símbolos de la cinta, llamados símbolos de entrada. Cada una del número infinito de celdas restantes sujetan el espacio en blanco, que es un tipo especial de símbolo que no es de entrada.
Cabeza de lectura/escritura
a1 a2 ... ai ... an B B ...
Máquina de Turing.
En un movimiento, dependiendo delsímbolo barrido por la cabeza de la cinta y del estado de control finito, la máquina de Turing:
* Cambia de estado,
* Imprime un símbolo en la celda de la cinta que está siendo barrida, sustituyendo lo que se encontraba ahí escrito y
* Mueve su cabeza una celda hacia la izquierda o la derecha.
De manera formal, una máquina de Turing (TM de sus siglas en inglés Turing Machine) se...
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 pueden realizar en esta máquina se limitan a:
* avanzar el cabezal lector/escritor para la derecha.
* avanzar el cabezal lector/escritor para la izquierda.
Elcómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) (\nuevo estado, \nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquiercómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de lamáquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.
La idea subyacente en el concepto de que una máquina de Turing es una persona ejecutando unprocedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de lamáquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha”. La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajesrecursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.
4.1. Definición formal de una máquina de turing.
El modelo básico, tiene un control finito, una cinta de entrada que está dividida en celdas y una cabeza de cintaque barre una celda de la cinta a la vez. La cinta tiene una celda que está más a la izquierda, pero se extiende de manera infinita hacia la derecha. Cada celda de la cinta puede contener exactamente un símbolo de un número infinito de símbolos de la cinta. Inicialmente, las n celdas que están más a la izquierda, para alguna n0 finita, sujetan la entrada, que es una cadena de símbolos escogidos deun subconjunto de los símbolos de la cinta, llamados símbolos de entrada. Cada una del número infinito de celdas restantes sujetan el espacio en blanco, que es un tipo especial de símbolo que no es de entrada.
Cabeza de lectura/escritura
a1 a2 ... ai ... an B B ...
Máquina de Turing.
En un movimiento, dependiendo delsímbolo barrido por la cabeza de la cinta y del estado de control finito, la máquina de Turing:
* Cambia de estado,
* Imprime un símbolo en la celda de la cinta que está siendo barrida, sustituyendo lo que se encontraba ahí escrito y
* Mueve su cabeza una celda hacia la izquierda o la derecha.
De manera formal, una máquina de Turing (TM de sus siglas en inglés Turing Machine) se...
Leer documento completo
Regístrate para leer el documento completo.