Page 28 - 06 Turing

definió una memoria ilimitada, anticipándose y dando la relevancia
a uno de los elementos más importantes en el origen e historia de
los ordenadores: la memoria. Más aún, por razones evidentes los
ordenadores no pueden disponer de una memoria de tamaño ilimi-
tado, lo que explica que estos se «cuelguen» cuando su memoria no
es suficiente al ejecutar un cierto programa o proceso.
Pero ¿qué se graba en la cinta? Supóngase que disponemos
de un alfabeto formado solamente por dos dígitos, el O y el 1, y
un tercer símbolo consistente en «no escribir símbolo alguno»,
al que llamaremos blanco o B. El conjunto de estos tres símbolos
forma un alfabeto al que llamaremos A. Así pues, cada celda de
la cinta infinita tendrá inicialmente grabado un símbolo, ya sea
O, 1 o B (véase la figura).
Consideremos ahora una máquina-a en su configuración más
elemental: ¿de qué partes se compone? Por un lado, dispone de
una cabeza de lectura y escritura, con la cual lee el contenido
de una celda, lo borra y graba en su lugar un nuevo símbolo. En el
modelo general de máquina de Turing se considera que cada vez
que la cabeza de la máquina ha concluido el ciclo de lectura de
una celda, borrado su contenido y grabado un nuevo símbolo, la
cabeza, y con ella toda la máquina, se mueve una posición hacia
la derecha de la cinta (D) o a su izquierda (I). Efectivamente, se
puede considerar, siendo equivalentes, que sea la cinta o la má-
quina, una de las dos, la que dé el salto a D o a I. Y por otro lado,
la máquina dispone de una pequeña memoria, el registro, en el que
se almacena en qué «estado» o configuración se encuentra en un
cierto instante de tiempo de forma similar a, por ejemplo, un se-
máforo que puede estar en estado rojo (R), ámbar (A) o verde (V).
En un instante dado, la máquina se encontrará en un determinado
estado, siendo finito el conjunto de posibles estados. A este con-

28 WUÉ ES UN ORDENADOR?