Lingua accettata e lingua decisa

Una TM accetta una lingua se entra in uno stato finale per qualsiasi stringa di input w. Una lingua è enumerabile ricorsivamente (generata dalla grammatica di tipo 0) se è accettata da una macchina di Turing.

Un TM decide una lingua se la accetta ed entra in uno stato di rifiuto per qualsiasi input non nella lingua. Un linguaggio è ricorsivo se è deciso da una macchina di Turing.

Potrebbero verificarsi casi in cui una TM non si interrompe. Tale TM accetta la lingua, ma non la decide.

Progettare una macchina di Turing

Le linee guida di base per la progettazione di una macchina di Turing sono state spiegate di seguito con l'aiuto di un paio di esempi.

Esempio 1

Progettare una TM per riconoscere tutte le stringhe costituite da un numero dispari di α.

Solution

La macchina di Turing M può essere costruito con le seguenti mosse:

  • Permettere q1 essere lo stato iniziale.

  • Se M è dentro q1; alla scansione di α, entra nello statoq2 e scrive B (vuoto).

  • Se M è dentro q2; alla scansione di α, entra nello statoq1 e scrive B (vuoto).

  • Dalle mosse sopra, possiamo vederlo M entra nello stato q1 se scansiona un numero pari di α ed entra nello stato q2se esegue la scansione di un numero dispari di α. Quindiq2 è l'unico stato accettante.

Quindi,

M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}

dove δ è dato da -

Simbolo di alfabeto del nastro Stato attuale 'q 1 ' Stato attuale 'q 2 '
α BRq 2 BRq 1

Esempio 2

Progettare una macchina di Turing che legga una stringa che rappresenta un numero binario e cancelli tutti gli zeri iniziali nella stringa. Tuttavia, se la stringa comprende solo 0, ne mantiene uno 0.

Solution

Supponiamo che la stringa di input sia terminata da un simbolo vuoto, B, a ciascuna estremità della stringa.

La macchina di Turing, M, può essere costruito con le seguenti mosse:

  • Permettere q0 essere lo stato iniziale.

  • Se M è dentro q0, leggendo 0, si sposta a destra, entra nello stato q1 e cancella 0. Alla lettura di 1, entra nello stato q2 e si muove a destra.

  • Se M è dentro q1, leggendo 0, si sposta a destra e cancella 0, cioè sostituisce 0 con B. Quando raggiunge l'1 più a sinistra, entraq2e si muove a destra. Se raggiunge B, cioè la stringa comprende solo 0, si sposta a sinistra ed entra nello statoq3.

  • Se M è dentro q2, leggendo 0 o 1, si sposta a destra. Raggiunto B, si sposta a sinistra ed entra nello statoq4. Ciò conferma che la stringa comprende solo 0 e 1.

  • Se M è dentro q3, sostituisce B con 0, si sposta a sinistra e raggiunge lo stato finale qf.

  • Se M è dentro q4, leggendo 0 o 1, si sposta a sinistra. Quando raggiunge l'inizio della stringa, cioè quando legge B, raggiunge lo stato finaleqf.

Quindi,

M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}

dove δ è dato da -

Simbolo di alfabeto del nastro Stato attuale 'q 0 ' Stato attuale 'q 1 ' Stato attuale 'q 2 ' Stato attuale 'q 3 ' Stato attuale 'q 4 '
0 BRq 1 BRq 1 ORq 2 - OLq 4
1 1Rq 2 1Rq 2 1Rq 2 - 1Lq 4
B BRq 1 BLq 3 BLq 4 OLq f BRq f