Máquina de Turing de Fita Semi-Infinita
Uma Máquina de Turing com uma fita semi-infinita tem uma extremidade esquerda, mas não uma extremidade direita. A extremidade esquerda é limitada com um marcador de final.
É uma fita de duas trilhas -
Upper track - Representa as células à direita da posição inicial da cabeça.
Lower track - Representa as células à esquerda da posição inicial da cabeça na ordem inversa.
A string de entrada de comprimento infinito é inicialmente gravada na fita em células de fita contíguas.
A máquina começa do estado inicial q0e a cabeça faz a varredura do marcador final esquerdo 'End'. Em cada etapa, ele lê o símbolo na fita sob sua cabeça. Ele grava um novo símbolo na célula da fita e então move a cabeça para a esquerda ou para a direita. Uma função de transição determina as ações a serem tomadas.
Tem dois estados especiais chamados accept state e reject state. Se em qualquer ponto do tempo ele entrar no estado aceito, a entrada será aceita e se ele entrar no estado rejeitado, a entrada será rejeitada pelo TM. Em alguns casos, ele continua a funcionar infinitamente sem ser aceito ou rejeitado por alguns símbolos de entrada específicos.
Note - As máquinas de Turing com fita semi-infinita são equivalentes às máquinas de Turing padrão.