Introduzione alla macchina di Turing

Una Turing Machine è un dispositivo di accettazione che accetta le lingue (insieme ricorsivamente enumerabile) generate dalle grammatiche di tipo 0. È stato inventato nel 1936 da Alan Turing.

Definizione

Una macchina di Turing (TM) è un modello matematico che consiste in un nastro di lunghezza infinita diviso in celle su cui viene fornito l'input. Consiste in una testina che legge il nastro in ingresso. Un registro di stato memorizza lo stato della macchina di Turing. Dopo aver letto un simbolo di input, viene sostituito con un altro simbolo, il suo stato interno viene modificato e si sposta da una cella a destra oa sinistra. Se la TM raggiunge lo stato finale, la stringa di input viene accettata, altrimenti rifiutata.

Una MT può essere formalmente descritta come una tupla di 7 (Q, X, ∑, δ, q 0 , B, F) dove -

  • Q è un insieme finito di stati

  • X è l'alfabeto del nastro

  • ∑ è l'alfabeto di input

  • δè una funzione di transizione; δ: Q × X → Q × X × {Shift_sinistra, Shift_Destra}.

  • q0 è lo stato iniziale

  • B è il simbolo vuoto

  • F è l'insieme degli stati finali

Confronto con l'automa precedente

La tabella seguente mostra un confronto di come una macchina di Turing differisce da Finite Automaton e Pushdown Automaton.

Macchina Stack struttura dati Deterministico?
Automa finito N / A sì
Automa pushdown Last In First Out (LIFO) No
Macchina di Turing Nastro infinito sì

Esempio di macchina di Turing

Macchina di Turing M = (Q, X, ∑, δ, q 0 , B, F) con

  • Q = {q 0 , q 1 , q 2 , q f }
  • X = {a, b}
  • ∑ = {1}
  • q 0 = {q 0 }
  • B = simbolo vuoto
  • F = {q f }

δ è dato da -

Simbolo di alfabeto del nastro Stato attuale 'q 0 ' Stato attuale 'q 1 ' Stato attuale 'q 2 '
un 1Rq 1 1Lq 0 1Lq f
b 1Lq 2 1Rq 1 1Rq f

Qui la transizione 1Rq 1 implica che il simbolo di scrittura è 1, il nastro si sposta a destra e lo stato successivo è q 1 . Allo stesso modo, la transizione 1Lq 2 implica che il simbolo di scrittura è 1, il nastro si sposta a sinistra e lo stato successivo è q 2 .

Complessità temporale e spaziale di una macchina di Turing

Per una macchina di Turing, la complessità temporale si riferisce alla misura del numero di volte che il nastro si muove quando la macchina viene inizializzata per alcuni simboli di input e la complessità dello spazio è il numero di celle del nastro scritte.

Complessità temporale tutte le funzioni ragionevoli -

T(n) = O(n log n)

La complessità spaziale della TM -

S(n) = O(n)