Variantes de una maquina de turing

VARIANTES DE UNA MÁQUINA DE TURING.
Hay otras definiciones de las máquinas de Turing que son equivalentes. Algunos de esos modelos alternativos son mucho más complicados aunque todos tienen lamisma potencia computacional (o de cálculo). Muchas de ellas dotan de mayor flexibilidad al diseño de una máquina de Turing que resuelva un problema en particular.
Máquina de Turing con Directiva dePermanecer
Recuérdese que la máquina de Turing sencilla sitúa la cabeza de lectura/escritura sobre el primer B que haya a la izquierda de la posición actual. Para hacerlo, busca fuera de la celda actualy retrocede. Esto es debido a la definición original que requiere que por cada transición se mueva la cabeza de la cinta.
Máquina de Turing Multipista
Es aquella mediante la cual cada celda de lacinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto quecada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de lacinta contienen (B, a, a), (b, a, a) y (b, b, B). Por tanto, los movimientos que realice está máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual.Máquina de Turing de Cinta infinita en una Dirección
Máquina de Turing que usa una cinta que se extiende infinitamente en una única dirección. Generalmente, se tiene una cinta que se extiendeinfinitamente hacia la derecha. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo.
Desde luego, cualquier máquina de Turing de esta forma puede sersimulada por una de las que responden a la definición original. Para cada computación, simplemente se marca una de las celdas de la cinta infinita por los dos lados, como la celda que se encuentra en...