MAQUINAS DE TURING
by Moisés Bello García
1. MT= (Σ,Q,Γ, δ,q0,B,F) Septupla de Turing
1.1. Σ, Es el alfabeto de entrada
1.2. Q, Es el conjunto de estados, finito y no Vacio
1.3. Γ Es el alfabeto de la cinta
1.4. δ Es la función de Transición, símbolo a escribir y movimiento de cabezal
1.5. q0 Es el estado inicial
1.6. B Símbolo especial que se denomina BLANCO
1.7. F Es el conjunto de estados finales
2. Modelos derivados de la clásica Maquina de Turing
2.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.
2.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).
2.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
2.4. M.T. RESTRINGIDAS Estas restringen el número de estados o el número de símbolos
3. Definición:
3.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.
4. Construcción Modular
4.1. Cinta infinita: Cuenta con celdas con caracteres formando una secuencia Entrada/Salida
4.2. Cabezal: De Lectura y escritura con desplazamientos Izquierda/Derecha
4.3. Transiciones:
4.3.1. A) Cambio de Estado
4.3.2. B) Escritura de Símbolo, de remplazo de valor
4.3.3. C) Desplazamiento L/R (izquierda/Derecha