Page 94 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

94

A la configuración siguiente:

B B B

Posición de la cabeza lectura/escritura y ahora en el estado o sea colocó una B
5
donde estaba A y corrió la cabeza de lectura a la derecha.

Obsérvese que al describir con una fusión las transiciones de una máquina de Turing, la máquina
es determinista. Esto es así, porque existe una, y solo una transición asociada a cada estado-
símbolo donde el estado no es el de detención.
Durante una operación normal, una máquina de Turing ejecuta transiciones repetidamente hasta
llegar al estado de parada. Es posible también que una MT quede atrapada en un ciclo sin fin. Se
considera una terminación anormal en estas máquinas, si ocurre que la cabeza lectora rebase el
extremo izquierdo de la cinta; en estos casos la máquina abandonará los cálculos decimos que la
ejecución de la máquina sufrió una terminación anormal.

Orígenes de la máquina de Turing: estas máquinas se diseñan para contener todo el poder de los
procesos computacionales. O sea, la idea original de Alan Turing era desarrollar un sistema con
el cual modelar cualquier proceso que pudiera considerarse como un cálculo.

En la actualidad no se ha podido producir un modelo computacional ampliamente aceptado que
supere el poder del modelo de Turing. Este modelo es tan general que incluso modela un concepto
superior al de las computadoras actuales, ya que una MT nunca está restringida por espacio de
almacenamiento. Por esto la mayoría de los científicos y estudiosos de la computación aceptan la
tesis de Turing: el poder computacional de una MT es tan grande como el de cualquier sistema
computacional posible.