Page 30 - 06 Turing

con el símbolo que representa su propio estado en la tabla, en la que
está grabado qué «deberá hacer» la máquina a continuación para
cada una de las combinaciones de símbolos. Es decir, en la tabla se
representa el estado de celda en la cinta y el estado de la máquina,
esto es Ax Q. La situación futura de la máquina queda defirúda en
la tabla a partir de la siguiente información: cuál es el estado futuro
Q de la máquina, y cuál será el nuevo símbolo A que deberá escri-
birse en la cinta en sustitución del símbolo leído, así como en qué
sentido tendrá que desplazarse, si hacia la derecha (D) o hacia la
izquierda (I). Por tanto, en su forma más sencilla, una máquina de
Turing está defirúda por tres elementos: los estados de la máquina
Q, un alfabeto de símbolos A que se escriben y borran en una cinta
de memoria, y una tabla /;}. que recogerá para cada paso concluido
cuál es el paso siguiente que deberá realizar la máquina de Turing.
Con el fin de entender el funcionamiento de la máquina de
Turing, supóngase un ejemplo elemental con tres estados Q = {El,
E2, E3} y una cinta de memoria cuyas celdas pueden contener los
símbolosA={O, 1). Asumamos que hemos asignado su estado ini-
cial 1 igual a El y que la cabeza de lectura/escritura está sobre la
0
segunda celda a la izquierda del fragmento de la cinta que estudia-
remos, en el ejemplo 011110. Sea la tabla de acciones la formada
por las tres tablas menores, una para cada estado de la máquina
El, E2 o E3, que se muestran más abajo; ¿cuál es el comporta-
miento que exhibirá la máquina?

Escribe Próxi mo estado
Símbolo cinta Mover
símbolo cinta máquina
o 1 I E2
1 o D E3

Escri be Próxi mo estado
Símbolo cinta Mover
símbolo cint a máquina
o o I E3
1 1 D El

30 WUÉ ES UN ORDENADOR?