Máquina de Turing de cinta semi-infinita
Una máquina de Turing con una cinta semiinfinita tiene un extremo izquierdo pero no un extremo derecho. El extremo izquierdo está limitado con un marcador de final.
Es una cinta de dos pistas.
Upper track - Representa las celdas a la derecha de la posición inicial de la cabeza.
Lower track - Representa las celdas a la izquierda de la posición inicial de la cabeza en orden inverso.
La cadena de entrada de longitud infinita se escribe inicialmente en la cinta en celdas de cinta contiguas.
La máquina comienza desde el estado inicial. q0y la cabeza escanea desde el marcador del extremo izquierdo 'Fin'. En cada paso, lee el símbolo en la cinta debajo de su cabeza. Escribe un nuevo símbolo en esa celda de cinta y luego mueve la cabeza hacia la izquierda o hacia la derecha de una celda de cinta. Una función de transición determina las acciones a realizar.
Tiene dos estados especiales llamados accept state y reject state. Si en algún momento entra en el estado aceptado, la entrada es aceptada y si entra en el estado de rechazo, la entrada es rechazada por el TM. En algunos casos, continúa ejecutándose infinitamente sin ser aceptado o rechazado para ciertos símbolos de entrada.
Note - Las máquinas de Turing con cinta semiinfinita son equivalentes a las máquinas de Turing estándar.