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. ρi⊢Mρi-1 per i∈[1,n-1] , ρ0=ρi,ρn=ρ’
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