Page 29 - 06 Turing

junto de estados lo representaremos con la letra Q (véase la fi-
gura). Supongamos que nuestra máquina del ejemplo puede en-
contrarse en uno de los siguientes cuatro estados: El, E2, E3 o E4.
Consideraremos también que hay un estado especial, o estado ini-
cial 1 , que es el valor que tiene el registro cuando la máquina es
0
puesta en funcionamiento.
Así pues, la máquina dispone de dos conjuntos finitos de sím-
bolos, los valores que se graban en las celdas de la cinta A= ¡o, 1,
B} y los estados del registro de la máquina Q = ¡1 , El, E2, E3, E4}.
0
Ahora bien, para que la máquina de Turing resulte útil, y por tanto
«pueda realizar su trabajo», debe seguir un protocolo similar al de
un oficinista. Cada vez que un oficinista realiza un trabajo admi-
nistrativo su ejecución tiene lugar por pasos sucesivos, tal que
concluido un paso debe conocer cuál es el siguiente que debe rea-
lizar. De forma similar, cada vez que la máquina de Turing ha pro-
cesado un símbolo de la cinta, debe actualizar su estado antes de
procesar el símbolo siguiente.
Para que la máquina de Turing pueda cambiar de estado se
define una tabla, la denominada tab/,a, de acciones, que identificare-
mos con el símbolo ti. La tabla, conocida también como función o
reglas de transición, indicará a la máquina qué estado u operación
futura deberá efectuar una vez concluida la operación anterior. Por
tanto, gracias a la lectura de dicha tabla la máquina de Turing actua-
lizará su estado, una vez concluida la tarea actual. Cada vez que la
cabeza de lectura/escritura lee un símbolo de la cinta, lo «combina»

LOS ESTADOS DE UNA MÁQUINA
Un ejemplo simple y cotidiano de los posibles estados para una máquina son
los programas de lavado de una lavadora. Cada vez que la máquina ha con-
cluido una cierta tarea, debe actualizar su estado, siguiendo el programa que
le hayamos marcado, normalmente el programa de lavado estándar, con pre-
lavado, lavado, aclarado y centrifugado. Es decir, en este caso, los estados de
la máquina (la lavadora) son las diferentes partes del programa de lavado que
puede estar ejecutando en un momento determinado.

WUÉ ES UN ORDENADOR? 29