Hola

Maracaibo 6/12/2010
Jose Angel Gomez F.
CI.: 20.378.993
Teoria de la computación.
Máquinas de Turing.

Esquema:
1.-¿Qué es un maquina de turing (MT)?
2.-¿Con que propósito se desarrollaron estas maquinas?
3.-¿Cómo es el funcionamiento de estas maquinas?
4.-¿Un sistema de turing completo como seria?
5.-¿Quién presento la maquina de turing cuantica y como esta estructurada esta?6.-¿Cuáles son los pasos para la combinacion de MT?
7.-Haga un ejemplo de MT

Desarrollo:

1.-¿Qué es un maquina de turing (MT)?
R: es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco(normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

2.- ¿Con que proposito se desarrollaron estas maquinas?
R: el proposito para el cual se desarrollaron los MT es contener todo el poder de los procesos computacionales. La intencion de turing fue desarrollar un sistema en el cual fuera posible modelar cualquier proceso que pudiera considerarcomo un calculo.

3.- ¿Cómo es el funcionamiento de estas maquinas?
R:  Las operaciones que se pueden realizar 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)
Estatabla 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.
La memoria será la cinta la cual se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especialdenominado “blanco”. Las instrucciones que determinan el funcionamiento de la má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”.

4.- ¿Un sistema de turing completo como seria?
R: Un sistema Turingcompleto es aquel que puede simular el comportamiento de una máquina de Turing.  Es evidente que salvando los problemas de memoria, los ordenadores modernos y  los lenguajes de programación de uso general, son sistemas de Turing completos.  También es evidente, que con independencia de su forma concreta, cualquier dispositivo que se comporte como un sistema de Turing completo, puede en principioejecutar cualquier cálculo que realice cualquier computador.

5.-¿Quién presento la maquina de turing cuantica y como esta estructurada esta?
R: En 1985, Deutsch presentó el diseño de la primera Máquina Cuántica basada en una máquina de Turing. La estructura de una máquina de Turing cuántica es muy similar a la de una máquina de Turing clásica. Está compuesta por los tres elementos clásicos:
*Una cinta de memoria infinita en que cada elemento es un QuBit
* Un procesador finito
* Un cursor
El procesador contiene el juego de instrucciones que se aplica sobre el elemento de la cinta señalado por el cursor. El resultado dependerá del QuBit de la cinta y del estado del procesador. El procesador ejecuta una instrucción por unidad de tiempo.
La cinta de memoria es similar a la de unamáquina de Turing tradicional. La única diferencia es que cada elemento de la cinta de la máquina cuántica es un QuBit. El alfabeto de esta nueva máquina está formado por el espacio de valores del QuBit.
El cursor es el elemento que comunica la unidad de memoria y el procesador. Su posición se representa con una variable entera.

6.-¿Cuáles son los pasos para la combinacion de MT?
R:...