Unida 6 Definición formal MT

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 )