Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página8/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   ...   4   5   6   7   8   9   10   11   ...   31

donde el símbolo representa un par de la cinta de dos pistas: en la pista de arriba se encuentra el símbolo si y en la pista de abajo el símbolo sj . El símbolo # será un marcador que indicará la casilla más a la izquierda de la cinta. De esta forma la configuración inicial de la cinta será

# B x


q1



Los estados de serán q1,q2,q3,q4,q5 , y

{ q´i,q´´i / i = 1,2,...,K }



así como ciertos estados adicionales.

Las cuádruplas de se dividirán en tres secciones: COMIENZO, MITAD y FINAL. COMIENZO sirve para copiar la entrada en la pista de arriba, poniendo blancos en la correspondiente pista de abajo. COMIENZO consta de las cuadruplas

q1 B R q2

1   ...   4   5   6   7   8   9   10   11   ...   31


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal