Presentaremos a continuación una serie de variaciones de la MT básica que, a diferencia del capítulo 8.4, presentan diversas limitaciones pero, como en las variaciones introducidas anteriormente, siguen generando lenguajes recursivamente enumerables.
Máquinas de Turing con Cintas Semi-infinitas
A diferencia de la MT básica, cuya cinta es infinita hacia la izquierda y la derecha, este tipo de MT es infinita hacia la derecha pero tiene un límite a la izquierda (se puede hacer un símil con el conjunto de los números naturales). La posición inicial de la cabeza es en el extremo izquierdo de la cinta, por lo que no hay casillas a la izquierda de la cabeza. Además les pondremos una restricción más a estas MTs: no pueden escribir espacios en blanco.
