Massimo Caliman
Massimo Caliman
1 min read

Modified

Categories

  • Theoretical Computer Science

Tags

  • Turing Machine
  • Linguaggi ricorsivamente enumerabili
  • Linguaggi ricorsivi

Languages

  • Italian

Kleeneliness is next to Gödeliness

Macchine di Turing deterministiche (DTM)

Una Macchina di Turing (d’ora innanzi abbreviata con TM) è un t-upa di 6 elementi 〈Q,Σ,Γ,q0,B,F〉 dove

  • Q insieme di stati (finito)
  • Σ alfabeto di input
  • Γ alfabeto del nastro Σ⊆Γ
  • δ:Q⨯Γ→Q⨯Γ⨯{L,R} funzione parziale detta funzione di transizione
  • q0∈Q stato iniziale
  • B∈(Γ\Σ) simbolo speciale (Blank)
  • F⊆Q insieme stati finali

δ(q,X)=〈q’,Y,D〉 dove q’ è prossimo stato, Y sovrascrive X e D∈{L,R} si può dare una rappresentazione tabellare tramite una matrice di transizione equivalente alla lista delle 5-uple 〈q,X,q’,Y,D〉 per definire il funzionamento si ricorre alla descrizione istantanea (o configurazione) di una TM tramite la tripla ρ=αqβ dove

  • α∈Γ* simboli a sinistra della testina
  • β∈Γ* simboli a destra della testina
  • q stato della testina

se β≠ε il simbolo puntato dalla testina è il primo simbolo di β. altrimenti la testina punta a B (blank)

Singolo passo di esecuzione: Dato M=〈Q,Σ,Γ,q0,B,F〉 una TM def la relazione ρ⊢Mρ’ indotta dalla funzione di transizione δ definita per casi nel seguente modo. Dati α,β∈Γ* e x,y,z∈Γ si ha

  • αqXβ⊢M αYq’β se δ(q,X)=〈q’,Y,R〉
  • αq⊢M αYq’ se δ(q,B)=〈q’,Y,R〉
  • αZqXβ⊢M αq’ZYβ se δ(q,X)=〈q’,Y,L〉
  • qXβ ⊢M q’BYβ se δ(q,X)=〈q’,Y,L〉

La relazione di raggiungibilitàM* tra configurazioni è definita come la chiusura riflessiva e transitiva della relazione ⊢M ossia ρ⊢M*q’ ⇔ vi è una sequenza ρ0,…,ρn≥0 t.c. ρiMρi-1 per i∈[1,n-1] , ρ0in=ρ’

Linguaggio accettato da una TM

Dato M=〈Q,Σ,Γ,q0,B,F〉 una TM, il linguaggio L(M)⊆Σ* accettato da M è definito come L(M)={u∈Σ* | q0u⊢αqβ,q∈F} sulle stringhe non accettate la computazione potrebbe non terminare. Alternativa senza stati finali è dove la stringa è accettata ⇔ la computazione corrispondente termina.

Linguaggi ricorsivamente enumerabili (r.e)

Un linguaggio è r.e. se è accettato da una TM, su qualche stringa potrebbe accadere (se non nel linguaggio) che la TM non termini.

Linguaggi ricorsivi

Un linguaggio è ricorsivo se è accettato da una TM che termina su ogni input