"La Máquina de Turing" Fatima Zepeda

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

1. Fue creada en 1936, por Alan Turing

2. Foto

3. ¿Qué es?

3.1. Es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas.

3.2. Puede simular la lógica de cualquier algoritmo de computador

3.3. Puede almacenar y procesar información virtualmente infinita.

3.4. Foto

4. ¿Como funciona?

4.1. La máquina es como una cinta infinita dividida en casillas.

4.2. Cada casilla tiene un simbolo.

4.3. En la cinta hay un dispositivo que lee los símbolos de las casillas.

4.4. Acciones de del dispositivo:

4.4.1. 1) Pasar a un nuevo estado

4.4.2. 2) Imprimir un simbolo

4.4.3. 3) desplazarse hacia la izquierda o hacia la derecha

4.4.4. 4) la máquina se para.

5. El funcionamiento se puede representar mediante una tabla:

5.1. Las filas están encabezadas por los estados.

5.2. Las columnas por los símbolos de la cinta.

5.3. en cada posición de la tabla hay 3 elementos:

5.4. 1) El estado siguiente

5.5. 2) El símbolo que se escribe en la cinta

5.6. 3) Movimiento de la cabeza

6. Estados

6.1. Estado p

6.2. Mientras se encuentra el símbolo 0 , este lo ignora y avanza hacia la izquierda.

6.3. En el símbolo 1, lo sustituye por 0

6.4. Pasa al estado q y avanza hacia la derecha

6.5. si encuentra una casilla en blanco: pasa al estado r y avanza hacia la derecha

6.6. Estado q

6.6.1. Ignora los símbolos 0 y 1 y avanza hacia la derecha.

6.6.2. Si encuentra un blanco, escribe 0, pasa al estado p y avanza hacia la izquierda.

6.6.3. añade un 0 al final de la cadena de 0 y unos Sobre a primera casilla en blanco situada a la derecha.

6.7. Estado r

6.7.1. Sustituye el 0 por 1 y avanza hacia la derecha.

6.7.2. Si encuentra una casilla en blanco, pasa al estado final

6.7.3. Se detiene la máquina.

7. La máquina es “Computacionalmente completa”

7.1. Esta máquina puede resolver cualquier problema recursivamente enumerable

8. Gracias a la existencia de esta máquina, hay ordenadores electrónicos que son capaces de hacer cualquier calculo computable

9. Modificaciones a la máquina de Turing

9.1. Las maquinas de Turing No deterministas: En cada posición de la tabla pueden incluir distintas posibilidades.

9.2. Maquinas con varias cintas

9.3. “El automata lineal acotado”: cinta infinita

9.4. “Automata a pila”: puede escribir y leer en una segunda cita

9.5. “El automata finito determinista”

10. Partes:

10.1. Una cinta:

10.2. Se divide en celdas, una al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito. La cinta es extensible hacia la izquierda y hacia la derecha,

10.3. Cabezal:

10.4. que puede leer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una celda a la vez.

10.5. Un registro de estado:

10.6. almacena el estado de la máquina de Turing.

10.7. Una tabla de acción