Las máquinas de Turing de movimiento derecho de solo lectura son un tipo particular de máquina de Turing .
Definición
La definición basada en una sola cinta infinita definida como una tupla de 7
dónde
- es un conjunto finito de estados
- es un conjunto finito del alfabeto / símbolos de la cinta
- es el símbolo en blanco (el único símbolo que se permite que ocurra en la cinta infinitamente a menudo en cualquier paso durante el cálculo)
- , un subconjunto de sin incluir b es el conjunto de símbolos de entrada
- es una función llamada función de transición , R es un movimiento a la derecha (un desplazamiento a la derecha).
- es el estado inicial
- es el conjunto de estados finales o de aceptación
En el caso de este tipo de máquinas de Turing, el único movimiento es hacia la derecha. Debe existir al menos un elemento del conjunto F (un estado HALT ) para que la máquina acepte un idioma regular (sin incluir el idioma vacío).
Un ejemplo de máquina de Turing en movimiento derecho de solo lectura
- , "blanco"
- , conjunto vacio
- ver tabla de estados a continuación
- , estado inicial
- el conjunto de un elemento de estados finales:
Tabla de estados para máquina de solo lectura de 3 estados y 2 símbolos
Estado actual A | Estado actual B | Estado actual C | |||||||
símbolo de cinta | Símbolo de escritura | Mueva la cinta | Siguiente estado | Símbolo de escritura | Mueva la cinta | Siguiente estado | Símbolo de escritura | Mueva la cinta | Siguiente estado |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | R | B | 1 | R | A | 1 | R | B |
1 | 1 | R | C | 1 | R | B | 1 | norte | DETENER |
Ver también
Referencias
- Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Segunda edición: Computabilidad, complejidad y lenguajes y lógica: fundamentos de la informática teórica (2ª ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.