Macchina di Turing a nastro semi-infinito

Una macchina di Turing con un nastro semi-infinito ha un'estremità sinistra ma non un'estremità destra. L'estremità sinistra è limitata da un indicatore di fine.

È un nastro a due tracce -

  • Upper track - Rappresenta le celle a destra della posizione iniziale della testa.

  • Lower track - Rappresenta le celle a sinistra della posizione iniziale della testa in ordine inverso.

La stringa di input di lunghezza infinita viene inizialmente scritta sul nastro in celle di nastro contigue.

La macchina parte dallo stato iniziale q0e la testa esegue la scansione dall'indicatore dell'estremità sinistra "Fine". Ad ogni passaggio, legge il simbolo sul nastro sotto la sua testa. Scrive un nuovo simbolo su quella cella del nastro e poi sposta la testina nella cella sinistra o destra di una cella. Una funzione di transizione determina le azioni da intraprendere.

Ha due stati speciali chiamati accept state e reject state. Se in qualsiasi momento entra nello stato accettato, l'input viene accettato e se entra nello stato di rifiuto, l'input viene rifiutato dal TM. In alcuni casi, continua a funzionare all'infinito senza essere accettato o rifiutato per alcuni simboli di input.

Note - Le macchine di Turing con nastro semi-infinito sono equivalenti alle macchine di Turing standard.