PARTE II

MACCHINE DI TURINGE CALCOLABILITA’ SECONDO TURING

Macchine di Turing ad un nastro e multinastro

Macchine di Turing non deterministiche

Macchine di Turing e linguaggi di tipo 0 e di tipo 1

Calcolabilita’ secondo Turing

Indecidibilita’ del problema della terminazione

2.1 MACCHINE DI TURING

La macchina di Turing è un automa con testina discrittura/lettura su nastro bidirezionale "potenzialmente"illimitato. Ad ogni istante la macchina si trova in uno statoappartenente ad un insieme finito e legge un carattere sul nastro.La funzione di transizione, in modo deterministico, fa scrivere uncarattere, fa spostare la testina in una direzione o nell'altra, facambiare lo stato.

Le macchine di Turing:

• forniscono una definizione formale del concetto di algoritmo• consentono il riconoscimento, almeno "parziale"(semidecidibilità, accettazione), di tutti i linguaggi di tipo 0• sono in grado di simulare ogni linguaggio diprogrammazione ed ogni altro modello di calcolo("tesi di Church-Turing").

Def. Macchina di Turing:

M=<Σ,b,K,q0,F,δ>

Σ alfabeto di simbolib carattere speciale, spazio bianco (blank)K insieme finito di statiq0 stato inizialeF insieme di stati finaliδ funzione di transizione (parziale)

δ: K × (Σ∪{b}) → K × (Σ∪{b}) × {d,s,i}

d,s,i indicano spostamento a destra, a sinistra e immobilita' dellatestina

Σb = Σ∪{b}

Possiamo definire molte varianti di macchine di Turing (tuttecomputazionalmente equivalenti)

• macchine a uno o piu' nastri

• macchine per calcolare funzioni

• macchine per riconoscere linguaggi

• macchine deterministiche e non deterministiche

• macchine con alfabeto limitato

• macchine con nastro seminfinito

Configurazioni e computazioni

NOTA BENE. Il nastro, pur essendo infinito, ha un numerofinito di caratteri ≠ b

Def. Configurazione di una macchina:porzione finita del nastro diversa da b + posizione della testina +stato corrente

Rappresentazione di una configurazione: stringa appartenente allinguaggio

(Σb)*.K.(Σb)+

Esempio

abbbbqiabbbbb

La conoscenza di una configurazione e della funzione ditransizione consente di determinare la configurazionesuccessiva.

Normalmente si fa l'ipotesi che all'inizio della computazione ilnastro contenga l'input, il resto del nastro contenga b e la testinasia sul primo carattere dell'input

Configurazione iniziale:stringa appartenente al linguaggio

{q0}.(Σb)+

Configurazione finale:stringa appartenente al linguaggio

(Σb)*.F.(Σb)+

Def. Relazione di transizione per macchina di Turing (|—):relazione binaria sulle configurazioni

ci |— ci+1

Def. Computazione per macchina di Turing: sequenzaeventualmente infinita di configurazioni <c1,c2,...,ci,...> tali che:

c1 |— c2 |— .... |— ci |— ci+1|—....

La notazione

c1 |—* c2

indica l'esistenza di una computazione che da c1 porta a c2tramite un numero finito (eventualmente 0) di transizioni.

Convenzione. In ogni computazione può esistere al più unaconfigurazione finale; se la macchina raggiunge unaconfigurazione finale il calcolo termina.

NOTA BENE. Una computazione infinita non ha configurazionifinali.

Def. Una computazione finitac1 |— c2 |— .... |— cn

e' massimale se non esiste una configurazione c tale che cn |— c.

Def. Una computazione massimale<c0, c1,...., cn> è accettante se c0 è iniziale e cn è finale.

Def. Una computazione massimale<c0, c1,...., cn> è rifiutante se c0 è iniziale e cn non è finale.

Convenzioni.

Computazione accettante: responso affermativoComputazione rifiutante: responso negativoComputazione non terminante: nessun responso

• Una macchina di Turing M riconosce un linguaggio L se perogni x∈Σ* M è in grado di stabilire se x∈L o no

• Una macchina di Turing M accetta un linguaggio L se pertutte e sole le x∈L M è in grado di stabilire tale appartenenza,ma se x∉L M non garantisce un comportamento prestabilito.

Def. M=<Σ,b,K,q0,F,δ> riconosce (decide) un linguaggio L seper ogni x∈Σ* esiste q∈K tale che• q0x |—* αqβ con α∈(Σb)* e β∈(Σb)+ e la computazionecorrispondente è massimale,• se e solo se x∈L allora q∈F

Def. Un linguaggio riconosciuto da una macchina di Turing èdetto decidibile.

NOTA BENE. Non è detto che una macchina di Turing possasempre riconoscere un linguaggio.

Def. M=<Σ,b,K,q0,F,δ> accetta un linguaggio L se per tutte esole le x∈L esiste q∈F tale che• q0x |—* αqβ con α∈(Σb)* e β∈(Σb)+.

Un linguaggio L è accettato da una macchinadi Turing M se:

L = L(M) = {x| x∈Σ* ∧ q0x |—*αqβ ∧ q∈F}

con α∈(Σb)*, β∈(Σb)+.

Def. Un linguaggio accettato da una macchina di Turing è dettosemidecidibile.

NOTA BENE. Se un linguaggio è decidibile è anchesemidecidibile.

Def. Macchina di Turing trasduttrice: ogni configurazione finaleè del tipo xbqy, dove x è il contenuto del nastro all'inizio dellacomputazione

Def. Una macchina trasduttrice calcola la funzione f se per tuttee sole le x nel dominio di definizione di f esiste q∈F tale che:

q0x|—*xbqf(x)

NOTA BENE. Se D è il dominio e D' il codominio dellafunzione f, x ed f(x) sono rispettivamente rappresentazioni deglielementi di D e D' nell'alfabeto della macchina.

Def. Una funzione (parziale) f per la quale esiste una macchinadi Turing che la calcola è detta calcolabile secondo Turing(T-calcolabile).

Esercizi

Realizzare le macchine di Turing che accettano i linguaggi{ wcwR | w ∈ (a+b)+}{ wwR | w ∈ (a+b)+}{ wcw | w ∈ (a+b)+}

Realizzare le macchine di Turing che calcolano le funzionif(x) = xcx, x ∈ (a+b)+f(x) = x+1, dove x ed x+1 sono interi rappresentati inbinariof(x, y) = x+y, dove x, y ed x+y sono interirappresentati in binario

2.2 MT MULTINASTRO (MTM)

Def. Macchina di Turing a k nastri:

Mk=<Σ,b,Z0,K,q0,F,δ(k)>

Σ alfabetob carattere speciale, spazio biancoZ0 carattere speciale, inizialeK insieme finito di statiq0 stato inizialeF insieme di stati finali

δ(k) funzione di transizioneδ : K × (Σb)k → K × (Σb)k × {d,s,i}k

Configurazioni, transizioni e computazioni

Configurazione:

q#α1↓β1#α2↓β2#....#αk↓βk

q e' lo stato; la stringa αi↓βi indica il contenuto e la posizionedella testina sul nastro i. αi e' eventualmente vuota e il primocarattere di βi e' il carattere attualmente osservato

configurazione finale: q appartiene a F

configurazione iniziale: q0#↓β1#↓Z0#....#↓Z0

l'input sta sul primo nastro e gli altri contengono il carattere Z0

transizioni e computazioni: analoghi alle MT

Esempi di macchine a più nastri:

- un trasduttore con un nastro di input (sola lettura), un nastro dioutput (sola scrittura) e uno o più nastri di lavoro (lettura escrittura)

- un riconoscitore con un nastro di input (sola lettura e one way)e uno o più nastri di lavoro (lettura e scrittura, bidirezionali)

Esercizio.Realizzare una macchina di Turing a due nastri che riconosce illinguaggio { xcxR | x ∈ (a+b)+}

Nota bene. L’automa a pila può essere visto come una macchinadi Turing a due nastri, il primo di sola lettura e one way, ilsecondo utilizzato in modo LIFO, come una pila.

Soluzione dell’esercizio.MTM per riconoscere xcxR con x∈{a,b}+

usiamo 2 nastri: uno di input monodirezionale a sola lettura euno di lavoro che usiamo come pila

durante la scansione di x, fino a c, x viene copiata sul nastrodi lavoro

durante la scansione di xR si confrontano i caratteri conquelli sul nastro di lavoro

configurazione iniziale della MTM:

q0#↓z#↓Z0

3 stati:q0 per scandire xq1 per scandire xRq2 stato finale

copiatura iniziale:δ(q0,a,Z0)=<q0,a,A,d,d>δ(q0,b,Z0)=<q0,b,B,d,d>

copiatura a regime:δ(q0,a,b)=<q0,a,A,d,d>δ(q0,b,b)=<q0,b,B,d,d>

passaggio dalla copiatura alla verifica:δ(q0,c,b)=<q1,c,b,d,s>

verifica positiva:δ(q1,a,A)=<q1,a,A,d,s>δ(q0,b,B)=<q1,b,B,d,s>

accettazione:δ(q1,b,b)=<q2,b,b,i,i>

computazione con input bacab:q0 #↓bacab #↓Z0 |—q0 #b↓acab #B↓b |—q0 #ba↓cab #BA↓b |—q1 #bac↓ab #B↓A |—q1 #baca↓b #↓BA |—q1#bacab↓b #↓bBA |—q2 #bacab↓b #↓bBA

computazione con input acb:q0 #↓acb #↓Z0 |—q0 #a↓cb #a↓b |—q1 #ac↓b #↓a

Equivalenza tra MTM e MT

Strumento di lavoro: MT a nastro suddiviso in tracce

se il nastro ha h tracce la testina può leggere/scrivere hcaratteri contemporaneamente

la corrispondenza tra MT a nastro suddiviso in tracce ed unanormale MT è immediata

osservazione:

se sulle tracce sono usati gli alfabeti Σ1,Σ2,....,Σh, una MTcorrispondente ha un alfabeto Σ con |Σ|≥|Σ1|x|Σ2|x....x|Σh|

Teorema. Data una MTMM=<Σ,b,K,q0,F,δ(k)> a k nastri esiste una MT che simula t passidi Mk in O(t2) passi usando un alfabeto di cardinalità O((2|Σ|)k)

Dim.

Costruiamo una MT M'=<Σ',b,K',q0',F',δ'> con nastro suddivisoin 2k tracce che simula M

poi costruiamo una MT M" equivalente a M'

le k tracce di posto pari di M' rappresentano i k nastri di M

sulle k tracce di posto dispari di M' con il carattere "↓"indichiamo la posizione delle testine sui k nastri di M

il nastro di M' all' inizio della computazione si presenta con tuttele tracce dispari "vuote" tranne la prima

per simulare la funzione di transizione di M che e' del tipo:

δ(k)(qi,σi1,..,σik) = <qj,σj1,..,σjk,zj1,..,zjk>

la δ' deve:rintracciare le posizioni dei marcatori,scrivere e spostare i marcatori,cambiare stato

quindi per ogni passo di M, M' deve eseguire un numero di passiproporzionale alla distanza (numero di caselle) tra i duemarcatori piu' lontani

dopo t passi due marcatori possono essersi allontanati di al piu'O(t) caselle

se M esegue t passi, M' ne esegue O(t2)

M" esegue gli stessi passi di M'

per cio' che riguarda la cardinalita' dell'alfabeto di M" abbiamoda codificare con un solo alfabeto stringhe di 2k simboli cosi'composte:

k simboli appartengono a {b,↓}1 simbolo appartiene a Σ∪{b}k-1 simboli appartengono a Σ∪{b,Z0}

|Σ"| = 2k(|Σ|+1)(|Σ|+2)k-1 = O((2|Σ|)k)

Esempio. MTM per riconoscere xxR con x∈{a,b}

usiamo 3 nastri: uno di input monodirezionale e due di lavoro

copiamo la stringa sui due nastri di lavoro poi scandiamo i duenastri in senso contrario ed effettuiamo i confronti

configurazione iniziale della MTM:

q0#↓w#↓Z0#↓Z0

copiatura iniziale:δ(q0,a,Z0,Z0)=<q0,a,A,A,d,d,d>δ(q0,b,Z0,Z0)=<q0,b,B,B,d,d,d>

copiatura a regime:δ(q0,a,b,b)=<q0,a,A,A,d,d,d>δ(q0,b,b,b)=<q0,b,B,B,d,d,d>

termine della copiatura:δ(q0,b,b,b)=<q0,b,b,b,i,s,s>

riposizionamento della testina:δ(q0,b,A,A)=<q0,b,A,A,i,s,i>δ(q0,b,B,A)=<q0,b,B,A,i,s,i>δ(q0,b,A,B)=<q0,b,A,B,i,s,i>δ(q0,b,B,B)=<q0,b,B,B,i,s,i>

fine del riposizionamento della testina:δ(q0,b,b,A)=<q1,b,b,A,i,d,i>δ(q0,b,b,B)=<q1,b,b,B,i,d,i>

verifica:δ(q1,b,A,A) = <q1,b,A,A,i,d,s>δ(q1,b,B,B) = <q1,b,B,B,i,d,s>δ(q1,b,b,b) = <q2,b,b,b,i,i,i>

2.3 MT NONDETERMINISTICHE (MTND)

Def. Macchina di Turing non deterministica:

M=<Σ,b,K,q0,F,δN>

Σ alfabeto di simbolib carattere speciale, spazio biancoK insieme finito di statiq0 stato inizialeF insieme di stati finali

δN funzione parziale di transizioneδN: K×Σb → P(K × Σb × {d,s,i})

La macchina di Turing non deterministica può eseguire piùtransizioni.

Def. Grado di non determinismo di una macchina Mν(M) = max|δN(qi,σj)|

Una computazione eseguita da una macchina non deterministicapuò essere rappresentata con un albero di computazionideterministiche.

nodi: configurazioniarchi: transizioni

NOTA BENE. Il grado di non determinismo coincide con ilmassimo numero di figli di un nodo dell'albero di computazione

Possiamo utilizzare macchine di Turing non deterministiche peraccettare linguaggi.

Def. Una MTND accetta una stringa se nell'albero dicomputazione è possibile trovare almeno un ramo checorrisponde ad una computazione deterministica accettante(cioè, almeno una foglia dell'albero corrisponde ad unaconfigurazione finale).

Nota bene. Anche in questo caso usiamo il termine accettazioneanziché riconoscimento perché c’è asimmetria tra l’accettazionee il rifiuto di una stringa: in un caso basta che esista un camminoaccettante, nell’altro caso bisogna che i cammini siano tuttirifiutanti.

Equivalenza tra MT e MTND

Le MTND sono più "efficienti" ma hanno lo stesso poterecomputazionale delle MT.

Teorema. Data una macchina non deterministica M con gradodi nondeterminismo d esiste una MT M' equivalente che simulak passi di M in O(kdk) passi

Dim.

L'albero di computazione di M viene visitato in ampiezza da M'(perché non in profondità?)

M' ha 3 nastri

nastro 1: contiene l'input

nastro 2: viene usato per generare, in ordine lessicografico, tuttele sequenze finite composte da cifre comprese tra 1 e dnastro 3: nastro di lavoro

per ogni sequenza generata sul nastro 2, M' copia l'input sulnastro 3

le transizioni di ogni insieme δN(q,σ) sono numerate da 1 a d

ogni sequenza di lunghezza s sul nastro 2 è incorrispondenza con una computazione di M di s passi

gli s numeri di ogni sequenza (compresi tra 1 e d) sono usatiper scegliere ad ogni passo una transizione tra le d possibili

es. se s=4 e d=2 e la sequenza è 2122 M' sceglie per la primamossa la seconda transizione disponibile, per la secondamossa la prima, ecc....

Se su qualche foglia dell'albero di computazione di M c'èuno stato finale, allora M' lo raggiunge in tempo finitoaltrimenti M' non raggiunge mai uno stato finale.

Se M termina in k passi M' ha bisogno di

kO( Σ jdj) = O(kdk) passi

j=0

NOTA BENE. Una macchina non deterministica può "risolvere"un problema (ad esempio, accettare un linguaggio) in tempopolinomiale rispetto alla lunghezza della stringa mentre lasimulazione effettuata da una macchina deterministica richiedetempo esponenziale.

Problema aperto. Esiste una simulazione più efficiente?E' possibile simulare una macchina di Turing non deterministicacon una deterministica in tempo polinomiale?

Per dimostare che k

O (Σ jdj) = O (kdk) passi j=0

si può procedere come segue.

Osserviamo innanzitutto che

kΣ d

j = (dk+1-1)/(d-1)

j=0

Derivando si ottiene:

kΣ jd

j-1 = (kdk+1-(k+1)dk+1)/(d-1) 2

j=1

e quindi

kΣ jd

j = O (kdk)

j=1

2.4 LINGUAGGI DI TIPO 0 E MT

Teorema. Un linguaggio L è semidecidibile se e solo se è unlinguaggio di Tipo 0

Dim.

i) Tipo 0 -> MT

Innanzitutto mostriamo come, dato un linguaggio L, generato dauna grammatica G di tipo 0, possiamo definire una MT che loaccetta. In realtà, per semplificare la dimostrazione utilizzeremouna MTND M con 2 nastri ma sappiamo che esiste comunqueuna MT M' ad un solo nastro che può simulare M.

La macchina M opera nel seguente modo: partendo dall'assiomaS la macchina applica via via, in modo non deterministico, tuttele produzioni applicabili. Dopo aver applicato una produzione,oltre a proseguire nell'applicazione delle produzioni, in modonon deterministico essa effettua una verifica per controllare se laforma di frase ottenuta è costituita da soli terminali e se essacoincide con la stringa da generare x. In tal caso M termina inuno stato finale.

I 2 nastri vengono utilizzati nel seguente modo:

N1 contiene la stringa x che deve essere accettata,

N2 contiene le forme di frase che via via vengono derivate e chedevono essere confrontate con la stringa x.

ii) MT -> Tipo 0

Supponiamo ora di avere una macchina di Turing M che accettaun linguaggio L. Mostriamo come si può costruire unagrammatica G di Tipo 0.

Se la macchina accetta L vuol dire che, per tutte e sole le x∈L,essa realizza la computazione q0x |—* aqFb con un opportunoqF∈F (per semplicità supporremo che esista un unico stato finaleqF∈F). In corrispondenza della macchina M la grammatica G ècosì definita.Il suo alfabeto non terminale è costituito da alcuni simboliausiliari, da simboli corrispondenti agli stati di M e da simboliche rappresentano il contenuto di due piste:quella superiore contiene caratteri σi di Σ∪{b}, quella inferiorecaratteri σj di Σ∪{b}. Tali simboli sono dunque del tipo:

σi σj

La grammatica opera nel seguente modo:

1. introduce lo stato iniziale q02. genera una qualsivoglia stringa x di Σ∗ sulle due piste3. genera un numero arbitrario di b a destra e a sinistra di x

sulle due piste4. simula M sulla pista inferiore5. se la pista inferiore è una configurazione finale e, solo in tal

caso, trasforma la forma di frase ottenuta finora nella stringax che è tuttora presente sulla pista superiore.

Vediamo la forma delle varie produzioni.

S → A1 q0 A2σi

A2 → σi A2 | Α3b b

A1 → Α1 b A3 → bA3

A questo punto abbiamo forme di frase del tipo:

b b ai1 ainbb bΑ1 b..... b q0 ai1... ainbb…. bA3

Per effettuare la simulazione della macchina avremo, per ogniregola di transizione, una serie di produzioni che realizzano, sullapista inferiore, le stesse trasformazioni. Ad esempio, incorrispondenza della regola di transizione

d(qk,σi) = (qh,σl,d)

avremo le regole di produzione

σj σjqk σi → σl qh

per ogni σj in Σ∪{b} che si trovi sulla pista superiore.

Infine per il passo 5 abbiamo:

qF → A4 A5 per ogni stato finale qF

σjσi Α4 → A4 σj

per ogni σj in Σ e σi in Σ∪{b}.

b σi Α4 →A4 per ogni σi in Σ∪{b}.

e analogamente per A5. Infine

A1 A4 → ε

A5 A3 → ε

2.5 LINGUAGGI DI TIPO 1 E AUTOMI LIMITATI

Teorema. I linguaggi di Tipo 1 sono decidibili.

Dim.

Dato che le forme di frase non possono diminuire di lunghezzabasta generare tutte le forme di frase in ordine di lunghezzacrescente e confrontare quelle di soli terminali con la stringa dariconoscere.

Teorema. Tutti e soli i linguaggi di Tipo 1 sono riconoscibili conmacchine di Turing nondeterministiche che fanno uso di nastrolimitato linearmente nella lunghezza delle stringhe in ingresso(Linear Bounded Automata, LBA)

Dim. Lasciata come esercizio.

2.6 CALCOLABILITA' SECONDO TURING(T-CALCOLABILITA')

Come abbiamo già visto le macchine di Turing ci consentono didefinire

• linguaggi decidibili o semidecidibili• funzioni (totali o parziali) calcolabili

Cosa ha condotto Turing a definire le sue ‘macchine’?

1900: Al Secondo Congresso Internazionale di MatematicaHilbert formula 23 problemi matematici per il XX secolo(Problemi futuri della Matematica).

Il secondo problema riguarda la consistenza (cioè la noncontraddittorietà) degli assiomi della teoria logica dell’aritmeticadei numeri naturali basata sugli assiomi introdotti da Peano nel1889.

1928: Hilbert riformula i problemi aperti riguardantil’Aritmetica:

- L’Aritmetica è completa? Cioè è possibile dimostrare ogniasserzione vera?

- L’Aritmetica è consistente? Cioè siamo certi che non siapossibile dimostrare un’asserzione e anche la suanegazione? Se ciò fosse vero ogni asserzione sarebbedimostrabile, quindi per dimostrare la consistenza èsufficiente dimostrare che esistono asserzionidell’aritmetica non dimostrabili.

- L’Aritmetica è decidibile? Cioè esiste un algoritmo checonsente di decidere se un’asserzione è un teorema?

Il ruolo dei paradossi.

1. Epimenide di Creta (VI sec. a. C.):Tutti i cretesi sono bugiardi.(questa affermazione non può essere vera ma può esserefalsa; non è un vero paradosso)

2. Eubulide di Mileto (IV sec. a. C.):Questa frase è falsa oppure Io sto mentendo(queste affermazioni non possono essere né vere né false)

3. Buridano (XIV sec.):Socrate dice: “Platone dice il falso”Platone dice: “Socrate dice il vero”(le due affermazioni congiunte sono un paradosso)

Nel XX sec. vengono formulati paradossi relativi alla teoriadegli insiemi:

4. Russell: L’insieme di tutti gli insiemi che nonappartengono a se stessi, appartiene o no a se stesso?

5. Russell: In un villaggio il barbiere rade tutti e soli coloroche non si radono da soli; chi rade il barbiere?

6. Gonseth: In una biblioteca può esistere un catalogo di tuttii cataloghi bibliografici che non contengono se stessi?

1931: Gödel dimostra che l’aritmetica non può essere al tempostesso completa e consistente. Idea:

- Rappresentare la logica (assiomi, regole d’inferenza,dimostrazioni e teoremi) all’interno dell’aritmeticamediante un procedimento di aritmetizzazione (oGödelizzazione, cioè codificazione dell’apparato dellalogica mediante numeri interi).

- Ricorrere allo stesso tipo di assurdità che si presentanonei classici paradossi sfruttando l’autoreferenzialità ecioè creando un’asserzione w che afferma: w non èdimostrabile. Se w fosse falsa sarebbe dimostrabile equindi necessariamente vera; quindi (se il calcolo non ècontraddittorio) w non può essere falsa e deve esserevera. Ma se è vera non è dimostrabile. Quindi w è unesempio di asserzione vera ma non dimostrabile.Conseguenze: l’aritmetica non è completa o non èconsistente (ma la consistenza non è dimostrabileall’interno della teoria stessa).

1935: Turing dimostra l’indecidibilità dell’aritmetica(On computable numbers, with an application to theEntschaidungsproblem, J. of Symbolic Logic, 1936).

- Definisce il concetto di algoritmo introducendo le‘macchine’ di Turing.

- Mostra che il problema della terminazione di una macchinadi Turing è formulabile come un’asserzione dell’aritmetica(ancora mediante una Gödelizzazione).

- Mostra che il problema della terminazione non è risolubilecon le macchine di Turing e quindi è indecidibile. Talerisultato implica che l’aritmetica stessa non è decidibile.

NOTA BENE. Contemporaneamente a Turing anche AlonzoChurch ha introdotto un concetto di calcolabilita' (λ-definibilita')basato su un sistema algoritmico (λ-calcolo). Tale sistema è statodimostrato equivalente, dallo stesso Turing. Ciò ha permesso diformulare la Tesi di Church-Turing: "Ogni funzione calcolabilecon qualunque approccio formale è T-computabile"

Tutti i formalismi definiti successivamente hanno confermato laTesi di Church-Turing.

Kleene (1936): funzioni ricorsive.Post (1943): sistemi di riscrittura.Markov (1949): algoritmi di Markov.Shepherdson e Sturgis (1963): macchine a registri.

Macchina di Turing universale

NOTA BENE. E' possibile descrivere una macchina di Turingcon una stringa di caratteri e fornire tale descrizione come inputad un'altra macchina di Turing.

Esistono vari modi di descrivere una macchina di Turing conuna stringa:

• possiamo fornire la sequenza delle quintuple checostituiscono la funzione di transizione

##d1##d2## ... ##dn

in cui è presente la quintupla qi#σj#qh#σk#tl se e solo se esistela regola di transizione δ(qi,σj)=(qh,σk, tl);

• possiamo sfruttare il fatto che ogni macchina di Turing puòessere realizzata come composizione di alcune macchineelementari e fornire la descrizione di una macchina comesequenza di tali macchine.

Sia DM la descrizione della macchina M.

Teorema. Esiste una macchina di Turing U, con stato inizialeq0U, (detta macchina di Turing universale) che, data unaqualunque descrizione DM, realizza la computazione q0UDM#x|—* αqfUβ, con qfU stato finale, se e solo se la macchina M, constato iniziale q0, realizza la computazione q0x |—* αqfβ, con qfstato finale.

Dim.

La macchina non fa che eseguire una per una le trasformazionirichieste dalle quintuple della macchina M contenute in DM. Altermine cancella dal nastro la descrizione DM.

NOTA BENE. Possiamo interpretare la MT universale come• un calcolatore e DM e x come un programma e i suoi dati• un interprete di un linguaggio di programmazione.

2.7 IL PROBLEMA DELLA TERMINAZIONE(HALTING PROBLEM)

Dimostriamo ora l'esistenza di una funzione che non e'calcolabile con una MT. In quanto segue assumiamo che lemacchine di Turing siano macchine ad un nastro, deterministichecon alfabeto Σ={0,1}.

Data una MT M=<Σ,b,K,q0,F,δ> sia DM la codifica di M in Σ.Per x∈Σ* definiamo il predicato della terminazione

h(DM,x) =1 se M con input x termina=0 se M con input x non termina

Teorema. Il predicato della terminazione delle macchine diTuring non è T-calcolabile.

NOTA BENE. Invece è T-calcolabile il predicato:

h(DM,x) =1 se M con input x termina= indefinito, altrimenti

Dim.Supponiamo che il predicato sia calcolabile, esista cioè unamacchina di Turing H che calcola h. Costruiamo la macchina H'che calcola il predicato

h'(DM) =1 se M con input DM termina=0 se M con input DM non termina

H' non è altro che la composizione di due macchine: la primacon input DM fornisce DMbDM, la seconda è la macchina H cheprende in input DMbDM e calcola il predicato della terminazione.

In altre parole H' è la macchina che verifica se una MT terminaquando le viene fornito in input il proprio codice.

Possiamo ora costruire una nuova macchina H" che prende ininput DM e calcola la funzione:

h"(DM) =0 se h'(DM) = 0=indefinito altrimenti

H", cioè, termina con 0 se H' si è fermata con 0 e si mette aciclare, se H' si è fermata con 1. Cosa accade ora se calcoliamoh"(DH"):

h"(DH") =indefinita se h"(DH") è definita=0 se h"(DH") è indefinita

In ogni caso abbiamo una contraddizione. Quindi non puòesistere la macchina H.