12. MACCHINE DI TURING E CALCOLABILITA’

12.1 Funzioni calcolabili secondo Turing 12.2 Insiemi e linguaggi decidibili e semidecidibili 12.3 Macchine di Turing multinastro e nondeterministiche 12.4 Macchina di Turing universale 12.5 Funzioni non calcolabili e problemi indecidibili 12.6 Relazioni tra macchine di Turing e calcolatori

12.1 FUNZIONI CALCOLABILI SECONDO TURING La macchina di Turing è un automa con testina di scrittura/lettura su nastro bidirezionale "potenzialmente" illimitato. Ad ogni istante la macchina si trova in uno stato appartenente ad un insieme finito e legge un carattere sul nastro. La funzione di transizione, in modo deterministico, fa scrivere un carattere, fa spostare la testina in una direzione o nell'altra, fa cambiare lo stato. Tali ‘macchine’ (modelli di calcolo) sono state introdotte da A. M. Turing nel 1935-36 con lo scopo di

- dare una definizione formale del concetto di algoritmo

- dimostrare l’esistenza di problemi non risolubili mediante algoritmi

- Le macchine di Turing: • consentono il riconoscimento, almeno "parziale" (semidecidibilità, accettazione), di tutti i linguaggi di tipo 0 • sono in grado di simulare ogni linguaggio di programmazione ed ogni altro modello di calcolo ("tesi di Church-Turing").

Def. Macchina di Turing:

M=<Σ,b,K,q0,F,δ> Σ alfabeto di simboli b carattere speciale, spazio bianco (blank) K insieme finito di stati q0 stato iniziale F 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 immobilità della testina

Σb = Σ∪{b}

ESEMPIO Consideriamo la macchina M con la funzione di transizione così definita: δ (q0, a) = (q0, b, d) δ (q0, b) = (q1, c, d) δ (q0, b) = (q0, a, d) δ (q1, b) = (q2, b, s) Stato iniziale: q0 Stato finale: q2 Come si comporta la macchina se viene avviata nello stato iniziale con la testina sul primo carattere della stringa aaabb? Come si comporta se viene avviata nello stato iniziale con la testina sul primo carattere della stringa aacbb?

Configurazioni e computazioni NOTA BENE. Anche se il nastro è infinito (illimitato), su di esso in ogni istante c’è un numero finito di caratteri ≠ b Def. Configurazione di una macchina è una terna costituita dalla (minima) porzione finita del nastro che contiene i simboli diversi da b, dalla posizione della testina, dallo stato corrente. Una configurazione viene generalmente rappresentata da una stringa appartenente al linguaggio (Σb)*.K.(Σb)+ ESEMPIO abbbbqiabbbbb

La conoscenza di una configurazione e della funzione di transizione consente di determinare la configurazione successiva.

Normalmente si fa l'ipotesi che all'inizio della computazione il nastro contenga l'input, il resto del nastro contenga b e la testina sia sul primo carattere dell'input Configurazione iniziale: stringa appartenente al linguaggio

{q0}.(Σb)+ Configurazione finale: stringa appartenente al linguaggio

(Σb)*.F.(Σb)+ La posizione della testina nella configurazione finale è in genere irrilevante.

Def. Una macchina di Turimg M determina una transizione dalla configurazione c alla configurazione c’ (indicato da: c |— c’) se c’ si ottiene da c applicando la funzione di transizione della macchina M. Def. Una computazione eseguita da una macchina di Turing è una sequenza eventualmente 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 c2 tramite un numero finito (eventualmente 0) di transizioni.

In ogni computazione può esistere al più una configurazione finale; se la macchina raggiunge una configurazione finale il calcolo termina. Un calcolo può terminare anche perché non è definita la configurazione successiva di una data configurazione (la funzione di transizione non è definita per quella configurazione). Def. Una computazione finita

c1 |— c2 |— .... |— cn è massimale se non esiste una configurazione c tale che cn |— c. In particolare siamo interessati a quelle computazioni massimali che portano dallo stato iniziale ad uno stato finale cioè computazioni del tipo c0 |—* cn in cui cn è una configurazione finale le altre corrispondono ad ‘errore’ o a

‘risultato non definito’.

Def. Macchina di Turing trasduttrice: ogni configurazione finale è del tipo xbqy, dove x è il contenuto del nastro all'inizio della computazione. Def. Una macchina trasduttrice calcola la funzione f se per tutte e sole le x su cui f è definita esiste q∈F tale che:

q0x|—*xbqf(x)

Si noti che la funzione f può essere una funzione da Γ* a Γ* (per un opportuno alfabeto Γ). In tal caso sia x che f(x) appartengono a Γ* e se Σ è l’alfabeto della macchina M avremo Γ ⊆ Σ. Come caso particolare la funzione calcolata può essere una funzione numerica definita su interi in notazione binaria o una funzione numerica definita su interi in notazione decimale. In tal caso sia x che f(x) sono numeri interi rappresentati rispettivamente in notazione binaria o decimale. ESEMPIO

Macchina di Turing M che calcola la funzione identità su una stringa x definita sull’alfabeto {a, b}. Tale macchina esegue la computazione: q0x|—*xbqx con q stato finale.

Def. Una funzione (parziale) f per la quale esiste una macchina di Turing che la calcola è detta calcolabile secondo Turing (T-calcolabile). Le macchine di Turing rappresentano uno dei più semplici e, al tempo stesso, più potenti modelli di calcolo. Le funzioni calcolabili secondo Turing sono la classe più ampia di funzioni calcolabili mediante algoritmi che si conosca. I logici Church e Turing hanno avanzato l’ipotesi che qualunque funzione calcolabile mediante algoritmi sia calcolabile mediante macchine di Turing (tesi di Church-Turing). Per tale motivo in genere diremo semplicemente ‘funzione calcolabile’ anziché ‘funzione calcolabile secondo Turing’.

ESERCIZI Realizzare le macchine di Turing che calcolano le funzioni f(x) = x+1, dove x ed x+1 sono interi rappresentati in binario f(x, y) = x+y, dove x, y ed x+y sono interi rappresentati in decimale

12.2 INSIEMI E LINGUAGGI DECIDIBILI E SEMIDECIDIBILI. Possiamo utilizzare macchine di Turing anche per riconoscere linguaggi (più in generale insiemi) o, in altre parole, per risolvere problemi di decisione. 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 affermativo Computazione rifiutante: responso negativo

Computazione non terminante: nessun responso

Informalmente: • Una macchina di Turing M riconosce un linguaggio L ⊆ Σ* se per ogni x∈Σ* M è in grado di stabilire se x∈L o no • Una macchina di Turing M accetta un linguaggio L se per tutte e sole le x∈L M è in grado di stabilire tale appartenenza, ma se x∉L M non garantisce un comportamento prestabilito: può dare una risposta negativa ma può anche non dare alcuna risposta.

Più formalmente: Def. M=<Σ,b,K,q0,F,δ> riconosce (decide) un linguaggio L se per ogni x∈Σ* esiste q∈K tale che • q0x |—* αqβ con α∈(Σb)* e β∈(Σb)+ e la computazione corrispondente è massimale, • se e solo se x∈L allora q∈F Def. Un linguaggio riconosciuto da una macchina di Turing è detto decidibile. Se un linguaggio non è decidibile è indecidibile.

NOTA BENE. Non è detto che una macchina di Turing possa sempre riconoscere un linguaggio. Esistono linguaggi di tipo 0 che non sono decidibili.

Def. M=<Σ,b,K,q0,F,δ> accetta un linguaggio L se per tutte e sole le x∈L esiste q∈F tale che • q0x |—* αqβ con α∈(Σb)* e β∈(Σb)+. Un linguaggio L è accettato da una macchina di Turing M se: Def. Un linguaggio accettato da una macchina di Turing è detto semidecidibile. NOTA BENE. Se un linguaggio è decidibile è anche semidecidibile. La famiglia dei linguaggi semidecidibili contiene strettamente la famiglia dei linguaggi decidibili poiché esistono linguaggi indecidibili ma semidecidibili.

ESERCIZI Realizzare le macchine di Turing che accettano i linguaggi

{ wcwR | w ∈ (a+b)+} { wwR | w ∈ (a+b)+} { wcw | w ∈ (a+b)+}

12.3 MACCHINE DI TURING MULTINASTRO E NON DETERMINISTICHE Possiamo definire molte varianti di macchine di Turing: • macchine a più nastri • macchine non deterministiche • macchine con alfabeto limitato a due soli simboli • macchine con nastro seminfinito ecc.

12.3.1 MT MULTINASTRO (MTM) Tutte queste varianti sono computazionalmente equivalenti: permettono il calcolo delle stesse funzioni e il riconoscimento (o accettazione) degli stessi linguaggi. Possono avere ‘tempi di calcolo’ diversi e utilizzare diverse quantità di ‘spazio’.

Def. Macchina di Turing a k nastri:

Mk=<Σ,b,Z0,K,q0,F,δ(k)> Σ alfabeto b carattere speciale, spazio bianco Z0 carattere speciale, carattere iniziale K insieme finito di stati q0 stato iniziale F 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 è lo stato; la stringa αi↓βi indica il contenuto e la posizione della testina sul nastro i. αi e' eventualmente vuota e il primo carattere di βi è 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 di

output (sola scrittura) e uno o più nastri di lavoro (lettura e scrittura, bidirezionali)

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

NOTA BENE L’automa a stati finiti può essere visto come una macchina di Turing con un solo nastro, di sola lettura, unidirezionale. L’automa a pila può essere visto come una macchina di Turing a due nastri, il primo di sola lettura e unidirezionale (one way), il secondo utilizzato in modo LIFO, come una pila.

ESEMPIO MTM per riconoscere xcxR con x∈{a,b}+

usiamo 2 nastri: uno di input monodirezionale a sola lettura e uno di lavoro che usiamo come pila durante la scansione di x, fino a c, x viene copiata sul nastro di lavoro durante la scansione di xR si confrontano i caratteri con quelli sul nastro di lavoro

configurazione iniziale della MTM: q0#↓z#↓Z0

3 stati: q0 per scandire x q1 per scandire xR q2 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

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 due nastri 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>

ESERCIZIO. Realizzare una macchina di Turing con due nastri (il primo di sola lettura e il secondo di lettura e scrittura ma entrambi bidirezionali) che riconosce il linguaggio { xcx | x ∈ (a+b)+}

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 h caratteri contemporaneamente la corrispondenza tra MT a nastro suddiviso in tracce ed una normale MT è immediata osservazione: se sulle tracce sono usati gli alfabeti Σ1,Σ2,....,Σh, una MT corrispondente ha un alfabeto Σ con |Σ|≥|Σ1|x|Σ2|x....x|Σh|

Teorema. Data una MTM M=<Σ,b,K,q0,F,δ(k)> a k nastri esiste una MT che simula t passi di Mk in O(t2) passi usando un alfabeto di cardinalità O((2|Σ|)k) Dim. Costruiamo una MT M'=<Σ',b,K',q0',F',δ'> con nastro suddiviso in 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 tutte le 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 passi proporzionale alla distanza (numero di caselle) tra i due marcatori 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" abbiamo da 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) 12.3.2 MT NONDETERMINISTICHE (MTND) Def. Macchina di Turing non deterministica:

M=<Σ,b,K,q0,F,δN> Σ alfabeto di simboli b carattere speciale, spazio bianco K insieme finito di stati q0 stato iniziale F 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 deterministica può essere rappresentata con un albero di computazioni deterministiche. nodi: configurazioni archi: transizioni NOTA BENE. Il grado di non determinismo coincide con il massimo numero di figli di un nodo dell'albero di computazione

Possiamo utilizzare macchine di Turing non deterministiche per accettare linguaggi. Def. Una MTND accetta una stringa se nell'albero di computazione è possibile trovare almeno un ramo che corrisponde ad una computazione accettante (cioè, almeno una foglia dell'albero corrisponde ad una configurazione finale). NOTA BENE. Anche in questo caso usiamo il termine accettazione anziché riconoscimento perché c’è asimmetria tra l’accettazione e il rifiuto di una stringa: in un caso basta che esista un cammino accettante, nell’altro caso bisogna che i cammini siano tutti rifiutanti.

Equivalenza tra MT e MTND Le MTND hanno lo stesso potere computazionale delle MT. Teorema. Data una macchina non deterministica M con grado di nondeterminismo d esiste una MT M' equivalente che simula k 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, tutte le sequenze finite composte da cifre comprese tra 1 e d nastro 3: nastro di lavoro

per ogni sequenza generata sul nastro 2, M' copia l'input sul nastro 3 le transizioni di ogni insieme δN(q,σ) sono numerate da 1 a d ogni sequenza di lunghezza s sul nastro 2 è in corrispondenza con una computazione di M di s passi

gli s numeri di ogni sequenza (compresi tra 1 e d) sono usati per 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 prima mossa la seconda transizione disponibile, per la seconda mossa la prima, ecc.... Se su qualche foglia dell'albero di computazione di M c'è uno stato finale, allora M' lo raggiunge in tempo finito altrimenti M' non raggiunge mai uno stato finale.

Se M termina in k passi M' ha bisogno di k O( Σ jdj) = O(kdk) passi j=0

Per dimostare che k

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

si può procedere come segue. Osserviamo innanzitutto che

k Σ d

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

j=0

Derivando si ottiene: k

Σ jdj-1

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

e quindi k

Σ jdj = O (kdk)

j=1

NOTA BENE. Una macchina non deterministica può "risolvere" un problema (ad esempio, accettare un linguaggio) in tempo polinomiale rispetto alla lunghezza della stringa mentre la simulazione effettuata da una macchina deterministica richiede tempo esponenziale. Problema aperto. Esiste una simulazione più efficiente? E' possibile simulare una macchina di Turing non deterministica con una deterministica in tempo polinomiale? ATTENZIONE: QUESTO E’ UN PROBLEMA DA UN MILIONE DI DOLLARI!

12.3.3 LINGUAGGI DI TIPO 0 E MT Teorema. Un linguaggio L è semidecidibile se e solo se è un linguaggio di Tipo 0 Dim. i) Tipo 0 -> MT Innanzitutto mostriamo come, dato un linguaggio L, generato da una grammatica G di tipo 0, possiamo definire una MT che lo accetta. In realtà, per semplificare la dimostrazione utilizzeremo una MTND M con 2 nastri ma sappiamo che esiste comunque una MT M' ad un solo nastro che può simulare M.

La macchina M opera nel seguente modo: partendo dall'assioma S la macchina applica via via, in modo non deterministico, tutte le produzioni applicabili. Dopo aver applicato una produzione, oltre a proseguire nell'applicazione delle produzioni, in modo non deterministico essa effettua una verifica per controllare se la forma di frase ottenuta è costituita da soli terminali e se essa coincide con la stringa da generare x. In tal caso M termina in uno 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 che devono essere confrontate con la stringa x.

ii) MT -> Tipo 0 Supponiamo ora di avere una macchina di Turing M che accetta un linguaggio L. Mostriamo come si può costruire una grammatica 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 opportuno qF∈F (per semplicità supporremo che esista un unico stato finale qF∈F). In corrispondenza della macchina M la grammatica G è così definita. Il suo alfabeto non terminale è costituito da alcuni simboli ausiliari, da simboli corrispondenti agli stati di M e da simboli che rappresentano il contenuto di due piste: quella superiore contiene caratteri σi di Σ∪{b}, quella inferiore caratteri σj di Σ∪{b}. Tali simboli sono dunque del tipo:

σi σj

La grammatica opera nel seguente modo: 1. introduce lo stato iniziale q0 2. genera una qualsivoglia stringa x di Σ∗ sulle due piste 3. genera un numero arbitrario di b a destra e a sinistra di x

sulle due piste 4. simula M sulla pista inferiore 5. se la pista inferiore è una configurazione finale e, solo in tal

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

Vediamo la forma delle varie produzioni. S → A1 q0 A2 σi

A2 → σi A2 | Α3 b 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 ogni regola di transizione, una serie di produzioni che realizzano, sulla pista inferiore, le stesse trasformazioni. Ad esempio, in corrispondenza della regola di transizione d(qk,σi) = (qh,σl,d)

avremo le regole di produzione σj σj

qk σ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 → ε

NOTA BENE. I linguaggi di Tipo 1 sono decidibili. Dato che le forme di frase non possono diminuire di lunghezza basta generare tutte le forme di frase in ordine di lunghezza crescente e confrontare quelle di soli terminali con la stringa da riconoscere.

12.4 MACCHINA DI TURING UNIVERSALE NOTA BENE. E' possibile descrivere una macchina di Turing con una stringa di caratteri e fornire tale descrizione come input ad un'altra macchina di Turing. Esistono vari modi di descrivere una macchina di Turing con una stringa: • possiamo fornire la sequenza delle quintuple che costituiscono la funzione di transizione

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

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

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

Sia DM la descrizione della macchina M. Teorema. Esiste una macchina di Turing U, con stato iniziale q0U, (detta macchina di Turing universale) che, data una qualunque descrizione DM, realizza la computazione q0UDM#x |—* αqfUβ, con qfU stato finale, se e solo se la macchina M, con stato iniziale q0, realizza la computazione q0x |—* αqfβ, con qf stato finale. Dim. La macchina non fa che eseguire una per una le trasformazioni richieste dalle quintuple della macchina M contenute in DM. Al termine 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.

12.5 FUNZIONI NON CALCOLABILI E PROBLEMI INDECIDIBILI Le macchine di Turing hanno consentito di - definire formalmente il concetto di algoritmo, di funzione

calcolabile e di problema decidibile - mostrare l’esistenza di funzioni non calcolabili e problemi non

decidibili Che cosa ha portato Turing ad affrontare questi problemi? Un po’ di storia.

1900: Al Secondo Congresso Internazionale di Matematica Hilbert formula 23 problemi matematici per il XX secolo (Problemi futuri della Matematica). Il secondo problema riguarda la consistenza (cioè la non contraddittorietà) della teoria logica dell’aritmetica dei numeri naturali basata sugli assiomi introdotti da Peano nel 1889. 1928: Hilbert riformula i problemi aperti riguardanti l’Aritmetica:

- L’Aritmetica è completa? Cioè è possibile dimostrare ogni asserzione vera?

- L’Aritmetica è consistente? Cioè siamo certi che non sia possibile dimostrare un’asserzione e anche la sua negazione? Se ciò fosse vero ogni asserzione sarebbe dimostrabile, quindi per dimostrare la consistenza è

sufficiente dimostrare che esistono asserzioni dell’aritmetica non dimostrabili.

- L’Aritmetica è decidibile? Cioè esiste un algoritmo che consente 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ò essere falsa; 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 teoria degli insiemi: 4. Russell: L’insieme di tutti gli insiemi che non

appartengono a se stessi, appartiene o no a se stesso? 5. Russell: In un villaggio il barbiere rade tutti e soli coloro

che non si radono da soli; chi rade il barbiere?

6. Gonseth: In una biblioteca può esistere un catalogo di tutti

i cataloghi bibliografici che non contengono se stessi?

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

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

- Ricorrere allo stesso tipo di assurdità che si presentano nei classici paradossi sfruttando l’autoreferenzialità e cioè creando un’asserzione w che afferma: w non è dimostrabile. Se w fosse falsa sarebbe dimostrabile e quindi necessariamente vera; quindi (se il calcolo non è contraddittorio) w non può essere falsa e deve essere vera. Ma se è vera non è dimostrabile. Quindi w è un esempio di asserzione vera ma non dimostrabile.

Conseguenze: l’aritmetica non è completa o non è consistente (ma la consistenza non è dimostrabile all’interno della teoria stessa).

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

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

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

- Mostra che il problema della terminazione non è risolubile con le macchine di Turing e quindi è indecidibile. Tale risultato implica che l’aritmetica stessa non è decidibile.

NOTA BENE. Contemporaneamente a Turing anche Alonzo Church ha introdotto un concetto di calcolabilità (λ-definibilità) basato su un sistema algoritmico (λ-calcolo). Tale sistema è stato dimostrato equivalente alle macchine di Turing, dallo stesso Turing. Ciò ha permesso di formulare la Tesi di Church-Turing: "Ogni funzione che sia dimostrata calcolabile con un qualunque approccio formale è calcolabile secondo Turing " Tutti i formalismi definiti successivamente hanno confermato la tesi di Church-Turing poiché si è dimostrato che hanno un potere computazionale equivalente alle macchine di Turing Kleene (1936): funzioni ricorsive. Post (1943): sistemi di riscrittura. Markov (1949): algoritmi di Markov.

Shepherdson e Sturgis (1963): macchine a registri.

IL PROBLEMA DELLA TERMINAZIONE (HALTING PROBLEM) E’ INDECIDIBILE Dimostriamo ora l'esistenza di un problema che non è decidibile e di una funzione che non è calcolabile con una MT. In quanto segue assumiamo che le macchine di Turing siano macchine ad un nastro, deterministiche con 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 di Turing non è calcolabile secondo Turing (o, in altre parole, il problema della terminazione è indecidibile).

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è una macchina 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 prima con input DM fornisce DMbDM, la seconda è la macchina H che

prende in input DMbDM e calcola il predicato della terminazione.

In altre parole H' è la macchina che verifica se una MT termina quando le viene fornito in input il proprio codice. Possiamo ora costruire una nuova macchina H" che prende in input 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 a ciclare, se H' si è fermata con 1. Cosa accade ora se calcoliamo h"(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.

Grazie alla tesi di Church-Turing abbiamo che la dimostrazione della indecidibilità del problema della terminazione ha come conseguenza che per ogni linguaggio di programmazione il problema della terminazione di una programma è indecidibile. Altri problemi indecidibili in informatica. Problemi indecidibili si incontrano in vari campi dell'informatica: - decidere se un programma è corretto, cioè se calcola la funzione

desiderata - decidere se, dato un programma ed una sua procedura (o

semplicemente una sua istruzione), la procedura sarà chiamata (o l'istruzione sarà eseguita)

- decidere se una grammatica CF è ambigua o se due grammatiche CF sono equivalenti.

Altri problemi indecidibili in matematica: - decidere se una formula del calcolo dei predicati del prim'ordine è un teorema (e quindi valida), - decidere se un'equazione diofantea, cioè un’equazione del tipo p(x1, ..., xn) = 0 dove p è un polinomio (come ad esempio l’equazione xn + ypxq + yrxszt = 0 ) ammette soluzioni intere non nulle (decimo problema di Hilbert).

12.6 RELAZIONI TRA MACCHINE DI TURING E CALCOLATORI MACCHINE A REGISTRI (RAM: Random Access Machines) Introdotte da Shepherdson e Sturgis nel 1963 per sviluppare la teoria della calcolabilità con un modello di macchina che fosse un’astrazione ragionevole di un calcolatore (macchina di von Neumann).

• Memoria costituita da un numero arbitrario di celle (registri) indirizzabili direttamente R[1], R[2], ..., R[n] contenenti un intero positivo di un numero qualunque di cifre • Registri speciali: contatore istruzioni (CI) accumulatore R[0] • Nastri di ingresso e di uscita • Unità centrale in grado di eseguire semplici istruzioni logico-aritmetiche

INPUT

............

R1

R2

R3

ALU

ACCUMULATORE

CONT. ISTRUZIONI

OUTPUT

Repertorio istruzioni LOAD, STORE: trasferimenti da registri ad accumulatore e viceversa READ, WRITE: trasferimenti da nastro di input a registri e da registri a nastro di output ADD, SUB, MULT, DIV, REM: operazioni aritmetiche (somma. sottrazione, moltiplicazione, divisione, resto della divisione) tra accumulatore e registri; il risultato resta nell'accumulatore JGTZ, JEQZ: salti condizionati in base al contenuto dell'accumulatore (rispettivamente > 0, = 0) JUMP: salto incondizionato HALT: terminazione

Sintassi delle istruzioni

LOAD [ = | * ] operando -> operando: numero STORE [ * ] operando d’ordine di registro ADD [ = | * ] operando -> = operando: SUB [ = | * ] operando operando immediato MULT [ = | * ] operando -> * operando: DIV [ = | * ] operando accesso indiretto REM [ = | * ] operando READ [ * ] operando WRITE [ = | * ] operando JUMP etichetta -> etichetta: numero JGTZ etichetta d’ordine di istruzione JEQZ etichetta HALT etichetta

Semantica delle istruzioni

(Esempi) ADD =n R[0]:= R[0]+ n CI:=CI+1 ADD n R[0] := R[0]+ R[n] CI := CI+1 ADD *n R[0] := R[0]+ R[R[n]] CI := CI+1 JGTZ m if R[0]>0 then CI := m

else CI := CI+1

Programmi per RAM Il programma non è contenuto in memoria ma è cablato: ad ogni macchina corrisponde un programma.

ESEMPIO - Programma per il calcolo di xy READ 1 lettura di x dal nastro di ingresso READ 2 lettura di y dal nastro di ingresso LOAD =1 STORE 3 inizializzazione del risultato 5 LOAD 2 JEQZ 14 fine ciclo while? LOAD 1 MULT 3 STORE 3 R[3] := x * R[3] LOAD 2 SUB =1 STORE 2 JUMP 5 14 WRITE 3 stampa del risultato HALT

Modelli di costo per le macchine a registri (RAM) • Modello a costi uniformi: costo unitario per l'esecuzione di ogni istruzione. Critiche: - moltiplicare due interi di 32 bit costa quanto moltiplicare due interi di 1024 bit - accedere ad una memoria di 1 kilobyte costa come accedere ad una memoria di 1 terabyte Vantaggi: il modello ha il pregio di essere molto semplice ed è quello più usato quando valutiamo il comportamento di programmi scritti in linguaggio ad alto livello.

• Modello a costi logaritmici: i costi sono proporzionali al numero di bit degli operandi e al logaritmo del numero d’ordine dei registri cui si accede. Definiamo la seguente funzione (lunghezza in binario):

l(n) = 1 se n=0 l(n) = (log n)+1 se n>0 - l'elaborazione di un intero n ha costo l(n) - l'accesso al registro i ha costo l(i)

Vantaggi: la valutazione dei costi è più realistica dal punto di vista asintotico (operandi molto grandi, memoria molto grande) Critiche: analisi più laboriosa

Per eseguire l'istruzione ADD 3 si paga: l (3) per accedere al registro 3 più l(R[3]) + l(R[0]) per eseguire la somma del contenuto del registro 3 e dell’accumulatore. Per eseguire l'istruzione ADD *3 si paga: l(3) + l(R[3]) per accedere al registro indirizzato dal registro 3 più l(R[R[3]]) + l(R[0]) per eseguire la somma.

ESEMPIO. Analisi del costo del programma per il calcolo di xy con il modello a costi logaritmici. La porzione di codice del ciclo viene eseguita O(y) volte. Costo di esecuzione totale: O(y2 log x)

READ 1 l(1)+l(x) O(log x) READ 2 l(2)+l(y) O(log y) LOAD =1 l(1) O(1) STORE 3 l(3)+l(1) O(1) 5 LOAD 2 l(2)+l(y) O(log y) JEQZ 14 l(y) O(log y) LOAD 1 l(1)+l(x) O(log x) MULT 3 l(3)+l(x)+l(xy) O(log x + y log x) STORE 3 l(3)+l(xy) O(y log x) LOAD 2 l(2)+l(y) O(log y) SUB =1 l(1)+l(y) O(log y) STORE 2 l(2)+l(y) O(log y) JUMP 5 1 O(1) 14 WRITE 3 l(3)+l(xy) O(y log x) HALT 1 O(1)

NOTA BENE. In pratica in situazioni in cui: a) i dati hanno una dimensione prefissata (es: 36 bit) b) le dimensioni della memoria sono prefissate i due modelli coincidono. NOTA BENE. Se le operazioni aritmetiche hanno precisione arbitraria o se si rende necessario l'accesso a memoria secondaria, si deve fare uso di modelli di calcolo analoghi al modello a costi logaritmici anche nell’analisi di complessità di algoritmi scritti in linguaggi ad alto livello

Simulazione di RAM con macchine di Turing Calcolabilità mediante RAM Def. Una funzione f: Nn →N è calcolabile da una RAM se esiste un programma P tale che

- se f(x1,...,xn)=y, allora P, attivato con x1,...,xn sul nastro di input, termina con y sul nastro di output

- se f(x1,...,xn) non è definita, allora P non termina

Teorema. Sia M=<{0,1},b,K,q0,F,δ> una MT con nastro seminfinito; esistono una RAM ed un programma P tali che se M calcola q0x|—*qFy e la RAM ha la stringa x nelle celle 2,....,|x|+1 al termine della computazione la RAM ha la stringa y nelle celle 2,....,|y|+1; inoltre la RAM simula T passi di M in tempo O(T log T) nel modello a costi logaritmici. Dim.

Stabiliamo una corrispondenza tra la cella i del nastro di M e la cella i+1 della memoria della RAM. Usiamo la cella 1 della RAM per rappresentare la posizione della testina di M.

All'inizio la cella 1 contiene il valore 2 (posizione iniziale della testina di M). P contiene una sequenza di istruzioni per ogni stato di M.

ESEMPIO. Se δ(q1,0)=<q2,1,d> e δ(q1,1)=<q3,0,s> allora P contiene il seguente frammento di programma (corrispondente allo stato q1):

.................... q1 LOAD *1 acquisizione del contenuto del nastro JGTZ q1' lettura di un 1 o di uno 0? LOAD =1 STORE *1 scrittura di un 1 sul nastro LOAD 1 ADD =1 STORE 1 movimento a destra della testina JUMP q2 aggiornamento dello stato q1' LOAD =0 STORE *1 scrittura di uno 0 sul nastro LOAD 1 SUB =1 STORE 1 movimento a sinistra della testina JUMP q3 aggiornamento dello stato ....................

Ogni passo di M è simulato da al più 8 istruzioni ognuna con costo O(log tmax) dove tmax è il massimo numero di celle usate da M Se M esegue T passi allora tmax ≤ T+1 Costo complessivo O(T log T)

Teorema. Data una RAM con programma P che calcola la funzione f esiste una MT M tale che se f(x1,...,xn)=y e sul nastro di input sono memorizzati in binario gli interi x1,...,xn la macchina M termina con la rappresentazione binaria di y sul nastro di output e se f(x1,...,xn) non è definita M non termina; inoltre se la computazione della RAM ha costo T nel modello a costi logaritmici allora M la simula in O(T2) passi. Dim. M ha tre nastri di lavoro, un nastro di input e un nastro di output. Sul nastro 1 sono memorizzati in binario i dati memorizzati nella memoria della RAM preceduti dal proprio indirizzo rappresentato in binario, cioè:

#i1#R[i1]#i2#R[i2]#i3#R[i3] ... #im#R[im]. Sul nastro 2 è rappresentato il contenuto dell'accumulatore. Il nastro 3 è usato per il funzionamento di M. Per ogni istruzione del programma della RAM, M ha un insieme di stati per eseguire le operazioni. • Istruzioni di salto JUMP, JGTZ, JZERO, HALT:

si controlla se il contenuto dell'accumulatore verifica le condizioni di salto e si gestiscono i corrispondenti cambiamenti di stato

• Istruzioni che non modificano il contenuto della memoria LOAD, ADD, SUB, MULT, DIV, WRITE:

si cerca sul nastro 1 il registro su cui si deve operare si esegue sul nastro contenente la rappresentazione dell'accumulatore l'operazione prevista

• Istruzioni che modificano il contenuto della memoria STORE,READ

si trascrive sul nastro 3 il contenuto del nastro 1 a destra del registro da modificare si esegue l'operazione modificando sul nastro 1 la rappresentazione del contenuto del registro da modificare si ricopia sul nastro 1 il contenuto del nastro 3 a destra della cella modificata.

Analisi di complessità. i) Ogni sequenza di transizioni relativa ad una operazione di RAM costa ad M, nel caso peggiore, un tempo dell'ordine della massima lunghezza lungmax del nastro 1 e se la RAM opera con costo totale T allora lungmax ≤ T. Infatti nel modello a costi logaritmici • se sul nastro 1 è presente l' indirizzo i vuol dire che la RAM ha acceduto almeno una volta al registro Ri e quindi ha pagato almeno una volta log i, d'altro canto l'indirizzo i occupa su nastro 1 proprio log i celle • se sul nastro 1 compare il contenuto del registro i allora la RAM ha pagato almeno una volta log(R[i]) d'altro canto R[i] occupa su nastro 1 proprio log(R[i]) celle quindi lungmax≤T

ii) Se la RAM opera con costo totale T le operazioni che essa esegue sono al più T In conclusione la MT M opera in tempo O(T lungmax) = O(T2).

NOTA BENE 1 • Tutto ciò che si può fare (calcolo di funzioni, riconoscimento o accettazione di insiemi, ecc.) con una MT si può fare anche con una RAM e viceversa (adottando le opportune convenzioni per la rappresentazione dell'input e dell'output). • Considerato che le RAM corrispondono a semplici programmi Assembler per una macchina di tipo von Neumann è chiaro che il loro potere computazionale coincide con quello dei linguaggi di programmazione ad alto livello per un normale calcolatore.

• Tesi di Church-Turing: tutti i modelli di calcolo introdotti per definire la calcolabilità (e tutti i linguaggi di programmazione) hanno al massimo lo stesso potere computazionale delle MT.

NOTA BENE 2 • Una MT ed una RAM con modello a costi logaritmici possono simularsi a vicenda in tempo polinomiale. La stessa cosa non si può fare se si considerano RAM con moltiplicazione e costi unitari (Esercizio). • Per stabilire se un problema può essere risolto in tempo polinomiale con un normale calcolatore possiamo indifferentemente far riferimento ad una MT o ad una RAM a costi logaritmici.