Máquina de Turing

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
Máquina de Turing por Mind Map: Máquina de Turing

1. ¿Qué es?

1.1. Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas

2. Sus partes son

2.1. Cabezal

2.1.1. capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar.

3. Operaciones que realiza

3.1. 1) Parar la computación

3.2. 2) Moverse un cuadrado a la derecha.

3.3. 3) Moverse un cuadrado a la izquierda.

3.4. 4) Escribir el símbolo S0 en lugar de cualquier otro que este en el cuadrado examinado.

3.5. 5) Escribir el símbolo S1 en lugar de cualquier otro que este en el cuadrado examinado.

4. Proceso de ronocimiento

4.1. 1) registrando la cadena a partir de la segunda celda de su cinta.

4.2. 2) situando su cabeza de lectura en el extremo izquierdo.

4.3. 3) arrancando la máquina desde el estado inicial hasta alcanzar un estado de parada.

5. Máquina de Turing Cuántica

5.1. En 1985, Deutsch presentó el diseño de la primera Máquina Cuántica basada en una máquina de Turing. Con este fin enunció una nueva variante la tesis de Church dando lugar al denominado “Principio de Church-Turing-Deutsch”.

6. La estructura de una máquina de Turing cuántica.

6.1. • Una cinta de memoria infinita en que cada elemento es un Qu Bit.

6.1.1. La cinta de memoria es similar a la de una máquina de Turing tradicional. La única diferencia es que cada elemento de la cinta de la máquina cuántica es un Qu Bit.

6.2. • Un procesador finito.

6.2.1. El procesador contiene el juego de instrucciones que se aplica sobre el elemento de la cinta señalado por el cursor, El procesador ejecuta una instrucción por unidad de tiempo.

6.3. • Un cursor.

6.3.1. El cursor es el elemento que comunica la unidad de memoria y el procesador. Su posición se representa con una variable entera.

7. De que depende el movimiento de una Máquina de Turing

7.1. Cada movimiento de la MT con varias cintas depende tanto de su estado, como del símbolo ledo por cada una de sus cabezadas de cinta.

8. Como decide que acción tomar

8.1. 1. Una máquina de Turing puede escribir a una cinta y leer de ella.

8.2. 2. La cabeza de la cinta puede moverse a la izquierda y a la derecha.

8.3. 3. La cinta es infinita.

8.4. 4. Los estados especiales para aceptar y rechazar tienen efecto inmediato.