6.1 Definición formal MT
La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.
(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.
Esta constituida por los siguiente elementos:
MT = ( E, A, B, e0, F, f)
E = Conjunto de estados, no vacío.
A = Conjunto de símbolos de entrada.
B = Conjunto de símbolos auxiliares.
e0 = Estado inicial.
F = Conjunto de estados finales.
f = Función de control, definida:
donde: f: ( E - F ) x ( A È B ) Þ E x ( A È B) x ( I, O, D )
No hay comentarios:
Publicar un comentario