Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
MAQUINAS DE TURING por Mind Map: MAQUINAS DE TURING

1. Definición:

1.1. consiste en una cinta que se extiende de manera infinita,en donde se escribe o lee la información por medio de una cabeza de lectura/Escritura.

2. Construcción Modular

2.1. Cinta infinita: Cuenta con celdas con caracteres formando una secuencia Entrada/Salida

2.2. Cabezal: De Lectura y escritura con desplazamientos Izquierda/Derecha

2.3. Transiciones:

2.3.1. A) Cambio de Estado

2.3.2. B) Escritura de Símbolo, de remplazo de valor

2.3.3. C) Desplazamiento L/R (izquierda/Derecha

2.4. Control Finito: Controla el funcionamiento el estado actual y las posibles transiciones

3. MT= (Σ,Q,Γ, δ,q0,B,F) Septupla de Turing

3.1. Σ, Es el alfabeto de entrada

3.2. Q, Es el conjunto de estados, finito y no Vacio

3.3. Γ Es el alfabeto de la cinta

3.4. δ Es la función de Transición, símbolo a escribir y movimiento de cabezal

3.5. q0 Es el estado inicial

3.6. B Símbolo especial que se denomina BLANCO

3.7. F Es el conjunto de estados finales

4. Modelos derivados de la clásica Maquina de Turing

4.1. MT. MULTICINTA: Este modelo tiene K cintas y K cabezales de L/E, solo hay una entrada de información y agrega un tercer movimiento (Z) que es nada.

4.2. M.T. MÚLTIPLES CABEZALES: Tienen K cabezales de L/E pero con una sola cinta. los cabezales operan de manera independiente se adminten los movimientos (L,R,N).

4.3. M.T. NO DETERMINISTA: Tiene una cinta limitada a la Izquierd, que se caracteriza por tener asociada más de una transición desde algún estado con el mismo simbolo

4.4. M.T. RESTRINGIDAS Estas restringen el número de estados o el número de símbolos

5. Bibliografía

5.1. Garcia-Capitulo 6 Modelos de la Maquinas de Turing ,Garcia,F. (2005) Pa´g. 85-102

5.2. Jurado Malaga,E. (2008) . Teoría de los autómatas y lenguajes Formales. Universidad de Extremadura, España Pág. 105- 119