1

Informatica Teorica

Presentazione del corso

2

Obiettivi e motivazioni

Perché l’informatica “teorica”?

La teoria stimolata dalla pratica:

generalità, rigore, “controllo”

• Comprendere a fondo e in maniera critica i principi dell’informatica (riesame approfondito di concetti elementari)

• Costruire basi solide per comprendere e dominare l’innovazione futura (esempi: multimedialità, modellazione della computazione concorrente e “senza fili”, …)

• La teoria come “antidoto” alla superspecializzazione (si fa tanto parlare di interdisciplinarità …)

3

• Gettare un ponte tra corsi applicativi di base e avanzati (ingegneria del SW (1-2), calcolatori-architetture HW, sistemi distribuiti…)– Informatica teorica nel contesto del “percorso formativo” del

corso di studi

• Applicazione “diretta” a casi pratici: prosieguo attraverso il corso di metodi formali e tesi/ne– compresa prova finale del primo livello

4

Il programma

• La modellizzazione informatica(Come descrivo un problema e la sua soluzione): non tanto singoli modelli specialisticipiuttosto creare la capacità di capire e “inventare” modelli vecchi e nuovi

• La teoria della computazione:che cosa so/posso fare con lo strumento informatico(quali problemi so risolvere)?

5

Il programma (continua)

• La teoria della complessità:quanto costa risolvere un problema con lo strumento informatico?

• Gli sviluppi nel(i) corso(i) a valle (II livello)(corso integrato/congiunto con il master Polimi/UIC):I metodi formali nella progettazione informatica

6

L’organizzazione

• Prerequisiti:– Le basi essenziali di Informatica (Informatica 1,[2,3], Ing.

del SW)– Elementi di matematica non continua ([Algebra e Logica])

• Lezioni e esercitazioni (stile classico)– Interazione auspicata vivamente:

• Intervento diretto a lezione• Ricevimento • Email (da usare “cum grano salis”: burocrazia OK, problemi tecnici

meno)

– Tre sezioni del corso • 2 a Leonardo + 1 in Teledidattica CO-CR• Parallele e coodinate

7

L’organizzazione (continua)

• Esame basato sulla capacità di applicare, non di ripetere:principalmente scrittopossibilità di consultare testinon ripetitivo; stimolante (?)punteggio max > 30

• Prove in itinere standard• Possibilità di recuperi

– Dettagli da stabilire

8

L’organizzazione (continua)

• Il materiale didattico:– Testo ufficiale (in italiano [UTET] e in inglese [Wiley]):

Ghezzi/Mandrioli: Informatica teorica– Eserciziario (Mandrioli, Lavazza, Morzenti, San Pietro,

Spoletini, terza edizione, Esculapio)– Temi d’esame risolti

(http://www.elet.polimi.it/upload/mandriol/Didattica/TemiEsITRecenti.pdf)– Lucidi e (non!) appunti (inutili)

(Lucidi ≠ bigino!)(http://www.elet.polimi.it/upload/mandriol/Didattica/lucidiit.pdf)

9

I modelli dell’informatica

• Non (sol)tanto discreti rispetto a continui(bit e byte rispetto a numeri reali ed equazioni varie)

• Quanto:

10

– Generali:il sistema informatico nel contesto (spesso) di un sistema più ampio: impianto, organizzazione, sistema “embedded”, …

– Flessibili:spesso non esiste il “modello già pronto”:occorre saper adattare modelli esistenti ad esigenze specifiche e impreviste

– esistono molti (troppi) modelli specialistici:occorre saper studiare/inventare nuovi modelli

11

• Occorre (maggiore) attitudine dinamica e critica:– confronto modello-realtà– analisi e sintesi del modello/progetto

• rispetto a:

),,(2

2

2

2

2

2

zyxgzf

yf

xf =

∂∂+

∂∂+

∂∂

,

12

• Spesso la vera difficoltà di un problema sta nel ….formularlo!

Che significa: – “automatizzare una procedura d’ufficio”– “evitare incidenti ferroviari/aerei/…”– …?

13

• Modelli operazionali(macchine astratte, sistemi dinamici, …)basati sul concetto di stato e di meccanismi (operazioni) per la sua evoluzione

• Modelli descrittivitesi a formulare le proprietà desiderate o temute del sistema piuttosto del suo funzionamento

14

Esempi

• Modello operazionale dell’ellisse:

• Modello descrittivo dell’ellisse:

cybxa =+ 22 ..

15

• Descrizione operazionale dell’ordinamento:– Calcola il minimo e mettilo al primo posto;– Calcola il minimo degli elementi rimasti e mettilo al secondo

posto; – …

• Descrizione non-operazionale dell’ordinamento:– Individua una permutazione della sequenza data tale che

∀ i, a[i] ≤ a[i+1]

16

• In realtà le differenze tra modellizzazione operazionalee modellizzazione descrittiva non sono così nette: più che altro si tratta di un utile riferimento nel classificareun tipo di modello

17

Un primo, fondamentale, “meta”modello:il linguaggio

• Italiano, francese, inglese, …• C, Pascal, Ada, …

ma anche:• Grafica• Musica• Multimedialità, ...

18

Gli elementi di un linguaggio

• Alfabeto o vocabolario (sinonimi, matematicamente parlando):Insieme finito di simboli base{a,b,c, …z}{0,1}{Do, Re, Mi, …}{abate, abbaino, …, zuzzurellone} ASCII...

19

• Stringa (su un alfabeto A):sequenza ordinata e finita di elementi di A, anche con ripetizionia, b, aa, alfa, giovanni, alla, nel mezzo del cammin, …

• Lunghezza di una stringa:|a| = 1, |ab| = 2

• La stringa nulla ε: |ε| = 0• A* = insieme di tutte le stringhe, inclusa ε, su A.

A = {0,1}, A* = {ε, 0, 1, 00, 01, 10, …}

20

• Operazione su stringhe:concatenazione:x.yx = abb, y = baba, x.y = abbbabax = Quel ramo, y = del lago di Como, x.y = Quel ramo del lago di Como “.” : associativa, noncommutativa

• A*: monoide libero costruito su A mediante “.”

• ε: unità rispetto a “.”

21

Linguaggio

• L sottoinsieme di A*:(L⊆ A*)Italiano, C, Pascal, … ma anche:sequenze di 0 e 1 con numero pari di 1l’insieme degli spartiti in fa minorele matrici quadrate il cui determinante è 0…

• Concetto estremamente ampio, in un certo senso universale

22

Operazioni su linguaggi

• Operazioni insiemistiche:∪ , ∩, L1 -L2, ¬L = A* - L, )( LL ¬=

• Concatenazione (tra linguaggi):L1 .L2 = {x.y| x ∈ L1, y ∈ L2}

L1 = {0,1}*, L2 = {a,b}* ; L1 .L2 = {ε, 0,1, 0a, 11b, abb, 10ba, …. Non ab1!}

23

• L0 = {ε}, Li = Li-1.L• L* =

NB: {ε} ≠∅ !{ε} . L = L; ∅ . L = ∅

• + = “*-0”: L+ =

n

nL

∞

=0U

n

nL

∞

=1U

24

Alcuni risvolti “pratici”

•– L1 : insieme dei documenti “Word/Mac”– L2 : insieme dei documenti “Word/PC”– L1 ∩ L2 : insieme dei documenti Word “compatibili Mac-PC” (= ∅ ??)

• Composizione di un messaggio su rete:– x.y.z:– x = testata (indirizzo, …)– y = testo– z = “chiusura”

•– L1 : insieme dei messaggi e-mail– L2 : insieme dei messaggi SPAM– Filtro: L1 - L2 (= ∅ ??)

25

• Il linguaggio: strumento di espressione …• di un problema• x ∈ L?

– Un messaggio è corretto?– Un programma è corretto?– y = x2?– z = Det(A)?– Il sonoro di un film è ben sincronizzato con il video?

26

• y = τ(x)τ : traduzione: funzione da L1 a L2– τ 1 : raddoppio degli “1” (1 --> 11):

τ 1(0010110) = 0011011110, …– τ 2 : scambio a con b (a <---> b):

τ 2(abbbaa) = baaabb, …– ma anche:– compressione di files– protocolli autocorrettori– compilazione da linguaggi di alto livello in linguaggi oggetto– traduzione italiano ---> inglese

27

Conclusione

• Il concetto di linguaggio e le operazioni base ad esso associate forniscono un mezzo espressivo estremamente generale per descrivere sistemi di ogni tipo, loro proprietà e problemi ad essi connessi:

• Calcolare il determinante di una matrice;• Stabilire se un ponte crollerà sotto un certo carico;• ….• In fin dei conti nel calcolatore ogni informazione è una stringa

di bit ...

28

Modelli operazionali(macchine a stati, sistemi dinamici)

• Le macchine (automi) a stati finiti (FSA):– Un insieme finito di stati:

{Acceso, spento}, {on, off}, ….{1,2,3,4, …k}, {canali TV}, {fasce di reddito}, …

Rappresentazione grafica:

On Off

29

Comandi (ingressi) e transizioni tra stati

• Due semplicissimi flip-flop:

On OffT

T

On Off

SRR

S

Accensione e spegnimento di luce, ...

30

Una prima formalizzazione

• Un automa a stati finiti è (costituito da):– Un insieme finito di stati: Q– Un insieme finito (alfabeto) di ingressi: I– Una funzione di transizione (parziale):

δ: Q × I → Q

31

L’automa come riconoscitore di linguaggi(x ∈ L?)

• Una sequenza di mosse parte da uno stato iniziale ed è accettata se giunge in uno stato finale o diaccettazione.

q0 q1

0 01

1

L = {stringhe con un numero pari di “1” e un numero qualsiasi di “0”}

32

Formalizzazione del riconoscimento di L

• Sequenza di mosse:– δ∗ : Q × I∗ → Q

δ∗ definita induttivamente a partire da δδ∗ (q,ε) = qδ∗ (q,y.i) = δ(δ∗ (q,y), i)

• Stato iniziale: q0 ∈ Q• Stati finali o di accettazione: F ⊆ Q• x ∈ L ↔ δ∗ (q0,x) ∈ F

33

Riconoscimento di identificatori Pascal

q0 q1

<letter>

<digit>qE

<digit>

<digit> <letter>

<letter>

a

<letter>b

c...

Z

34

L’automa come traduttore di linguaggiy = τ(x)

Transizione con uscita:

q q’i/w

τ: ogni due “0” se ne riscrive 1 e ogni “1” se ne scrivono due (gli “0” devono essere pari)

q0 q1

1/11 1/110/ε

0/0

35

Formalizzazione degli automi traduttori

• T = <Q, I, δ, q0, F, O, η>– <Q, I, δ, q0, F>: come per A riconoscitore– O: alfabeto di uscita– η : Q × I → O*

• η* : Q × I* → O*

η∗ (q,ε) = εη∗ (q,y.i) = η∗ (q,y).η(δ∗ (q,y), i)

• τ(x) [x ∈ L] = η∗ (q0,x) [δ∗ (q0,x) ∈ F]

36

Analisi del modello a stati finiti(per la sintesi si rimanda ad altri corsi - e.g. calcolatori)

• Modello molto semplice ed intuitivo, applicato in molteplici settori, anche fuori dall’informatica

• Si pagherà un prezzo per tale semplicità?• …• Una prima proprietà fondamentale: il comportamento ciclico

degli automi a stati finiti

37

a

a

b

b

b

q1 q2

q3q4

q6 q7

q9

q8

bb aq0

b a

q5 a

C’e` un ciclo q1 ----aabab---> q1

Se un ciclo è percorribile una volta, esso è anche percorribile 2, 3, …, n, … 0 volte =========>

38

Più formalmente:

• Se x ∈ L e |x| > |Q| esiste un q ∈ Q e un w ∈ I+ tali che:• x = ywz

• δ∗ (q,w) = q

==============>• ywnz ∈ L, ∀ n ≥ 0 :

• Pumping Lemma

39

Dal pumping lemma derivano molte importanti proprietà degliFSA -positive e “negative”-

• L = ∅ ? ∃ x ∈ L ↔ ∃ y ∈ L, |y| < |Q|:Basta “eliminare tutti i cicli” dal funzionamento dell’automa che riconosce x

• |L| = ∞? Ragionamento simile

• …• Si noti che in generale, saper rispondere alla domanda “x ∈ L ?”

per un generico x, non implica saper rispondere alle altre domande!!

40

Alcuni risvolti pratici

• Ci interessa un linguaggio di programmazione consistente di … 0 programmi corretti?

• Ci interessa un linguaggio di programmazione in cui è possibile scrivere solo un numero finito di programmi?

• ...

41

Una conseguenza “negativa” del pumping lemma

• Il linguaggio L = {anbn|n > 0} è riconosciuto da qualche FSA?• Supponiamo, per assurdo, di sì:• Consideriamo x = ambm, m > |Q| e applichiamo il PL• Casi possibili:

– x = ywz, w = ak , k > 0 ====> am+r.kbm ∈ L, ∀ r : NO– x = ywz, w = bk , k > 0 ====> idem– x = ywz, w = ak bs , k,s > 0 ====> am-kakbs akbsbm-s ∈ L: NO

42

• Più intuitivamente: per “contare” n qualsiasi occorre una memoria infinita!• Rigorosamente parlando ogni calcolatore è un FSA, però …astrazione

sbagliata! Importanza del “concetto astratto di infinito”!• Passando dall’esempio “giocattolo” {anbn} a casi più concreti:

– Il riconoscimento di strutture parentetiche tipiche dei linguaggi diprogrammazione non è effettuabile con memoria finita

• Occorrono perciò modelli “più potenti”

43

Le proprietà di chiusura dei FSA

• Il concetto matematico di chiusura:– I numeri naturali sono chiusi rispetto alla somma– ma non rispetto alla sottrazione– I numeri interi sono chiusi rispetto a somma, sottrazione,

moltiplicazione, ma non …– I numeri razionali …– I numeri reali …– Importanza generale del concetto di chiusura (di operazioni e

relazioni)

44

Nel caso dei linguaggi:

• L = {Li}: famiglia di linguaggi

• L chiusa rispetto a OP se e solo se per ogni L1 , L2 ∈ L , L1 OP L2 ∈ L .

• R : linguaggi regolari, riconosciuti da FSA

• R chiusa rispetto alle operazioni insiemistiche, alla concatenazione, la “*”, … e praticamente “tutte” lealtre.

45

Intersezione

ab aA q9q0 q1 q2

ab aB p9p0 p1 p2

Posso simulare il “funzionamento parallelo” di A e Bsemplicemente “accoppiandoli”:

p0q0ab a<A,B> p1q1 p2q2 p9q9

46

Formalmente:

• Dati A1 <Q1, I, δ1, q01, F1> e

A2 <Q2, I, δ2, q02, F2>

• < A1, A2 >:<Q1 × Q2, I, δ, <q0

1 , q02 >, F1 × F2 >

δ(<q1 , q2 > , i) = <δ1(q1, i), δ2(q2,i)>• Una semplice induzione dimostra che

L(< A1, A2 >) = L(A1) ∩ L( A2 )

47

Unione

• Costruzione simile …oppure ...

Complemento:

q0 q1

0 01

1

Idea: F^ = Q -F: Sì però ….

48

q0 q1

0 01

Se mi limito a scambiare F con Q - F …

Il problema nasce dal fatto che δ è parziale:

q0 q1

10 0

qE0

1

1

49

Filosofia generale del complemento

• Se esamino tutta la stringa allora basta “scambiare il sì con ilno” (F con Q-F)

• Se però non riesco a giungere in fondo alla stringa (mi “blocco o …”) allora scambiare F con Q-F non funziona

• Nel caso dei FSA il problema è facilmente risolto …• In generale occorre cautela nel considerare la risposta negativa a

una domanda come problema equivalente al ricavare la risposta positiva!!

50

Aumentiamo la potenza dei FSA aumentandone lamemoria

• Una visione più “meccanica” del FSA:

Nastro di lettura

Organo di controllo (a stati finiti)

Nastro di scrittura

51

• Ora “arricchiamolo” un po’:

Memoria a “pila”Nastro di lettura

Organo di controllo (a stati finiti)

a

pq

AB

x

Nastro di scritturaZ0

52

La mossa dell’automa a pila:

• In funzione del:– simbolo letto dal nastro di ingresso (però potrebbe anche non leggere

nulla …)– simbolo letto dalla pila– stato dell’organo di controllo:– cambia stato– sposta di una posizione la testina di lettura– sostituisce al simbolo A letto dalla pila una stringa α di simboli (anche

nulla)– (se traduttore) scrive una stringa (anche nulla) nel nastro di uscita

(spostando la testina di conseguenza)

53

• La stringa di ingresso x viene riconosciuta (accettata) se– L’automa la scandisce completamente (la testina di lettura

giunge alla fine di x)– Giunto alla fine di x esso si trova in uno stato di accettazione

(come il FSA)

• Se l’automa è anche traduttoreτ(x) è la stringa che si trova nel nastro di scrittura dopo che x è stata scandita completamente (se x è accettata,altrimenti τ(x) è indefinita: τ(x) = ⊥ .

• (⊥ : simbolo di “indefinito”)

54

Un primo esempio: riconoscimento di {anbn | n > 0}

q0 q3

a,A/AA

a,Z0/ Z0 B

b,A/ε

b,A/ε

b,B /εq2q1

a,B/BA

b,B /ε

A n - 1 AA

B

Z0

55

Oppure:

q0

a,A/AA

a,Z0/ Z0 Aq1 q3

b,A/ε

q2b,A/ε ε, Z0 /ε

ε- mossa!

56

Un (classico) automa-traduttore a pila

a,Z0/ Z0A,ε

a,A/ AA,ε

a,B/ BA,ε

b,Z0/ Z0B,ε

b,A/ AB,ε

b,B/ BB,ε

c,A/ ε, a

c,B/ ε, b

ε,A/ ε, a

ε,B/ ε, b

ε,Z0/ ε,ε

q0

q1 q2

57

Formalizziamo un po’ ...

•Automa [traduttore] a Pila: <Q,I,Γ,δ, q0, Z0 , F [O, η]>

•Q, I, q0, F [O] come FSA [T]

• Γ alfabeto di pila (per comodità disgiunto dagli altri)

•Z0 : simbolo iniziale di pila

• δ: Q × (I ∪ {ε}) × Γ → Q × Γ* δ : parziale!

• η: Q × (I ∪ {ε}) × Γ → O* ( η definita dove δ è definita)

<p,α> = δ(q,i, A)w = η(q,i, A)

Notazione grafica:

i,A/α,wpq

58

• Configurazione (concetto generale di stato): c = <q, x, γ, [z]>:– q: stato dell’organo di controllo– x: stringa ancora da leggere nel nastro di ingresso (la testina è

posizionata sul primo carattere di x)– γ : stringa dei caratteri in pila

(convenzione: <alto-destra, sinistra-basso>)– z: stringa già scritta nel nastro di uscita

59• Transizione tra configurazioni:

c = <q, x, γ, [z]> |-- c’ = <q’, x’, γ’, [z’]>– γ = βA– Caso 1: x = i.y e δ(q,i, A) = <q’, α> (è definita)

[η(q,i, A) = w]– x’ = y– γ’= βα– [z’ = z.w]– Caso 2: x = y e δ(q,ε, A) = <q’, α> (è definita)

[η(q, ε, A) = w]– x’ = y– γ’= βα– [z’ = z.w]

• NB: ∀ q,A, δ(q,ε, A) ≠ ⊥ ⇒ δ(q, i, A) = ⊥ ∀ i.• Altrimenti … nondeterminismo!

60

• Accettazione [e traduzione] di una stringa • |-*- : chiusura transitiva e riflessiva di |--• x ∈ L [z = τ(x)] ↔• c0 = <q0,x, Z0, [ε]> |-*- cF = <q, ε, γ, [z]>, q ∈ F

Occhio alle ε-mosse, soprattutto a fine stringa!!

61

L’automa a pila in pratica

• Cuore dei compilatori• Memoria a pila (LIFO) adatta ad analizzare strutture

sintattiche “nestate” (espressioni aritmetiche, istruzioni composte, …)

• Macchina astratta a run-time dei linguaggi conricorsione

• ….Sfruttamento sistematico nel corso di linguaggi etraduttori

62Proprietà degli automi a pila (soprattutto come riconoscitori)

• {anbn | n > 0} riconoscibile da un automa a pila (non da un FSA)– Però {anbncn | n > 0} ….– NO: dopo aver contato -mediante la pila- n a e decontato n b come facciamo a

ricordare n per contare i c?La pila è una memoria distruttiva: per leggerla occorre distruggerla!Questa limitazione dell’automa a pila può essere dimostrata formalmente mediante un’estensione del pumping lemma.

• {anbn | n > 0} riconoscibile da un automa a pila;{anb2n | n > 0} riconoscibile da un automa a pila

• Però {anbn | n > 0} ∪ {anb2n | n > 0} …– Ragionamento -intuitivamente- simile al precedente:– Se svuoto tutta la pila con n b perdo memoria se ci sono altri b– Se ne svuoto solo metà e non trovo più b non posso sapere se effettivamente sono

a metà pila– La formalizzazione però non è la stessa cosa ….

63

Alcune conseguenze

• LP = classe dei linguaggi riconosciuti da automi a pila

• LP non chiusa rispetto all’unione né all’intersezione• Perché?• Quanto al complemento …

Il principio è lo stesso dei FSA: scambiare stati di accettazionecon stati di non accettazione.Nascono però nuove difficoltà

64

• La δ va completata (come per gli FSA) con lo stato di errore.Occhio però al nondeterminismo causato dalle ε-mosse!

• Le ε-mosse possono causare cicli ---> non si giunge mai in fondo alla stringa ----> la stringa non è accettata, ma non è accettata neanche dall’automa con F^ = Q-F.

• Esiste però una costruzione che ad ogni automa associa unautoma equivalente loop-free

• Non è ancora finita: che succede se si ha una sequenza di ε-mosse a fine scansione con alcuni stati in F e altri no??

65

• <q1, ε, γ1> |-- <q2, ε, γ2> |-- <q3, ε, γ3> |-- …q1∈ F, q2 ∉ F, …. ?

• Occorre “obbligare” l’automa a decidere l’accettazione solo alla fine di una sequenza (necessariamete finita) di ε-mosse.

• Anche questo è possibile mediante apposita costruzione.

Anche in questo caso più che i tecnicismi della costruzione/dimostrazione interessa il meccanismo generale per riconoscere il complemento di unlinguaggio: talvolta la stessa macchina che risolve il “problema positivo” può essere impiegata per risolvere anche quello negativo in modo semplice; ma ciò non è sempre banale: occorre la sicurezza di “poter arrivare in fondo” ….

66

Gli automi a pila [riconoscitori (AP) o traduttori (TP)] sono più potentidi quelli a stati finiti (un FSA è un banale caso particolare di AP; in più gli AP hanno capacità di conteggio illimitato che gli FSA non hanno)Però anche gli AP/TP hanno i loro limiti …… un nuovo e “ultimo” (per noi) automa:La Macchina di Turing (MT)Modello “storico” di “calcolatore”, nella sua semplicità di notevole importanza concettuale da diversi punti di vista.Ora lo esaminiamo come automa; successivamente ne ricaveremo proprietà universali del calcolo automatico.

Per ora versione a “K-nastri”, un po’ diversa dal (ancora più semplice)modello originario. Spiegheremo poi il perché di questa scelta.

67MT a k-nastri

Primo nastro di memoria

Nastro di lettura A

a

pq

Secondo nastro di memoria

B

K-esimo nastro di memoria

D

x

Nastro di scrittura

68

Descrizione informale e parziale formalizzazione delfunzionamento della MT

(formalizzazione completa: esercizio)

• Stati e alfabeti come per gli altri automi (ingresso, uscita, organo di controllo,alfabeto di memoria)

• Per convenzione storica e convenienza di certe “tecnicalità matematiche” i nastri sono rappresentati da sequenze infinite di celle [0,1,2, …] invece che da stringhefinite. Però esiste un simbolo speciale “blank” (“ “, o b “barrato” o “_”) o spazio bianco e si assume che ogni nastro contenga solo un numero finito di celle noncontenenti il blank. Evidente l’equivalenza tra i due modi di rappresentare il contenuto dei nastri.

• Testine di lettura/scrittura, pure “simili” alle altre testine

69

• La mossa della macchina di Turing:• Lettura:

– carattere in corrispondenza della testina del nastro di ingresso– k caratteri in corrispondenza delle testine dei nastri di memoria– stato dell’organo di controllo

• Azione conseguente:– cambiamento di stato: q ----> q’– riscrittura di un carattere al posto di quello letto su ogni nastro di memoria:

Ai ----> Ai’, 1 <= i <= k– [scrittura di un carattere sul nastro di uscita]– spostamento delle k + 2 testine:

• le testine di memoria e di ingresso possono spostarsi di una posizione a destra (R) o asinistra (L) o stare ferme (S)

• la testina del nastro di uscita può spostarsi di una posizione a destra (R) o stare ferma(S) (se ha scritto “è bene” che si sposti; se si sposta senza aver scritto lascia il blank)

70

Di conseguenza:

}],{[},,{:][, 1 SROSLRQIQ kkk ×××Γ×→Γ××>< +ηδ

(parziali!)

Notazione grafica:

q q’i,<A1,A2, …Ak>/[o], <A’1, A’2 …A’k> , <M0, M1 …Mk , [Mk+1 ]>

Mi ∈ {R,L,S} Mk+1 ∈ {R,S}

Perché non si perde generalità usando O invece che O* in uscita?

71

•Configurazione iniziale:

•Z0 seguito da tutti blank nei nastri di memoria

•[nastro di uscita tutto blank]

•Testine nelle posizioni 0-esime di ogni nastro

•Stato iniziale dell’organo di controllo q0

•Stringa di ingresso x a partire dalla 0-esima cella delnastro corrispondente, seguita da tutti blank

72

• Configurazione finale:– Stati di accettazione F ⊆ Q– Per comodità, convenzione:

<δ,[η]> (q, …) = ⊥ ∀ q ∈ F:– La macchina si ferma quando <δ,[η]> (q, …) = ⊥– La stringa x di ingresso è accettata se e solo se:

• dopo un numero finito di mosse la macchina si ferma (si trova in una configurazione in cui <δ,[η]> (q, …) = ⊥

• lo stato q in cui si trova quando si ferma ∈ F

• NB:– x non è accettata se:

• la macchina si ferma in uno stato ∉ F; oppure• la macchina non si ferma

– C’e` una somiglianza con l’AP (anche l’AP non loop-free potrebbe non accettare per “non fermata”), però… esiste la MT loop-free??

73

Alcuni esempi

• MT che riconosce {anbncn | n > 0}

Nastro di lettura

a b c

Z0

OC

aa b b cNastro di memoria

c

M M M

74

a, Z0/Z0, <S, R>q0 q1 q2

b, _ / _, <S, L>

b, M / M, <R, L>a, _ / M, <R, R>

c, Z0/Z0, <S, R>

_, _ / _, <S, S>q3qF

c, M / M, <R, R>

75

Calcolo del successore di un numero codificato in cifre decimali

• M copia tutte le cifre di n su T1, alla destra di Z0.Così facendo sposta la testina di T2 dello stesso numero di posizioni.

• M scandisce le cifre di T1 da destra a sinistra. Scrive in T2 da destra a sinistra modificando opportunamente le cifre (i 9 diventano 0, la prima cifra ≠ 9 diventa la cifra successiva, poi tutte le altre vengono copiate uguali, …)

• M ricopia T2 sul nastro di uscita.

• Notazione: � : qualsiasi cifra decimale• _ : blank• # : qualsiasi cifra ≠ 9• ^ : il successore della cifra denotata da # (nella stessa transizione)

76

Nastro di lettura

99

Z0

OCT2

Z0

Nastro di scrittura

3 41 9T1

1 43 9 9 9

77

q0 q1 q2

q3 q4

q5

q6 q7

�,Z0,Z0/_,<Z0,Z0>,<S,R,R,S>�,_,_/_,< �,_>,<R,R,R,S>

_,_,_/_,< _,_>,<S,L,L,S>

_,9,_/_,< 9,0>,

<S,L,L,S>

_,#,_/_,< #,^>,<S,L,L,S>_, �,_/_,< �, � >,<S,L,L,S>

_,Z0,Z0/_,<Z0,Z0>,<S,R,R,S>

_, �, � / �,< �, � >,<S,R,R,R>_,_,_/_,< _,_>,<S,S,S,S>

_,Z0,Z0/1,<Z0,Z0>,<S,R,R,R>

_, �, 0 / 0,< �, 0 >,<S,R,R,R>

_,_,_/_,< _,_>,<S,S,S,S>

78

Proprietà di chiusura delle MT

• ∩ : OK (una MT puo, facilmente simularne due, sia “in serie”che “in parallelo”)

• ∪ : OK (idem)• Idem per altre operazioni (concatenazione, *, ….)

• E il complemento?

Risposta negativa! (Dimostrazione in seguito)Certo se esistessero MT loop-free come gli AP, sarebbe facile: basterebbe definire l’insieme degli stati di halt (facile renderlo disgiunto dagli stati non di halt) e partizionarlo in stati di accettazione e stati di non accettazione.

==========>Evidentemente il problema sta nellecomputazioni che non terminano

79

Modelli equivalenti di MT

• MT a nastro singolo (≠ da MT a un nastro - di memoria!)

Nastro unico (di solito illimitato a destra e sinistra):funge da ingresso, memoria e uscita

OC

x

80

• MT a nastro bidimensionale

OC

• MT a k testine per nastro

•…..

81

Le varie versioni di MT sono tutte tra loro equivalenti, rispetto alla capacità riconoscitiva/traduttiva:

ad esempio:

OC

*#

Memorizza i contenuti delle k + 1 celle puntate dalle testine

x Contenuto Nastro i-esimo*

Marca posizione testina i-esima

82

Che relazioni sussistono tra automi vari (MT in particolare) emodelli di calcolo più tradizionali e realistici?

•La MT può simulare una macchina di von Neumann (pur essa “astratta”)•La differenza fondamentale sta nel meccanismo di accesso alla memoria: sequenziale invece che “diretto”•La cosa non inficia la potenza della macchina dal punto di vista della capacità computazionale (classe di problemi risolvibili)•Può esserci invece impatto dal punto di vista della complessità del calcolo• Esamineremo implicazioni e conseguenze in entrambi i casi

83

I modelli (operazionali) non deterministici

• Solitamente si tende a pensare ad un algoritmo come una sequenza dioperazioni determinata: in un certo stato e con certi ingressi non sussistono dubbi sulla “mossa” da eseguire

• Siamo sicuri che ciò sia sempre auspicabile?

Confrontiamoif x > y then max := x else max := yconif x >= y then max := x

y >= x then max := yfi

84• E` solo una questione di eleganza?

• Pensiamo al costrutto case del Pascal & affini:perché non un

• case– x = y then S1– z > y +3 then S2– …. then …

• endcase?

85

Un’altra forma di nondeterminismo “nascosto”: la ricerca “cieca”

?

86• In realtà i vari algoritmi di ricerca sono una “simulazione” di algoritmi“sostanzialmente nondeterministici”:

• L’elemento cercato si trova nella radice dell’albero?

• Se sì OK. Altrimenti

– Cerca nel sottoalbero di sinistrao

– cerca nel sottoalbero di destra

• scelte o priorità tra le diverse strade sono spesso arbitrarie

• Se poi fossimo in grado di assegnare i due compiti in parallelo a due diversemacchine ---->

• Nondeterminismo come modello di computazione o almeno di progettazionedi calcolo parallelo(Ad esempio Ada ed altri linguaggi concorrenti sfruttano il nondeterminismo)

87

Tra i tanti modelli nondeterministici (ND):versioni ND dei modelli già noti

• FSA ND (ne vedremo tra poco la “comodità”)

q1

q2

q3

a

a

Formalmente: δ(q1,a) = {q2, q3}

δ : Q × I → P(Q)

88δ* : formalizzazione della sequenza di mosse

q1

q2

q3

a

a

q4

q5

q6

b

b

b

b

δ(q1,a) = {q2, q3}, δ(q2,b) = {q4, q5}, δ(q3,b) = {q6, q5}

δ∗ (q1,ab) = {q4, q5 , q6}

),'().,(),('

*

*

*iqiyq

yqqδδ

δ∈∪=

}{),( qq εδ =

89

Come accetta un FSA ND?

∅≠∩↔∈ FxqLx ),( 0*δ

Tra i vari modi di funzionamento dell’automa è sufficiente che uno di essi abbia successo per accettare la stringa di ingresso

Sono possibili convenzioni diverse )),(( 0* Fxq ⊆δ

90

Gli AP nondeterministici (APND)

• In realtà essi nascono ND di natura:

q1

q2

q3

i, A/α

ε, A/β

91

• Tanto vale rimuovere la restrizione del determinismo e generalizzare:

q1

q2

q3

i, A/α

i, A/β

)(}){(: *Γ×℘→Γ×∪× QIQ Fεδ

• Perché l’indice F?• Al solito l’APND accetta x se esiste una sequenza• c0 |-*- <q, ε, γ>, q ∈ F• |-- è non più univoca!

92

Un “banale” esempio

q0’

a,A/AA

a,Z0/ Z0 Aq1’ q3’

b,A/ε

q2’b,A/εε, Z0 /ε

q0

ε,Z0/ Z0

q0”

a,A/AA

a,Z0/ Z0 Aq1

ε,Z0/ Z0

q4

b,A/εε, Z0 /ε

q2b,A/Α

q3

b,A/Α

93

Alcune immediate ma significative conseguenze

• Gli APND possono riconoscere un linguaggio non riconoscibile dagli APdeterministici ---->sono più potenti

• La costruzione precedente può essere facilmente generalizzata ottenendo una dimostrazione costruttiva (come altre precedenti) di chiusura rispetto all’unione degli APND -proprietà non sussistente per gli AP deterministici

• La chiusura rispetto all’intersezione invece continua a non sussistere ({anbncn} = {anbnc*} ∩ {a*bncn} non è riconoscibile mediante una pila, neanche in modo ND) -I due controesempi precedenti {anbncn} e {anbn} ∪ {anb2n} non sono poi così simili tra loro …

94

• Se una famiglia di linguaggi è chiusa rispetto all’unione e non rispetto all’intersezione non può essere chiusa rispetto al complemento (perché?)

• Ciò mette in evidenza il profondo cambiamento causato dal nondeterminismo rispetto alla complementazione di un problema - in generale-:se il modo di funzionamento della macchina è univoco e se la sua computazione giunge al termine è sufficiente scambiare la risposta positivacon quella negativa per ottenere la soluzione di un “problema complemento” (ad esempio presenza invece di assenza di errori in un programma)

95

• Nel caso degli APND pur essendo possibile, come per gli APD, far sì che una computazione giunga sempre al termine, potrebbero darsi duecomputazioni

– co |-*- <q1, ε, γ1>– co |-*- <q2, ε, γ2>– q1 ∈ F, q2 ∉ F

• In questo caso x è accettata• Però se scambio F con Q-F, x continua ad essere accettata:

nell’ambito del nondeterninismo scambiare il sì con il no non funziona!

• E gli altri tipi di automi?

96FSA ND

q1

q2

q3

a

a

q4

q5

q6

b

b

b

b

Partendo da q1 e leggendo ab l’automa si trova in uno stato che appartiene all’insieme {q4,q5,q6}

Chiamiamo nuovamente “stato” l’insieme dei possibili stati in cui si può trovare l’automa ND durante il suo funzionamento.

Sistematizzando ...

97

• Dato un FSA ND ne costruisco automaticamente uno equivalente determistico ---->

• gli automi FSA ND non sono più potenti dei loro fratelli deterministici(diversamente dagli AP)(e allora a che cosa servono?)

• AND = <QN,I, δN, q0N, FN>• AD = <QD,I, δD, q0D, FD>

– QD = ℘ (QN )

–

– q0D = {q0N}

–

),(),( iqiq NqqDDDN

δδ∈∪=

}|{ ∅≠∩⊆= ND FQQQF

98

• E` bensì vero che, per ogni automa FS ND ne posso trovare (e costruire) uno equivalente deterministico

• Ciò non significa che sia superfluo usare gli FSA ND:– Può essere più facile “progettare” un AND e poi ricavarne automaticamente uno

deterministico, risparmiandosi la fatica di costruirlo noi stessi deterministico finda subito (ne vedremo un’applicazione tra breve)

– Da un AND a 5 stati (ad esempio), ne ricavo, nel caso pessimo, uno con 25 stati!•

• Resta da esaminare la MT ...

99

Le MT nondeterministiche

}]),{[},,{(:][, 1 SROSLRQIQ kkk ×××Γ×℘→Γ××>< +ηδ

•E` necessario l’indice F?

•Configurazioni, transizioni, sequenze di transizioni e accettazione sono definite come al solito

•Il nondeterminismo aumenta la potenza delle MT?

100Albero delle computazioni

c32

c22

c13c12

c26c25c23 c24

c31 ckjcim

Computazionenon terminante

c0 C di accettazione

C di halt ma nonaccettazione

c11

c21

101

• x è accettata da una MT ND se e solo se esiste una computazione della M ND che termina in uno stato di accettazione

• può una MT deterministica stabilire se una sua “sorella” ND accetta x, ossia accettare a sua volta x se e solo se la M ND la accetta?

• Si tratta di percorrere o “visitare” l’albero delle computazioni ND per stabilire se esiste in esso un cammino che termina in uno stato di accettazione

• Questo è un (quasi) normale e ben noto problema di visita di alberi, per il quale esistono classici algoritmi di visita

• Il problema è perciò ridotto ad implementare un algoritmo di visita di alberi mediante MT: compito noioso ma sicuramente fattibile … a meno del “quasi” di cui sopra ...

102

• Tutto facile se l’albero delle computazioni è finito• Però potrebbe darsi il caso che alcuni cammini dell’albero siano infiniti

(descrivono computazioni che non terminano)• In tal caso, un algoritmo di visita depth-first (ad esempio, in preordine

sinistro) potrebbe “infilarsi in un cammino infinito” senza scoprire che in un altro punto dell’albero ne esiste uno finito che porta all’accettazione.

• Il problema è però facilmente risolvibile adottando ad esempio un algoritmo di visita di tipo breadth-first (che usa una struttura a coda invece di una a pila per accumulare i vari nodi da esaminare).

103Conclusioni

• Nondeterminismo: utile astrazione per descrivere problemi/algoritmi di ricerca; situazioni in cui non esistono elementi di scelta, o sono tra loro indifferenti; computazioni parallele

• In generale non aumenta la potenza di calcolo, almeno nel caso delle MT (che sono l’automa più potente tra quelli visti finora) però può fornire descrizioni più compatte

• Aumenta la potenza degli automi a pila• Può essere applicato a diversi modelli di calcolo (praticamente a tutti); in alcuni casi sono stati

definiti modelli “intrinsecamete nondeterministici” (inventati apposta per descrivere fenomeni nondeterministici

• Per semplicità ci siamo concentrati soprattutto su riconoscitori nondeterministici ma il concetto può essere esteso anche agli automi traduttori.

• NB: il concetto di ND non è da confondersi con un fenomeno stocastico (esistono modelli stocastici -e.g. catene di Markov- che sono ben diversi da quelli nondeterministici)

104

Grammatiche

• Gli automi sono un modello riconoscitivo/traduttivo/elaborativo (dilinguaggi):essi “ricevono” una stringa nel loro ingresso e la elaborano in vari modi

• Passiamo ora ad esaminare un modello generativo:una grammatica produce o genera stringhe (di un linguaggio)

• Concetto generale di grammatica o sintassi (matematicamente, alfabeto evocabolario e grammatica e sintassi sono sinonimi):insieme di regole per costruire frasi di un linguaggio (stringhe): si applica aqualsiasi nozione di linguaggio nel senso più lato.

• In modo sostanzialmente simile ai normali meccanismi linguistici una grammatica formale genera stringhe di un linguaggio attraverso un processodi riscrittura:

105

• “Una frase è costituita da un soggetto seguito da un predicatoUn soggetto a sua volta può essere un sostantivo, oppure unpronome, oppure ….Un predicato può essere costituito da un verbo seguito da uncomplemento…”

• Un programma è costituito da una parte dichiarativa e da una parte esecutivaLa parte dichiarativa …La parte esecutiva è costituita da una sequenza di istruzioniUn’istruzione può essere semplice o composta….

106

• Un messaggio di posta elettronica è costituito da una testata eda un corpoLa testata contiene indirizzo, ….

• …

• In generale questo tipo di regole linguistiche descrive un “oggetto principale” (libro, programma, messaggio, protocollo, ….) come una sequenza di “oggetti componenti” (soggetti, testate, parti dichiarative, …). Ognuno di questi viene poi “raffinato” rimpiazzandoli con altri oggetti più dettagliati e così via finche` non si giunge ad una sequenza di elementi base (bit,caratteri, …)Le varie riscritture possono presentare delle alternative: un soggetto può essere un nome o un pronome o altro, un’istruzione può essere di assegnamento o di I/O, ...

107

La definizione formale di grammatica

• G = <VN, VT, P, S>– VN : alfabeto o vocabolario nonterminale– VT : alfabeto o vocabolario terminale– V = VN ∪ VT

– S ∈ VN : elemento particolare di VN detto assioma o simbolo iniziale

– : insieme delle regole di riscrittura, o produzioni sintatiche.

*VVP N ×⊆ +

}{ scriveremo comoditàper },{ βαβα →=><= PP

108

Esempio

• VN = {S, A, B, C, D}• VT = {a,b,c}• S• P = {S → AB, BA → cCD, CBS → ab, A → ε}

109

Relazione di derivazione immediata

><∈→∧==

↔∈∈⇒ +

3122

22321321

*

, contesto nel come riscrive si ,

,,

ααβαβααβαβααα

βαβα

Pa

VV

Rispetto alla grammatica precedente:

aaBAS ⇒ aacCdS

Definiamo poi come al solito la chiusura riflessiva etransitiva di ⇒: ⇒*

110

Linguaggio generato da una grammatica

}|{)(*

* xSVxxGL T ⇒∧∈=

Consiste di tutte le stringhe costituite da soli simboli terminali derivabili (in numero qualsiasi di passi) da S

111

Primo esempio

0.},{)(:azionegeneralizz facile una Mediante

000

0iderivazion Alcune

}0,,,,{,},0,,{},,,{

*1

1

bbaaGL

aabbaabbSaabBaaSaASbbbbSbBSaaaaSaAS

S

SbSBbBSaSAaASPSPbaBASG

=

⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒

⇒

→→→→→=>=<

112

Secondo esempio

}0|{)(otteniamo con osostituiam Se

}1|{)(:azionegeneralizz facile una Mediante

iderivazion Alcune),per oneabbreviazi(}|{

,},,{},{

2

2

2

≥=→→

≥=

⇒⇒⇒⇒⇒

⇒

→→→=>=<

nbaGLSabS

nbaGL

aaabbbaaSbbaSbSaabbaSbS

abS

abSaSbSabaSbSPSPbaSG

nn

nn

ε

113

Terzo esempio

...

},,,,,,{

*

*

↓⇒⇒⇒⇒⇒

⇒⇒⇒⇒⇒⇒⇒⇒⇒

↓⇒⇒⇒⇒

⇒⇒⇒⇒

→→→→→→→

aaaCCbcaaaCCbDcaaaCCBDcaaaCCCDaaaACCCDS

aabbccaabbDccaabBDccaabCDcaaBCDcaaCBDcaaCCDaaACCDaACDSaaCCaaCCDaaACCDaACDS

abcaBDcaCDaACDS

DBCCBBDcCDbBAaACAaACDS εε

114

Alcune domande “naturali”

• Quale utilità pratica delle grammatiche (oltre ai“divertimenti” con {anbn}?)

• Quali linguaggi si possono ottenere con legrammatiche?

• Che relazioni esistono tra grammatiche e automi (omeglio tra i linguaggi generati dalle grammatiche e ilinguaggi riconosciuti dagli automi?

115

Alcune risposte

• Definizione della sintassi dei linguaggi diprogrammazione

• Applicazioni duali rispetto a quelle degli automi• Esempio più semplice: la compilazione dei linguaggi

(non solo di programmazione): la grammatica definisce il linguaggio; l’automa lo riconosce e traduce.

• In modo un po’ più sistematico:

116

Classi di grammatiche

• Grammatiche non-contestuali (context-free):– ∀ α → β ∈ P, |α| = 1, cioe` α è un elemento di VN.– Non-contestuale perché la riscrittura di α non dipende dal

contesto in cui si trova.– Sono di fatto la stessa cosa della BNF usata per definire la

sintassi dei linguaggi di programmazione (quindi vanno beneper definire certi meccanismi sintattici tipici dei linguaggi diprogrammazione e naturali … ma non tutti)

– Le G1 e G2 precedenti sono non-contestuali, non così la G3.

117

• Grammatiche regolari:– ∀ α → β ∈ P, |α| = 1, β ∈ VN . VT ∪ VT.– Le grammatiche regolari sono anche non-contestuali, ma non

viceversa– La G1 precedente è regolare, ma non la G2.

Relazioni tra grammatiche e linguaggi

G generali

G non-contestuali (GNC)

G regolari (GR)

118

Se ne deduce immediatamente che:

LR ⊆ LNC ⊆ LGen

Ma i contenimenti sono stretti?

La risposta dal confronto con gli automi

119Relazioni tra grammatiche e automi

(senza troppe sorprese)

• GR equivalenti agli FSA– Dato un FSA A, poniamo VN = Q, VT = I, S = <q0>, e,

per ogni δ(q, i) = q’ poniamo <q>→ i<q’>inoltre se q’∈ F, aggiungiamo <q> → i

– E` intuitivo (facile induzione) che δ∗ (q, x) = q’ se e solo se <q> ⇒* x<q’>

– Viceversa:– Data una GR, poniamo Q = VN∪ {qF}, I = VT, <q0> = S, F = {qF} e,

per ogni A→ bC poniamo δ(A,b) = C per ogni A→ b poniamo δ(A,b) = qF

NB: L’FSA così ottenuto è nondeterministico: molto più comodo!

120

• GNC equivalenti a AP (ND!)

giustificazione intuitiva (senza dimostrazione:la dimostrazione costituisce il “cuore” della costruzionedi un compilatore):

121

aabbaSbS ⇒⇒a a b b

S

a a b b

bSa

a a b b

bS

Z0 Z0 Z0

a a b b a a b b a a b b

bba

Z0bb

Z0 Z0

122

Ggen equivalenti alle MT

• Data G costruiamo (a grandi linee) una MT ND (!), M,che accetti L(G):– M ha un nastro di memoria– La stringa di ingresso x si trova nel nastro di ingresso– Il nastro di memoria viene inizializzato con S (meglio: Z0S)– Il nastro di memoria (in generale esso conterrà una stringa α,

α ∈ V*) viene scandito alla ricerca di una parte sinistra diqualche produzione di P

– Quando se ne trova una -non necessariamente la prima,operando una scelta ND- essa viene sostituita dalla corrispondente parte destra (se ve n’è più d’una si operaancora nondeterministicamente)

123

– In tal modo:><−−><=↔⇒ βαβα 00 ,*|, ZqZqc ss

Se e quando sul nastro si trova una stringa y ∈ VT*, la si confronta con

x. Se coincidono x viene accettata, altrimenti questa particolare sequenza di mosse non porta all’accettazione.

Si noti che:•L’uso del ND facilita molto la costruzione ma non è essenziale

•E` invece essenziale -e, vedremo, ineluttabile- il fatto che, se x ∉ L(G), M potrebbe“tentare infinite strade”, alcune delle quali anche non terminanti, senza poter concludere che x ∈ L(G) (giustamente), ma neanche il contrario.Infatti la definizione di accettazione richiede che M giunga in una configurazione diaccettazione se e solo se x ∈ L, ma non richiede che M termini la computazione (in uno stato negativo) se x ∉ L

•Tornano in ballo il problema-complemento e l’asimmetria tra risolvere un problemain maniera positiva o in maniera negativa.

124

• Data M (per comodità e senza perdere generalità, a nastro singolo) costruiamo (a grandi linee) una G, che generi L(M):– In primo luogo G genera tutte le stringhe del tipo

x$X, x ∈ VT*, X essendo una “copia di x” costituita da

caratteri nonterminali (ad esempio, per x = aba, x$X = aba$ABA)L’obiettivo è di ricavare da x$X una derivazione x$X ⇒* x se e solo se x è accettata da M.

– L’idea base è di simulare ogni mossa di M mediante una derivazione immediata di G:

125

– Rappresento la configurazione

q

α A βCB

– Mediante la stringa (i casi particolari sono lasciati in esercizio):$αBqACβ

– Se è definita:• δ(q,A) = <q’, A’, R) si definisce in G la produzione qA → A’q’• δ(q,A) = <q’, A’, S) si definisce in G la produzione qA → q’ A’• δ(q,A) = <q’, A’, L) si definisce in G la produzione BqA → q’ BA’

∀ B dell’alfabeto di M (si ricordi che M è a nastro singolo e quindi ha un soloalfabeto per ingresso, memoria e uscita)

126

– In tal modo:

q

α A βCB α A’ βCB

q’

– Se e solo se: x$αBqACβ ⇒ x$αBA’q’Cβ, ecc.– Aggiungo infine produzioni che permettano a G di derivare

da x$αBqFACβ la sola x se - e solo se- M giunge a una configurazione di accettazione (αBqFACβ), cancellando tutto ciò che si trova a destra di $, $ compreso.

127

L’uso delle formule logiche come formalismo descrittivo

• Logica: formalismo “universale” (molto vicino allinguaggio naturale)

• Applicabile a contesti molto vari (non solo informatici) (del resto il confine tra computer engineering e system engineering è molto labile)

• Sulla logica sono basati molti formalismi applicativi(dai linguaggi di programmazione a quelli di specifica)

128

1. La logica per definire linguaggi

• In realtà l’abbiamo già fatto:

"." elementare operazione di) (simbolo del base sulla).00(

formula dalla definita è operazionel' voltasua a dove)1(

ordineprim' del formula della oneabbreviaziun' che ènon altro }1|{

1 xxxnxnnx

baxnnLxnba

nnn

n

nn

nn

−=→>∧=→=∀

=∧≥∃↔∈≥

ε

129

• Similmente L1 = a*b* è definita da:

• Posto L2 = b*c* e definito in maniera simile• L3 = a*b* c* (= L1 L2) è definito anche come:

• L4 = {x|#xa = #xb} con #xa definita da:

)()()( 111 LyybxyLyayxyxLx ∈∧=∃∨∈∧=∃∨=↔∈ ε

)))(())((()()(

1332

213

LyLyycxLyLyayxyLxLxLx

∈∨∈∧=∨∈∨∈∧=∃∨∈∨∈↔∈

aaaaa yxbyxyxayxxx ##1##0# =→=∧+=→=∧=→= ε

(con quantificazione implicita ∀ x ∀ y)

130

2. La logica per definire proprietà dei programmi

• Specifica di un algoritmo di ricerca:La variabile logica found deve essere vera se e solo se esiste un elemento dell’array a, di n elementi, uguale all’elemento cercato x:

• Specifica di un algoritmo di inversione di un array:

)][1( xianiifound =∧≤≤∃↔

]1[][)1( +−=→≤≤∀ inaibnii

131

Più in generale• {Precondizione: Pre}

Programma - o frammento di programma- P• {Postcondizione: Post}

Se vale Pre prima dell’esecuzione di P si vuole che P sia tale da far valerePost dopo la sua esecuzione:

• Ricerca in un array ordinato:

NB: ciò non significa affatto che P debba essere un algoritmo di ricerca binaria. Significa solo che chi lo realizza può sfruttare il fatto che a sia ordinato prima dell’esecuzione di P. Un normale algoritmo di ricerca sequenziale sarebbe corretto rispetto a questa specifica; al contrario unalgoritmo di ricerca binaria non sarebbe corretto rispetto ad una specifica che avesse come precondizione semplicemente True.

)}][1({

]}1[][)1({

xianiifoundP

iaianii

=∧≤≤∃↔

+≤→≤≤∀

132

• Ordinamento di un array di n elementi senza ripetizioni:

E` una specifica “adeguata”?(Pensiamo all’analogia “specifica = contratto”)

]}1[][)1({

])}[][11(,{

+≤→≤≤∀

=∧≠∧≤≤∧≤≤¬∃

iaianiiORD

jaiajinjniji

133

]))}[][()1(()1(]))[][()1(()1(

]1[][)1({

]}[][)1(])[][11(,{

jbianiinjjjbianjjnii

iaianiiORD

ibianiijaiajininiji

=∧≤≤∃→≤≤∀∧=∧≤≤∃→≤≤∀

∧+≤→<≤∀

=→≤≤∀∧=∧≠∧≤≤∧≤≤¬∃

• E se eliminiamo la prima riga della precondizione la specifica è ancora valida?

• Siamo sicuri che il problema dell’ordinamento venga sempre inteso alla stessa maniera, sia che si tratti di ordinare un array o una lista o un file?

• In realtà anche un concetto ben noto come l’ordinamento è esposto aimprecisioni ed equivoci nell’uso informale del termine

• Pensiamo a requisiti del tipo “vogliamo automatizzare il rilascio di certificati, o la gestione dei cc bancari”

134

3. La logica per la specifica di proprietà di sistemi

• “Se premo il pulsante si accende la luce entro ∆ istanti”:– PB(t): Predicato che indica la pressione del pulsante all’istante t– LO(t): Predicato che indica che all’istante t la luce è accesa

)))()(()(( 111 tLOtttttPBt ∧∆+≤≤∃→∀

In realtà una specifica siffatta lascia molto a desiderare rispetto aquanto normalmente si chiede ad un pulsante di accensione della luce.

Scendiamo in qualche dettaglio

135

• Focalizziamo l’attenzione su un classico “pulsante a tempo” per la luce (seeccita di più la fantasia: un allarme e/o chiusura a tempo per cassaforti)

L_On

L_Off L_Off

t+kP_B(t)

))(_)(())(_)(()(_(

222

111

tOffLtktttOnLktttttBPt

→≤+∀∧→+<≤∀→∀

• In realtà ci sono ancora molte cose che non vanno …un po’ di caccia all’errore ...

136

Proviamo questa:

L_On

L_Off L_Off

t+kP_B(t)

)(_)))(_)(()(_(,

))(_))(_)(())(_)(_((

454535343

111

tOffLtBPtttttOffLtt

ktOffLtOnLktttttOffLtBPt

→¬→≤≤∀∧∀∧

+∧→+<≤∀→∧∀

137

Un approccio un po’ più sistematico (utile soprattutto per modelli a tempo continuo)

• Event_E: notazione abbreviata per l’assioma seguente:

)))()(()(( 11111 tEttttttttEt ¬→+<<∨<<−∀∃→∀ δδδ

t

E

• Up_to_now_S(t): notazione abbreviata per l’assioma seguente:

0) :o(sottintes ))()(( 111 >→<<−∀∃ δδδ tStttt

• From_now_on_S(t): notazione abbreviata per l’assioma seguente:

))()(( 111 tStttt →+<≤∀∃ δδ

138

Tornando al nostro timer:L_On

L_Off L_Off

t+kP_B(t)

)(_)))(_)(()(_(,))(_))(_)((

))(____)(_((_

le)(discutibi ))(_)(_(

454535343

111

tOffLtBPtttttOffLttktOffLtOnLktttt

tOffLnowtoUptBPtBEvent_P

tOffLtOnLt

→¬→≤≤∀∧∀∧+∧→+<≤∀

→∧∀∧∧¬↔∀

139

Variazioni sul tema:

• Pulsante di spegnimento• Mantenimento luce accesa mediante pressione durante

l’accensione• Apertura e chiusura tende/paratoie/finestrini auto, …

– Mantenimento pressione pulsanti– Interruzione o non interruzione movimento in corso– …..

• Generalità e sistematicità dell’approccio

• Verso metodi e linguaggi di specifica

140

Dalla specifica alla prova: un cenno

• Dopo aver specificato i requisiti di un algoritmo (e.g., di ordinamento) e dopo aver costruito un tale algoritmo, occorre verificare la correttezza del medesimo:se ho a disposizione un modello matematico (e.g., un’assiomatizzazione) dell’implementazione costruita, in linea di principio posso ottenere la prova di correttezza come una dimostrazione di teorema.

• Similmente a livello di sistema ...

141

Consideriamo un passaggio a livello (ultra-semplificato)

Ar En Ex

d l

Un solo binario e una sola direzione.Formalizzazione relativa al passaggio di un solo trenoAbbassamento ed innalzamento delle sbarre istantanei.

•Event_Ar

•Event_En

•Event_Ex

142

Dinamica del treno:

)))()(())()(()(()))()(()(()))()(()((

)))()(())()(()((

)()()()()(

222111

21max11

min1111

max222211min11

minmax

maxmin

max4

min3

max2

min1

tttExttttEnttIntttttArttExt

ttttArttEntttttExtttttEnttArt

Vld

Vd

Vl

Vl

Vld

Vd

≤∧¬∃∧≤∧∃↔∀∧−≤≤−∧∃→∀∧−≤≤−∧∃→∀

∧+≤≤+∧∃∧+≤≤+∧∃→∀

∧+=∧=∧=∧=∧+=∧=

δδδδ

δδδδ

δδδδδδ

“Progetto” del passaggio a livello

))()(()))()(()(()))()(()((

1min1max1

1max1min1

tUptDownttArtttttDownttDowntttttArt

¬↔∀∧∧−≤≤−∃→∀∧→+≤≤+∀→∀

δδδδ

Specifica del requisito di sicurezza:))()(( tDowntInt →∀

A questo punto il requisito può (e dovrebbe) essere dimostratocome teorema derivato dalla formalizzazione del sistema(controllore/controllato) … in corsi successivi

143

Un’applicazione pratica di modelli informatici

• Il problema della sicurezza e gli attacchi degli hackers• Internet e la (in)sicurezza distribuita• Alcuni esempi di attacchi:

– Spoofing: x si finge y nei confronti di z (spesso funzionale ad ulteriori attacchi)

– Half-open TCP (denial of service): x (o un insieme di hosts) manda(no) molte richieste di collegamento a y senza mandare l’ack finale: y lancia n processi che rimangono sospesi e dopo un po’ collassa.

– Smurf: x manda “broadcast” ICMP echo request (ping) a n hosts con indirizzo spoofed (y): y viene inondato da echo reply a collassa.

– ...– Categorizzazione ed analisi degli attacchi ... fuori dagli scopi di questa

presentazione.

144

• Gli attacchi in rete sono un po’ come i virus: ne vengono generati in continuazione di nuovi (anche se spesso secondo schemi molto ripetitivi) e occorre far fronte ad essi spesso anche in “tempo reale”.

• Gli IDS (intrusion detection system) –analoghi agli antivirus- sono uno strumento per rilevare, controllare, reagire agli attacchi.

145

Architettura –semplificata- di un IDS “attuale”

Internet Gateway

LAN

Security administrator

: host

: sensore

146

Difetti dell’attuale architettura:

• I sensori individuano solo certi particolari eventi (ad esempio un messaggio di provenienza x e destinazione y). Il grosso dell’analisi (capire se un messaggio è sintomo di un attacco) sta all’operatore e alla sua esperienza.

• Il traffico è spesso enorme e incontrollabile da operatore umano almeno in tempo reale

• Gli attacchi sono in continua evoluzione (come i virus) e occorre adattare l’IDS ad ogni nuovo attacco in tempi brevi e “on line”

• ...

147

Un’architettura più avanzata:

• L’IDS è in larga parte automatizzato nelle sue funzioni principali:– Sensori “intelligenti”– Struttura gerarchica del sistema (metasensori)– L’operatore diventa principalmente un progettista/gestore

dell’IDS– La maggior automatizzazione permette anche una capacità di

reazione in real-time e di riconfigurazione dinamica (e.g. caricare un nuovo scenario (descrizione di un attacco) su un sensore; ridistribuire i carichi e i compiti assegnati ai vari sensori, ...)

– ...

148

Per ottenere tutto ciò:

• Occorre –tra l’altro- un linguaggio/modello universale per descrivere e interpretare gli attacchi: STATL

• STATL sintetizza il concetto di macchina astratta a stati (non finiti!) e di descrizione di condizioni ed eventi tramite un linguaggio logico.

• Tanto per dare un’idea ... senza pretesa di approfondimenti:

149

Lo scenario IP spoofing

Message m in [IPDatagram d] {i_s, i_v}|

d.dst == a_v and d.src == a_z and isFirst (m.d);

s2s1

Host spoofer in Network.hosts,

Interface i_s in spoofer.interfaces;

Host victim in Network.Hosts | victim != spoofer;

Interface i_v in victim.interfaces;

IPAddress a_v in i_v.ipAddresses;

IPAddress a_z in Network.ipAddresses |

Not spoofer.ipAddresses.contains (a_z)

Un messaggio m a livello link appartiene a una sequenza di messaggi generata da un datagramma IP d tra i_s e i_v. d ha a_v come indirizzo IP destinazione (la vittima) e a_z come sorgente (l’indirizzo contraffatto). m è il primo messaggio della sequenza. a_z non è un indirizzo IP della sorgente del messaggio.

150

Ad esempio:

cameron

i0

i1

i2

i3

i4

L1 L2

lucas

coppola

gilliam

Se cameron inganna lucas spacciandosi per gilliam viene generata la sequenza di messaggi <i4,i3,<a1,a0>>,<i2,i0,<a1,a0>>, il primo dei quali soddisfa lo scenario precedente.

Il sensore altro non è che un interprete della macchina astratta descritta dallo scenario STATL.

Il sensore posto sul link L2 individua l’attacco.

151

Osservazione:

In realtà per individuare tutti i possibili attacchi IP-spoofing occorrerebbe, nel caso generale, integrare l’informazione proveniente dai vari sensori generando ulteriore traffico sulla rete.

Se tale overhead viene ritenuto eccessivo si può ricorrere a una condizione più debole: condizione che garantisce l’esistenza di uno spoofing ma non sempre è verificata per tutti gli spoofing:

Un messaggio <ix,iy,<az,av>> si trova in un link tra ix e iyche non appartiene a nessun cammino tra az e av .

Ma il nostro scopo qui non è imparare a progettare IDS ma constatare che STATL è un modello ricavato combinando alcuni modelli base studiati in precedenza.

152

Un ulteriore esempio: half-open TCPL’attaccante manda un messaggio SYN alla vittima e non manda l’ack finale che completa il collegamento: con molte di queste connessioni incomplete –magari provenienti da host diversi- vengono consumate le risorse della vittima che collassa.

s0 s1s2

SYN

RST

ACK

Timed-out

153

• L’attaccante manda un segmento TCP SYN per chiedere una connessione.

• Ciò fa scattare la transizione SYN che registra indirizzi e porte di attaccante e vittima e fa partire un timer.

• Se il server chiude la connessione con un reset o il client manda l’ack allora l’attacco è annullato o non era un attacco (rispettivamente).

• Se scade il timeout l’attacco viene confermato e sgnalato a chi di dovere (sensore di livello superiore o operatore)

• Tutto ciò è formalizzato nel modo seguente:

154

// Half-open TCP - produce a synthetic event for every TCP

// handshake timed out in half-open state.

use tcpip, netstat;

scenario halfopen_tcp ( int timeout )

{

timer t0;

u_int32 victim_addr;

u_int16 victim_port;

u_int32 attacker_addr;

u_int16 attacker_port;

timeval start;

155/************************ STATES ************************/

initial

state s0 { }

state s1

{ timer_start(t0, timeout, 0); }

/* final state - generate synthetic event */

state s2

{

halfopen_tcp_event e =

halfopentcp_event(attacker_addr,

attacker_port,

victim_addr,

victim_port,

start);

enq_event(e,halfopen_tcp_event_ID,start);

}

156

/*********************** TRANSITIONS ***********************/

transition SYN (s0->s1) nonconsuming

{

[IP_EVENT ip [TCP_EVENT tcp]] :

(tcp.tcp_header.th_flags & TH_SYN) &&

!(tcp.tcp_header.th_flags & TH_ACK)

{

victim_addr = ip.ip_header.ip_dst;

victim_port = tcp.tcp_header.th_dport;

attacker_addr = ip.ip_header.ip_src;

attacker_port = tcp.tcp_header.th_sport;

start = ip.time;

}

}

157

/*********************** TRANSITIONS ***********************/

transition ACK (s1->s0) consuming

{

[IP_EVENT ip [TCP_EVENT tcp]] :

(ip.ip_header.ip_dst == victim_addr) &&

(tcp.tcp_header.th_dport == victim_port) &&

(ip.ip_header.ip_src == attacker_addr) &&

(tcp.tcp_header.th_sport == attacker_port)&&

!(tcp.tcp_header.th_flags & TH_SYN) &&

(tcp.tcp_header.th_flags & TH_ACK)

}

158

/*********************** TRANSITIONS ***********************/

transition RST (s1->s0) consuming

{

[IP ip [TCP tcp]] :

(ip.ip_header.ip_src == victim_addr) &&

(tcp.tcp_header.th_sport == victim_port) &&

(ip.ip_header.ip_dst == attacker_addr) &&

(tcp.tcp_header.th_dport == attacker_port) &&

(tcp.tcp_header.th_flags & TH_RST)

}

transition conn_timed_out (s1->s2) consuming

{

[timer t0]

}

159

In conclusione

• In questa maniera la progettazione/gestione di un IDS diventa un problema di:– Definizione di un nuovo scenario in termini di STATL– “Compilazione” dello scenario in un interprete da assegnare

a un sensore– Riconfigurazione dinamica dell’IDS

• Si ottiene quindi:• Massima generalità, flessibilità, dinamicità ed

efficienza (reazione in tempo reale)

160

Qualche osservazione conclusiva (con un pizzico di pepe) sull’importanza dell’attività di modellizzazione

• Estrapoliamo da:– Timer della luce– Passaggio a livello– Intrusion detection– …

• a– Vicenda Therac 25– Ariane 5– Sistema di gestione conferenze– Riordino del Politecnico– ….

• Siamo proprio convinti che un po’ di sana teoria non serva alla pratica?

161

Teoria della computazione

• Quali problemi sappiamo risolvere– Con quali macchine– In assoluto

• A prima vista la domanda può sembrare troppo generale:– Che cosa intendiamo per problema?

Un calcolo matematico; una decisione di un’assemblea di condominio; il prelievo di contante dal Bancomat; …?

– Quante e quali macchine astratte dobbiamo considerare?– Che significa saper risolvere “in assoluto” un problema:

Pinco può essere più capace di pallino;Se non so risolvere un problema con un mezzo potrei riuscire a risolverlo con un altro.

162

In realtà siamo già in grado di inquadrare per bene il tema pur nella sua generalità

• Ricordiamo in primis che il concetto di linguaggio ci permette di formalizzare qualsiasi “problema informatico” (non quello di conquistare il cuore di un/a ragazza/o …):x ∈ L?y = τ(x)In realtà anche le due formulazioni di cui sopra possono essere ricondotte l’una all’altra:

– Se ho una macchina che sa risolvere il problema y = τ(x) e voglio usarla per risolvere un problema x ∈ L?, mi basta definire τ(x) = 1 se x ∈ L, τ(x) = 0 se x ∉L.

– Viceversa, se ho una macchina che sa risolvere il problema x ∈ L?, posso definire il linguaggiodopodiché, fissato un certo x, enumero tutte le possibili stringhe y sull’alfabeto di uscita e per ognuna di esse domando alla machina se x ∈ Lτ: prima o poi, se τ(x) è definita, troverò quella per cui la macchina risponde positivamente: quella è la y cercata (ricordiamo il gioco di indovinare un oggetto formulando domande e ottenendo risposte “binarie”).Procedimento forse “lunghetto” ma in questo momento la lunghezza del calcolo non ci interessa.

)}(|${ xyyxL ττ ==

163

• Quanto alla macchina di calcolo … effettivamente ce n’è una miriade, oltre quelle che conosciamo; e ben di più se ne possonoinventare al massimo potrei ambire a risultati del tipo{anbn|n > 0} può essere riconosciuto da un AP e da una MT ma non da un

FSA.• In realtà, a ben pensare, abbiamo già osservato che non è poi così facile

“superare” la MT: aggiungere nastri, testine, nondeterminismo, … non produce aumento di potenza (nel senso dei linguaggi riconoscibili); non è poi così difficile far fare alla MT ciò che fa un normale calcolatore: basta simulare la memoria dell’uno con quella dell’altra (o viceversa) (torneremo su questo tema in maniera meno ovvia quando ci interesserà esaminare anche il costo delle computazioni)

con una generalizzazione potente e audace:

164

Tesi di Church (e Turing e altri):Anni 30!!

• Non esiste meccanismo di calcolo automatico superiore alla MT o ai formalismi ad essa equivalenti.Fin qui potrebbe essere un Teorema di Church (da aggiornare ogni volta che qualcuno si sveglia la mattina con un nuovo modello di calcolo)

• Nessun algoritmo, indipendentemente dallo strumento utilizzato per implementarlo, può risolvere problemi che non siano risolvibili dalla MT: la MT è il calcolatore più potente che abbiamo e che potremo mai avere!

• Occhio a certe affermazioni recenti di certa stampa divulgativa.• Allora è ben posta la domanda: “Quali sono i problemi risolvibili

algoritmicamente o automaticamente che dir si voglia?”:Gli stessi risolvibili dalla semplicissima MT!

165

E allora studiamo per bene le MT

• Esistono problemi che non si possono risolvere?• Come si fa a capirlo?

Le risposte che troveremo varranno anche per programmi C, Modula, transputer, ….

166

Primo fatto:

• Le MT sono algoritmicamente enumerabili• Enumerazione di un insieme S:• E: S N• Enumerazione algoritmica: E può essere calcolata

mediante un algoritmo … cioè mediante una MT• Enumerazione algoritmica di {a, b}*:• {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …}

• {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ….}

167

• Tanto per fissare le idee e per semplicità, senza perdere generalità alcuna:

• Fissiamo un alfabeto (unico) A (negli esempi |A| = 2, A = {0 (_),1})

• MT a nastro singolo• Ulteriori convenzioni seguiranno• Lasciando stare le MT a uno stato … osserviamo quelle a due

stati:0 1 0 1

q0 q0⊥ ⊥ ⊥ ⊥q1 q1⊥ ⊥ ⊥ <q0, 0, S>

MT1MT0

168

• Quante MT con due stati?δ: Q × A → Q × A × {R,L,S} … ∪ {⊥ }

• In generale: quante f: D → R?• |R||D|

• Con |Q| = 2, |A| = 2, (2.2.3+1)(2.2) = 134 MT a due stati• Mettiamo in ordine queste MT: {M0, M1, …M134-1 }• Poi mettiamo in ordine alla stessa maniera le (3.2.3+1)(3.2) MT

con 3 stati e così via.• Otteniamo un’enumerazione E: {MT} N• E è algoritmica o effettiva: pensiamo a scrivere un programma

C (ovvero una MT) che, dato n, costruisce la n-esima MT (adesempio una tabella che definisce δ) e viceversa, data una(tabella che descrive una) MT, dice in che posizione è: E(M).

• E(M): numero di Goedel di M, E: goedelizzazione.

169

• Ulteriore convenzione: visto che stiamo parlando di numeri, d’ora in avanti, e per un po’:

• Problema = calcolo di una funzione f: N → N• fy = funzione calcolata dalla y-esima MT• NB: fy(x) = ⊥ se My non si ferma quando riceve in

ingresso x• Aggiungiamo la convenzione fy(x) = ⊥ se e solo se My

non si ferma quando riceve in ingresso x:basta far sì che una qualsiasi MT se si fermasse in uno stato che non porta alla definizione di un valore significativo fy(x) si porti in un nuovo stato che la fa procedere all’infinito, ad esempio spostando la testina sempre a destra, senza più fermarsi (è solouna comodità)

170

Secondo fatto:

• Esiste una Macchina di Turing Universale (MTU): la MT che calcola la funzione g(y,x) = fy(x)

• Ad essere precisi la MTU così definita non sembra appartenere alla famiglia {My} perché fy è funzione di una variabile, mentre g è funzione di due variabili

• Però noi sappiamo che N × N ↔ N : ad esempio:

xyxyxyxd ++++=2

)1)((),(

4

6

3

1

0 2 5

171

• Possiamo codificare g(y,x) come una g^(n) = g(d-1(n))NB: d e d-1 sono computabili

• Schema di una MTU che calcola g^ (d’ora in poi per semplicità scriveremo direttamente g):– Dato n calcolo d-1(n) =<y,x>– Costruisco la tabella di My (calcolando E-1(y)) e la memorizzo nel nastro

della MTU:

$ q a q’ a’ S $ .. ..

- In un’altra porzione di nastro simulo la configurazione di My

# 0 1 q0 .. 1 1 1 0 #

NB: I simboli speciali #, $ e gli stati sono codificati come stringhe di 0 e 1

Alla fine MTU lascia sul nastro fy(x), se e solo se My termina lacomputazione su x

172

• La MT è un modello molto astratto e semplice di calcolatore

• Approfondendo l’analogia:• MT: calcolatore a programma cablato.

Una MT “normale” esegue sempre lo stesso algoritmo, calcola sempre la stessa funzione

• MTU: calcolatore a programma memorizzato:y = programmax = dati del programma

173

Torniamo alla domanda “quanti e quali problemi sono risolvibili algoritmicamente?”

• Quante e quali sono le funzioni fy: N → N ?• Cominciamo con il “Quante”:• {f: N → N } ⊇ {f: N → {0,1} } ⇒

| {f: N → N }| >= | {f: N → {0,1} }| = ℘ (N) = 2ℵ 0

• D’altro canto l’insieme {fy: N → N} è per definizione numerabile: NB: E: {My} ↔ N induce E^: N → {fy} non biunivoca(in molti casi fy = fz, con z ≠ y) ma basta per asserire

• |{fy: N → N}| = ℵ 0 < 2ℵ 0 ⇒• la “gran parte” delle funzioni (problemi) non è

calcolabile (risolvibile) algoritmicamente!!

174

E` proprio una grave perdita?• In realtà quanti sono i problemi definibili?• Per definire un problema usiamo una frase (stringa) di un qualche linguaggio:

– f(x) = x2

– “Il numero che moltiplicato per se stesso dà y”– …

• Ma un linguaggio è un sottoinsieme di A*, che è un insieme numerabile →• L’insieme dei problemi definibili è pure numerabile, come quello dei

problemi risolvibili (algoritmicamente).• Possiamo ancora sperare che coincidano

Certamente {Problemi risolvibili} ⊆ {Problemi definibili}(Una MT definisce una funzione, oltre a calcolarla)

∫=x

adzzgxf )()(

175

Passiamo allora alla domanda:“Quali sono i problemi risolvibili?”

• Il problema della terminazione del calcolo(molto “pratico”):– Costruisco un programma– Fornisco dei dati in ingresso– So che in generale il programma potrebbe non terminare

l’esecuzione (in gergo: “andare in loop”)– Posso determinare se questo fatto si verificherà?

• In termini -assolutamente equivalenti- di MT:– Data la funzione g(y,x) = 1 se fy(x) ≠⊥ , g(y,x) = 0 se fy(x) =⊥– Esiste una MT che calcola g?

176

Risposta: NO!

• Ecco perché il compilatore (un programma) non può segnalarci nella sua diagnostica che il programma che abbiamo scritto andrà in loop con certi dati (mentre può segnalarci se abbiamo dimenticato un end):

• Stabilire se un’espressione aritmetica è ben parentetizzata è un problema risolvibile (decidibile);

• Stabilire se un dato programma con un dato in ingresso andrà in loop è un problema irrisolvibile (indecidibile)algoritmicamente [ne vedremo molti altri: sono “molte” (anche in termini qualitativi) le cose che il calcolatorenon sa fare]

177

Dimostrazione• Sfrutta una tipica tecnica diagonale utilizzata anche nel teorema di Cantor

per dimostrare che ℵ 0 < 2ℵ 0

• Ipotesi assurda: g(y,x) = 1 se fy(x) ≠⊥ , g(y,x) = 0 se fy(x) =⊥computabile

• Allora anche h(x) = 1 se g(x,x) = 0 (fx(x) =⊥ ), ⊥ altrimenti (fx(x) ≠⊥ )

• è computabile(NB: ci siamo posti sulla diagonale y = x e abbiamo scambiato il si col no, poi abbiamo fatto sì che il no diventasse una nonterminazione (sempre fattibile)

• Se h è computabile h = fx0 per qualche x0.

• Domanda h(x0) = 1 o h(x0) =⊥ ?

178

• Supponiamo h(x0) = f x0(x0) = 1• Ciò significa g(x0,x0) = 0 ovvero f x0(x0) =⊥ :• Contraddizione • Allora supponiamo il contrario: h(x0) = f x0(x0) =⊥• Ciò significa g(x0,x0) = 1 ovvero f x0(x0) ≠⊥ :• Contraddizione in ambo i casi: QED

• Vedremo che “in conseguenza” di questa irrisolvibilità molti altri problemi risultano irrisolvibili.

• Per il momento:

179

• Un primo “corollario” dell’irrisolvibilità del Problema dell’halt della MT– La funzione h(x) = 1 se fx(x) ≠⊥ ; = 0 se fx(x) =⊥

non è calcolabile– In realtà, rigorosamente parlando, si tratta piuttosto di un lemma che di

un corollario.– Infatti esso costituisce il “cuore” della dimostrazione del teorema

precedente– Di per se stesso l’enunciato non significa molto– E’ però importante menzionarlo per sottolineare che il suo enunciato non

può essere ricavato come conseguenza immediata del teorema precedente (+generale):

– NB: in generale, se un problema è irrisolvibile, può darsi che un suo caso particolare diventi risolvibile (: vedremo esempi irrisolvibili per linguaggi qualsiasi, risolvibili per linguagi regolari); invece una sua generalizzazione è necessariamente pure irrisolvibile.Al contrario, se un problema è risolvibile, può darsi che una sua generalizzazione diventi irrisolvibile mentre una sua particolarizzazione rimane certamente risolvibile.

180Un altro importante problema indecidibile

• La funzione k(y) = 1 se fy è totale, ossia fy(x) ≠ ⊥ ∀ x∈ N; = 0 altrimentinon è calcolabile

• NB1: è un problema simile ma diverso dal precedente. Qui abbiamo una quantificazione rispetto a tutti i possibili dati in ingresso.In certi casi potrei essere in grado di stabilire ∀ x,se fy(x) ≠⊥ , senza perquesto poter rispondere alla domanda “fy è una funzione totale?”(Ovviamente se trovo un x tale che fy(x) =⊥ , posso concludere che fy non ètotale, ma se non lo trovo?).Viceversa, potrei essere in grado di concludere che fy non è totale eppure potrei non poter decidere se fy(x) ≠⊥ per un singolo x. (Certo, se invece concludessi che è totale fy …)

• Dal punto di vista dell’impatto pratico questo teorema è forse ancor piùsignificativo del precedente: dato un programma, voglio sapere se esso terminerà l’esecuzione per qualsiasi dato in ingresso o corre il rischio, per qualche dato, di andare in loop. Nel caso precedente, invece mi interessava sapere se un certo programma con certi dati avrebbe terminato o meno l’esecuzione.

181

Dimostrazione (non indispensabile ma utile)• Meccanismo standard: assurdo + diagonale, con qualche dettaglio tecnico in più.• Ipotesi assurda: k(y) = 1 se fy è totale, ossia fy(x) ≠ ⊥ ∀ x∈ N; altrimenti = 0

calcolabile, e, ovviamente, totale per definizione• Definisco allora g(x) = w = indice (numero di Goedel) della x-esima MT (in E)

che calcola una funzione totale.• Se k è calcolabile e totale, allora lo è anche g:

– calcolo k(0), k(1), …, sia w0 il primo valore tale che k(w0) = 1, allora pongo g(0) = w0;– procedendo pongo g(1) = w1, essendo w1 il secondo valore tale che k(w1) = 1; …– il procedimento è algoritmico; inoltre, essendo le funzioni totali infinite, g(x) è certo definita per

ogni x, ergo è totale.

• g è anche strettamente monotona: passando da x a x+1, wx+1 è certo > di wx;• quindi g-1 è una funzione, pure strettamente monotona, anche se non totale: g-1(w)

è definita solo se w è il numero di Goedel di una funzione totale.• Definisco ora (α) h(x) = fg(x)(x) + 1 = fw(x) + 1: fw è calcolabile e totale e quindi

anche h lo è ⇒• (β) h = fw0 per qualche w0; siccome h è totale, g-1(w0) ≠ ⊥ , poniamo g-1(w0) = x0

182

• Quanto vale h(x0) ?– h(x0) = fg(x0)(x0) + 1 = fw0(x0) + 1 (da (α))– h = fw0 → h(x0) = fw0(x0) (da (β))

• Contraddizione!

183

NB (molto critico): sapere che un problema è risolvibilenon vuol dire saperlo risolvere!

• In matematica spesso ottengo dimostrazioni non costruttive:dimostro che la soluzione di un problema esiste (ed è unica) ma non per questo fornisco un modo di calcolarla

• Nel nostro caso:– un problema è risolvibile se esiste una MT che lo risolve– per certi problemi posso arrivare alla conclusione che esiste una MT che li

risolve ma non per questo essere in grado di fornirla

• Cominciamo con un caso banale– Il “problema” consiste nel rispondere a una domanda la cui risposta è

necessariamente Sì o No:• E’ vero che il numero di molecole dell’universo è 1010101010

?• E’ vero che la “partita a scacchi perfetta” termina in parità?• (20 anni fa’ ...) E’ vero che ?)2|,,,( >∧=+∈∃¬ ywzxNwzyx yyy

• ….

184

• In questi casi so a priori che la risposta è Si o No anche se non so (sapevo)quale sia (fosse).

• La cosa stupisce un po’ meno se ricordiamo che Problema = funzione; risolvere un problema = calcolare una funzioneChe funzione associamo ai problemi di cui sopra?Codificando TRUE = 1; FALSE = 0, tutti i problemi sono espressi da una delle due funzioni: f1(x) = 1, ∀ x, f1(x) = 0, ∀ xEntrambe le funzioni sono banalmente calcolabili →Qualsiasi sia la risposta al problema essa è calcolabile ma nonnecessariamente nota.

• In maniera un po’ più astratta:g(10,20) = 1 se f10(20) ≠⊥ , g(10,20) = 0 se f10(20) =⊥g(100,200) = 1 se f100(200) ≠⊥ , g(100,200) = 0 se f100(200) =⊥g(7,28) = 1 se f7(28) ≠⊥ , g(7,28) = 0 se f7(28) =⊥

….sono tutti problemi risolvibili, anche se non è detto che noi ne conosciamo lasoluzione.

185

• Esaminiamo ora casi un po’ meno banali ma molto istruttivi:– f(x) = x-esima cifra dell’espansione decimale di π.

f è sicuramente calcolabile e conosciamo algoritmi (MT) che la calcolano– Basandosi sulla capacità di calcolare f (allo stato attuale non si hanno

altre fonti di conoscenza) investighiamo la calcolabilità dig(x) = 1 se in π ∃ esattamente x 5 consecutivi, 0 altrimentiCalcolando la sequenza {f(0) = 3, f(1) = 1, f(2) = 4, f(3) = 1, f(4) = 5, f(5) ≠ 5, …}Otteniamo g(1) = 1In generale il grafico di g sarà del tipo seguente:

1

0 1 3 x 5 y 9 10

186

– Per qualche valore di x potremmo scoprire che g(x) = 1,anzi, se g(x) = 1, prima o poi, pur di aver pazienza, lo scopriamo(approfondiremo questo fatto più avanti) ma che elementi abbiamo perconcludere, ad esempio, che g(100000000) = 0 se dopo aver calcolatof(1000000000000000) non abbiamo ancora trovato 100000000 5consecutivi?Allo stato attuale di conoscenze (personali), nessuno!

– Possiamo però escludere che sia vera la seguente congettura:Qualsiasi sia x, pur di espandere un numero sufficientemente grande dicifre di π, prima o poi si troveranno x 5 consecutivi ?

– Se essa fosse vera, ne ricaveremmo che g è la funzione costanteg(x) = 1 ∀ x e scopriremmo quindi anche che la sappiamo calcolare.

– In conclusione, allo stato attuale, non possiamo concludere né che g sia calcolabile, né che non lo sia.

187

• Consideriamo ora la seguente “lieve” modifica di g:h(x) = 1 se in π ∃ almeno x 5 consecutivi, 0 altrimentiOvviamente, se g(x) = 1 anche h(x) = 1;Osserviamo però che se per qualche x h(x) = 1, allora h(y) = 1 ∀ y ≤ x. Ciò significa che il grafico di h è di uno dei due tipiseguenti:– 1) (h(x) = 1 ∀ x)

– 2)

xxxh

xxxh

>∀=

≤∀=

0)(

1)(

x

188

• Quindi h appartiene sicuramente all’insieme delle funzioni

Si noti che ognuna delle funzioni di questo insieme ébanalmente calcolabile (fissato é immediato costruire una MTche calcola ; idem per )

• Dunque h è sicuramente calcolabile: esiste una MT che lacalcola

• Sappiamo calcolare h?Attualmente no: tra le infinite MT che calcolano le funzioni dell’insieme suddetto non sappiamo quale sia quella giusta!

}1)(|{}0)(1)(|{ xxhhxxxhxxxhh xxx ∀=∪>∀=∧≤∀=

xxh h

189Decidibilità e semidecidibilità

Ovvero:1/2 + 1/2 = 1

• Concentriamoci su problemi formulati in modo taleche la risposta sia di tipo binario:Problema = insieme S ⊆ N: x ∈ S?

• Funzione caratteristica di un insieme S:cS(x) = 1 se x ∈ S, cS(x) = 0 se x ∉ S

• Un insieme S è ricorsivo (o decidibile) se e solo se lasua funzione caratteristica è computabile (NB: cS ètotale per definizione).

190

• S è ricorsivamente enumerabile (RE) (o semidecidibile) se e solo se:– S è l’insieme vuoto– oppure– S è l’insieme immagine di una funzione totale e computabile:

da qui il termine “ricorsivamente (algoritmicamente) enumerabile”– possiamo spiegare in termini intuitivi anche l’attributo “semidecidibile”:

se x ∈ S, enumerando gli elementi di S prima o poi trovo x e sono ingrado di ottenere la risposta giusta (Sì) alla domanda;ma se x ∉ S?

– una conferma più formale ci viene dal seguente ...

),...}3(),2(),1(),0({

}),(|{

SSSS

Sg

ggggS

NyygxxISS

=⇒

∈===

191

Teorema• A) Se S è ricorsivo è anche RE

(decidibile è più che -non meno di- semidecidibile)• B) S è ricorsivo se e solo se S stesso e il suo

complemento S^ = N - S sono RE (due semidecidibilità fanno una decidibilità; ovvero quando rispondere No equivale a (è ugualmente difficile che) rispondere Sì (e quando invece …)

• Corollario: gli insiemi (linguaggi, problemi, …) decidibili sono chiusi rispetto al complemento.

• Dimostrazione:

192

A): S ricorsivo implica S RE• Se S è vuoto esso è RE per definizione!• Assumiamo allora S ≠ ∅ e indichiamo con cs la sua

funzione caratteristica:∃ k ∈ S, cioè cs(k) = 1

• Definiamo la funzione gs:gs(x) = x se cs(x) = 1, altrimenti gs(x) = k

• gs è totale, computabile e IgS = S• → S è RE• NB: dimostrazione non costruttiva:

sappiamo se S ≠ ∅ ? Sappiamo calcolare gs?Sappiamo solo che esiste gs se S ≠ ∅ : è quanto ci basta!

193B) S è ricorsivo se e solo se S e S^ = N - S sono RE • B.1.) S ricorsivo → S RE (parte A)• B.1.2) S ricorsivo → cS(x) (= 1 se x ∈ S, cS(x) = 0 se x ∉ S)

calcolabile → cS^(x) (= 0 se x ∈ S, cS(x) = 1 se x ∉ S)calcolabile → S^ ricorsivo → S^ RE

• B.2) S RE →S^ RE →Ma S∪ S^ = N, S∩S^ = ∅

perciò ∀ x ∈ N ,(x appartiene a una e una sola delle due enumerazioni) →Se costruisco l’enumerazione

sono sicuro di trovarvi qualsiasi x: a quel punto se trovo x in unposto dispari concludo x ∈ S, se lo trovo in posto pari concludo x ∈ S^. So quindi calcolare cS.

),...}3(),2(),1(),0({ SSSS ggggS =),...}3(),2(),1(),0({ ^^^^

^SSSS

ggggS =

))()(|()()(| ^^ zgxzgxzygxygxy SSSS=∧=∃¬∧=∨=∃

),...}3(),3(),2(),2(),1(),1(),0(),0({ ^^^^ SSSSSSSS gggggggg

194

Alcuni enunciati con importanti risvolti pratici• Abbia un generico insieme S le seguenti caratteristiche:

– i ∈ S → fi totale– f totale e computabile → ∃ i ∈ S | fi = f

• Allora S non è RE

• Ciò significa: non esiste un formalismo (RE: Automi, grammatiche, funzioni ricorsive, …) in grado di definire tutte e sole le funzioni calcolabili totali:I FSA, definiscono “funzioni totali” ma non tutte; le MT definiscono tutte lefunzioni calcolabili, ma anche quelle non totali; il C permette di programmare qualsiasi algoritmo, ma anche quelli che non terminano: esiste un sottoinsiemeRE del C che definisca solo i programmi che terminano? NO!Ad esempio l’insieme dei programmi i cui loop siano solo cicli for soggiacentia precise limitazioni può contenere solo programmi che terminano ma non tutti.

195

• Tentiamo un altro trucco per sbarazzarci delle scomode funzioni non totali (algoritmi che vanno in loop):– estendiamo una funzione, ad esempio arricchendo N con il

nuovo valore {⊥ }, oppure semplicemente attribuendo ad f un valore convenzionale quando f è indefinita.

– Matematicamente l’operazione è perfettamente sensata (infatti in matematica pura si presta poca attenzione alle funzioni parziali)

– il trucco non funziona:– Non esiste una funzione totale e computabile che sia

un’estensione della funzione computabile ma non totaleg(x) = {se fx(x) ≠⊥ allora fx(x) + 1, altrimenti ⊥ }

• Posso prendere una funzione parziale e farla diventare totale, manel farlo potrei perderne la computabilità: coperta corta!

196

• S è RE ↔– S = Dh, con h computabile e parziale: S = {x| h(x) ≠ ⊥ }

↔– S = Ig, con g computabile e parziale: S = {x| x = g(y), y ∈ N}

• Dimostrazione omessa (qui) ma usa una tecnica particolarmente utile e significativa (v. esercitazioni)

• Serve come Lemma per dimostrare che:• Esistono insiemi semidecidibili che non sono decidibili:• K = {x| fx(x) ≠ ⊥ } è semidecidibile perché K = Dh con

h(x) = fx(x). Però sappiamo anche che cK(x) (= 1 se fx(x) ≠⊥ , 0 altrimenti) non è computabile, → K non è decidibile

• Conclusione:

197

Insiemi ricorsivi

Insiemi

RE

P(N)

I contenimenti sono tutti stretti

Corollario: gli insiemi RE (i linguaggi riconosciuti dalle MT) non sono chiusi rispetto al complemento

198

• Il potentissimo teorema di Rice:• Sia F un insieme di funzioni computabili

L’insieme S de(gli indici di) MT che calcolano funzioni di F (S = {x| fx ∈ F}) è decidibile se e solo se F = ∅ o F è l’insieme di tutte le funzioni computabili

• → in tutti i casi non banali S non è decidibile!• →

– La correttezza di un programma: P risolve il problema specificato? (Mxcalcola la funzione costituente l’insieme {f}?)

– L’equivalenza tra due programmi (Mx calcola la funzione costituente l’insieme {fy}?)

– Un programma gode di una qualsiasi proprietà riferibile alla funzione da esso calcolata (funzione a valori pari, funzione con insieme immagine limitato, …)?

– …

• Sono solo alcuni tra gli innumerevoli esempi di problemi la cui indecidibilità discende banalmente dal teorema di Rice.

199Come facciamo, in pratica a stabilire se un problema è (semi)decidibile o no?

(ovviamente questo è a sua volta un problema indecidibile)

• Se troviamo un algoritmo che termina sempre → decidibile• Se troviamo un algoritmo che potrebbe non terminare ma

termina sempre se la risposta al problema è Sì → semidecidibile• Ma se riteniamo che il problema in questione sia non

(semi)decidibile, come facciamo a dimostrarlo?• Tentiamo di costruirci una nuova dimostrazione di tipo

diagonale ogni volta? … staremmo freschi!• In realtà abbiamo ora mezzi più comodi:• Un primo strumento potentissimo l’abbiamo già visto: il

teorema di Rice• Di fatto implicitamente abbiamo già usato più volte una tecnica

naturale e generalissima:

200

La riduzione di problemi

• Se ho un algoritmo per risolvere il problema P lo posso sfruttare per risolvere il problema P’:– Se so risolvere il problema della ricerca di un elemento in un

insieme posso costruire un algoritmo per risolvere il problema dell’intersezione tra due insiemi

– In generale se trovo un algoritmo che, data un’istanza di P’ ne costruisce la soluzione ricavandone un’istanza di P per il quale asua volta so ricavarne la soluzione, ho ridotto P’ a P.

– Formalmente:• Voglio risolvere x ∈ S?• So risolvere y ∈ S’• Se trovo una funzione t calcolabile e totale tale che x ∈ S ↔ t(x) ∈ S’

sono in grado di rispondere algoritmicamente alla domanda x ∈ S?

201• Il procedimento può funzionare anche al contrario:– Voglio sapere se posso risolvere x ∈ S?– So di non saper risolvere y ∈ S’ (S’ non è decidibile)– Se trovo una funzione t calcolabile e totale tale che y ∈ S’ ↔ t(y) ∈ S

ne concludo che x ∈ S? è non decidibile, altrimenti ne ricaverei laconseguenza assurda che anche S’ è decidibile

• In realtà abbiamo usato questo meccanismo già varie volte in forma implicita:– Dall’indecidibilità del problema dell’halt della MT abbiamo concluso in

generale l’indecidibilità del problema della terminazione del calcolo:• Ho una MT My un numero intero x un programma C, P e un file di ingresso f• Costruisco un programma C, P che simula My e memorizzo x in un file di

ingresso f • P termina la sua computazione su f se e solo se g(y,x) ≠ ⊥• Se sapessi decidere se P termina la sua computazione su f saprei risolvere anche

il problema dell’halt della MT.• NB: avremmo potuto ridimostrare in modo diretto l’indecidibilità della

terminazione dei programmi C enumerando i programmi e applicando la stessa tecnica diagonale … con un po’ più di dettagli notazionali.

202Un meccanismo abbastanza generale• E’ decidibile se durante l’esecuzione di un generico programma

P si acceda ad una variabile non inizializzata?– Supponiamo per assurdo che sia decidibile– Allora consideriamo il problema dell’halt e riduciamolo al problema

nuovo come segue:• Dato un generico P^ che riceve in ingresso generici dati D, costruisco un P

cosiffatto:begin var x, y: …

P^;y := x

endavendo cura di usare identificatori x e y che non sono usati in P^

• è chiaro che l’assegnamento y := x produce un accesso ad x che non èinizializzata perché x non compare in P^

• Quindi l’accesso ad una variabile non inizializzata accade in P se e solo se P^ termina.

– Allora se sapessi decidere il problema dell’ accesso ad una variabile non inizializzata, saprei decidere anche il problema della terminazione del calcolo, ciò che è assurdo.

203

• La stessa tecnica può essere applicata per dimostrare l’indecidibilità di molte altre tipiche proprietà dei programmi durante la loro esecuzione:– Indici di array fuori dai limiti– Divisione per 0– Compatibilità dinamica tra tipi– …– Tipici errori a run-time: a questo proposito ...

204

• Riprendiamo in considerazione gli esempi precedenti– l’halt della MT– la divisione per 0 e gli altri errori a run-time, …

• Sono non decidibili ma semidecidibili: se la MT si ferma, prima o poi lo scopro; se esiste un dato x di unprogramma P tale per cui P tenti a un certo punto dieseguire una divisione per 0 prima o poi lo scopro …

• Fermiamoci un momento e apriamo una parentesi:– come scopro il fatto precedente: se io comincio ad eseguire P

sul dato x e P non si ferma su x come faccio a scoprire che eseguendo P su y, P eseguirà una divisione per 0?

205

• In generale: Teorema (formulazione astratta dei vari casi concreti precedenti):– Il problema di stabilire se ∃ z| fx(z) ≠ ⊥ è semidecidibile– Schema di dimostrazione

• E’ chiaro che se cerco di calcolare fx(0) e trovo che è ≠ ⊥ sono a posto;• Però se la computazione di fx(0) non termina e fx(1) è ≠ ⊥ come posso scoprirlo?• Uso allora il seguente trucco (ancora una volta di sapore diagonale):

– Simulo 1 passo di computazione di fx(0): se mi fermo, ho chiuso positivamente;– in caso contrario simulo un passo di computazione di fx(1); – se ancora non mi sono fermato simulo 2 passi del calcolo di fx(0); successivamente 1

passo di fx(2); 2 di fx(1); 3 di fx(0); e così via secondo lo schema già adottato di figura:

In questa maniera se ∃ z| fx(z) ≠ ⊥ , prima o poi lo trovo perchéprima o poi simulerò abbastanza passi della computazione di fx(z) per farla arrestare.

206

• Chiudendo la parentesi:• abbiamo dunque un notevole numero di problemi (tipicamente gli errori a

run-time dei programmi) non decidibili ma semidecidibili.• Attenzione però: qual’è esattamente il problema semidecidibile:

– la presenza dell’errore (se c’è lo trovo)– non l’assenza!

• Ma, siccome si dà il caso che il complemento di un problema in RE - R nonsia neanche RE (altrimenti sarebbe anche decidibile),

• L’assenza di errori (ovvero la correttezza di un programma rispetto ad unerrore) non solo non è decidibile, ma non è neanche semidecidibile!

• Ne otteniamo quindi un modo sistematico per dimostrare che un problema non è RE: dimostrare che il suo complemento lo è (ovviamente non essendo decidibile).

207

La complessità del calcolo

• Non analisi di singoli algoritmi (si fa riferimento ai corsi di fondamenti)

• Non algoritmica avanzata (si rimanda a corsi successivi)

• Bensì:• Riesame critico del problema e dell’approccio• Ricerca di principi di validità generale• Costruire una capacità di inquadramento nel giusto

ambito di singoli problemi

208

La complessità come “raffinamento” della risolvibilità

• Non ci accontentiamo più di sapere se sappiamo risolvere (algoritmicamente) un problema ma vogliamo sapere quanto ci costa risolverlo

• Analisi critica del concetto di “costo” (e beneficio):– Costo di esecuzione (risorse fisiche necessarie), a sua volta diviso in:

• Tempo– di compilazione– di esecuzione

• Spazio– Costo di sviluppo– …– Valutazioni oggettive e soggettive, trade-off tra obiettivi contrastanti, …– … verso problematiche e approcci da Ingegneria del software– Qui ci si limita a concetti di costo oggettivi e formalizzabili: tipiche risorse:

memoria e tempo (di esecuzione)

209

Sarebbe bello partire come per la risolvibilità:

• Le domande che ci poniamo e le risposte che otterremo non dipendono dal modo con cui formuliamo il problema né dallo strumento usato (Tesi di Church).

• Però:– Fare la somma in unario è ben diverso dal fare la somma in

base k– Se uso la tecnica z ∈ per calcolare τ(x)

dovrò decidere un problema di appartenenza un numero anche illimitato di volte per risolvere il problema originario di traduzione

– E’ verosimile che cambiando calcolatore (o MT) non cambi il tempo di esecuzione? Evidentemente no, però...

)}(|${ xyyxL ττ ==

210

• Certo l’obiettivo è arduo o addirittura mal posto• Tuttavia alla fine riusciremo ad ottenere risultati di

notevole validità generale ….• … una sorta di “Tesi di Church della complessità”• Visto che per ora una Tesi di Church della complessità

non sussiste …

211

… cominciamo da un’analisi di complessità legata alle MT

• Complessità temporale: sia c0 = |-- c1 |-- c2 |-- c3 … |-- crTM(x) = r se la computazione termina in cr, altrimenti ∞

• Complessità spaziale: c0 = |-- c1 |-- c2 |-- c3 … |-- cr

SM(x) =

• NB: SM(x) ≤ k . TM(x) ∀ x

esima-i mossa alla j nastro del contenuto},...,1,max{1

==∑=

ij

k

jij ri αα

212

Un primo esempio: riconoscimento di {wcwR}Nastro di lettura

b c b b a

OC

a bNastro di memoria

Z0 A B B

TM(x) = |x| + 1 se x ∈ L

|w|+1 se x = wz, w = vucuR, v =sa, z = bp

|x| + 1 se x ∈ {a,b}*

…

SM(x) = |x| + 1 se x ∈ {a,b}*, |x|/2 + 1 se x ∈ L, ...

213

• Un po’ troppi dettagli, …• utili/necessari?

• Cerchiamo di semplificare e di andare al sodo:

• Complessità in f(x) → complessità in f(n), “dimensione dei dati in ingresso”:n = |x|, righe/colonne di una matrice, numero di record in un file, …Però in generale |x1| = |x2| ¬⇒ TM (|x1|) = TM (|x2|)(idem per SM) ---->

214

alfabetodell' àcardinalit ,)(

=∑

= kk

xT

nnx

M

• Scelta del caso pessimo:TM(n) = max{TM(x), |x| = n} (idem per SM(n) )

• Scelta del caso medio:

TM(n) =

• Noi adotteremo per lo più il caso pessimo:– ingegneristicamente più rilevante (per certe applicazioni)– matematicamente più semplice (a rigore il caso medio

dovrebbe tener conto di ipotesi probabilistiche sulla distribuzione dei dati: i nomi di una guida del telefono non sono equiprobabili)

215

• Uso della notazione Θ per valutare l’ordine di grandezza di una funzione (di complessità)

• f Θ g ↔• è una relazione di equivalenza ---->• Diremo che TM(n) è Θ(n), ….• (Dire che TM(n) è Θ(n) è come dire che TM(n) è

lineare?)

• Non solo l’uso dell’ordine di grandezza permette di evidenziare con facilità la parte più importante di una funzione di complessità, ma vedremo che in uncerto senso esso descrive anche la parte “indipendente dalla potenza di calcolo”

∞≠≠=∞→

cccngnf

n,0,

)()(lim

216

Torniamo all’esempio {wcwR}

• TM(n) è Θ(n), SM(n) è pure Θ(n)• Si può fare di meglio?• Per TM(n) difficile (in generale dovrò almeno leggere tutta la stringa)• Per SM(n):

Nastro di lettura

b c b b a

OC

Nastro di memoria: contiene icodificato in binario

a b

Z0 1 1

Memorizzo solo la posizione i del carattere da esaminare; poi sposto la testina di lettura in posizione i e n-i+1 e confronto i due caratteri letti ===>

217

• Ottengo:– SM(n): Θ(log(n))

ma – TM(n): Θ(n2.log (n)):

• ∀ i, • costruisco i in binario (in un nastro) (Θ(log(i) per implementare i := i+1);• copio i su un nastro ausiliario (j := i);• i volte:

– decremento j di 1 e sposto di 1 la testina nel nastro di ingresso (a partire dal centro) (Θ(log(i));

– quando j = 0 la testina è in posizione i-esima– (Θ(i .log(i));

– classico trade-off spazio-temporale• L’esempio ci spiega anche perché nella MT a k nastri la testina di ingresso può

muoversi nelle due direzioni: in caso contrario non ci sarebbero esempi significativi di complessità spaziale sublineare

218

A proposito di MT a k nastri ...

• Proviamo a cambiare modello di calcolo:– FSA hanno sempre SA(n) Θ(k) e TA(n) Θ(n), anzi TA(n) = n (macchine real-time

…);

– PDA hanno sempre SA(n) ≤ Θ(n) e TA(n) Θ(n); – MT a nastro singolo?

• Il riconoscimento di {wcwR} richiede in prima istanza Θ(n2), • La complessità spaziale non potrà mai essere < Θ(n)

(ciò fornisce un’ulteriore spiegazione della scelta della MT a k nastri come modello principale)• Si può fare meglio di Θ(n2)? NO: dimostrazione tecnicamente complessa come quasi sempre per

limiti inferiori di complessità che non siano banali.

– MT a nastro singolo più potenti dei PDA ma talvolta meno efficienti– E i calcolatori a’ la von Neumann?

Aspettiamo ancora un po’ ...

219

I teoremi di “accelerazione” lineare

• Se L è accettato da un MT M a k nastri con complessità SM(n), per ogni c > 0 si può costruire una MT M’ (a k nastri) con complessità SM’(n) < c. SM(n).

ar b1 b2ai bi cia1 a2 br c1 c2

b1... bi … br> <c1... ci … cr><a1... ai … ar> <

r.c ≥ 2

220

• Se L è accettato da un MT M a k nastri concomplessità SM(n), si può costruire una MT M’ a 1 nastro (non a nastro singolo) con complessità SM’(n) = SM(n).

• Se L è accettato da un MT M a k nastri concomplessità SM(n), per ogni c > 0 si può costruire unaMT M’ a 1 nastro con complessità SM’(n) < c. SM(n).

221

• Se L è accettato da un MT M a k nastri concomplessità TM(n), per ogni c > 0 si può costruire unaMT M’ (a k+1 nastri) con complessità TM’(n) = max{n+1, c. TM(n)}

• Schema di dimostrazione analogo a quello usato per la complessità spaziale. Però, con qualche dettaglio tecnico in più:– occorre prima leggere e tradurre tutto l’input (richiede n mosse)– ciò crea qualche problema all’interno della classe Θ(n)– nel caso pessimo occorrono 3 mosse per simulare almeno r + 1 mosse di

M

222

Conseguenze pratiche dei teoremi di accelerazione lineare• Lo schema di dimostrazione è valido per qualsiasi tipo di modello di calcolo:

anche per calcolatori reali:• significa aumentare il parallelismo fisico (da 16 bit a 32 a 64 …)• pur di aumentare la potenza di calcolo in termini di risorse disponibili si può

aumentare “a piacere” la velocità di esecuzione • però tale aumento di prestazioni rimane confinato nell’ambito di

miglioramenti al più lineari: non riesco a cambiare l’ordine di grandezza• miglioramenti di ordini di grandezza possono essere ottenuti solo cambiando

algoritmo e in modo non automatico:• per valori di n sufficientemente grandi ordinare una sequenza di n elementi

con il merge sort sarà sempre più efficiente che ordinarla mediante inserzione lineare o bubble-sort, anche se il primo algoritmo viene eseguito su una macchina di modesta “potenza” e il secondo da un supercalcolatore:

• l’intelligenza può superare di gran lunga la forza bruta!

223

Riprendiamo ora il confronto tra MT e calcolatori reali

• A prima vista il confronto è impari …:– per calcolare la somma di due numeri una MT impiega Θ(n)

(n è la lunghezza -della stringa di caratteri che codifica- i due numeri) mentre un calcolatore fornisce questa operazione come elementare (eseguita in un ciclo macchina)

– un calcolatore può accedere direttamente a una cella di memoria, mentre la MT ha accesso solo sequenziale:

• ad esempio, se cerchiamo di implementare la ricerca binaria mediante una MT otteniamo addirittura una complessità Θ(n.log(n)) > Θ(n)

• Non possiamo perciò accontentarci di valutazioni di complessità legate esclusivamente alle MT

224

Un modello molto astratto di calcolatore: la RAM

Nastro di letturaM[0]n

Programma (cablato)

Program counter Unità

aritmetica

AccumulatoreM[1]

M[3]M[2]

x

Nastro di scrittura

Ogni cella contiene un intero, non un carattere!

225

• Il repertorio istruzioni della RAM:

– LOAD [=, *] X M[0] := M[X], X, M[M[X]]– STORE [*] X M[X] := M[0], …– ADD … M[0] := M[0]+M[X], …– SUB, MULT, DIV– READ [*] X– WRITE [=, *] X– JUMP lab PC := b(lab)– JZ, JGZ, ... lab– HALT

226Un programma RAM che calcola la funzione is_prime(n) = if n is prime then 1 else 0

READ 1 Il valore di ingresso n è memorizzato nella cella M[1]LOAD= 1 Se n = 1, esso è banalmente primo ...SUB 1JZ YESLOAD= 2 M[2] è inizializzato a 2STORE 2

LOOP: LOAD 1 Se M [1] = M[2] allora n è primoSUB 2JZ YESLOAD 1 Se M [1] = (M[1]div M[2] ) * M[2] alloraDIV 2 M[2] è un divisore di M[1];MULT 2 quindi M[1] non è primoSUB 1JZ NOLOAD 2 M[2] è incrementato di 1 e il ciclo viene ripetutoADD= 1STORE 2JUMP LOOP

YES WRITE= 1HALT

NO WRITE= 0HALT

227

Quanto costa eseguire il programma di cui sopra mediante una RAM?

• Ovviamente:– SR(n) Θ(2)– TR(n) Θ(n)– (Attenzione però: che cos’è n?? Non è la lunghezza della stringa di ingresso!

Attenzione al parametro di “dimensione dei dati”!!)• Pure ovviamente:

– Riconoscimento di wcwR con• SR(n) Θ (n)• TR(n) Θ (n)

– Ricerca binaria con TR(n) Θ(log(n))– Ordinamento– …

• Però ...

228

Calcoliamo 22nusando una RAM (o macchina analoga)

• read n;• x := 2;• for i :=1 to n do x := x*x;• write x

• Ottengo ((2)2)2) … n volte ossia 22n

• Quale complessità temporale?• Θ(n)! (non Θ(n!))• Siamo proprio sicuri?!• In realtà occorrono almeno 2n bit solo per scrivere il risultato!

• L’analisi sembra decisamente irrealistica!

229Il problema sta nel fatto che la RAM (macchina di von Neumann) è un po’ troppo ...

astratta

• Una cella contenente un numero arbitrario = unità di memoria?• Un’operazione aritmetica = operazione elementare a costo unitario?• Ciò è corretto solo fino a quando la macchina reale (a 16, 32, 64, … bit)

corrisponde esttamente alla macchina astratta.• Altrimenti … doppia precisione ecc. ---> le operazioni relative non sono più

elementari e occorre programmarle ad hoc.• ---->• rifacciamo tutti gli algoritmi e le relative analisi di complessità in funzione

del livello di precisione (numero di bit) usati?• Concettualmente sì ma più comodamente:

• Criterio di costo logaritmico: basato su un’analisi “microscopica” (vedi “microcodice”) delle operazioni HW:

230

• Quanto costa copiare il numero i da una cella all’altra?: tante microoperazioni elementari quanti sono i bit necessari a codificare i:log(i)

• Quanto costa accedere alla cella di posizione i-esima?:l’apertura di log(i) “cancelli” di accesso ad altrettanti banchi di memoria

• Quanto costa eseguire l’operazione LOAD i?

• …• Con semplice e sistematica analisi si ottiene la seguente ...

231Tabella dei costi logaritmici della RAM

• LOAD= x l(x)• LOAD x l(x) + l(M[x])• LOAD* x l(x) + l(M[x]) + l(M[M[x]])• STORE x l(x) + l(M[0])• STORE * x l(x) + l(M[x]) + l(M[0])• ADD= x l(M[0]) + l(x)• ADD x l(M[0]) + l(x) + l(M[x])• ADD * x l(M[0]) + l(x) + l(M[x]) + l(M[M[x]])• …• READ x l(valore di input corrente) + l(x)• READ* x l(valore di input corrente) + l(x) + l(M[x])• WRITE= x l(x)• WRITE x l(x) + l(M[x])• WRITE * x l(x) + l(M[x]) + l(M[M[x]])• JUMP lab 1• JGZ lab l(M[0])• JZ lab l(M[0])• HALT 1

232Applicando il nuovo criterio di costo

• Al calcolo di is-prime(n) (solo nei punti essenziali)

• LOOP: LOAD 1 1+l(n)• SUB 2 l(n) +2 + l(M[2])• JZ YES l(M[0])• LOAD 1 1+l(n)• DIV 2 l(n) +2 + l(M[2])• MULT 2 l(n/M[2]) +2 + l(M[2]) (< l(n))• SUB 1 l(M[0]) +1 + l(n) < 2. l(n) +1 • JZ NO ≤ l(n)• LOAD 2 ≤ l(n) + k• ADD= 1 ...• STORE 2• JUMP LOOP

• In conclusione si può facilmente maggiorare la singola iterazione del ciclo con Θ(log(n))• Ergo la complessità temporale complessiva è Θ(n.log(n))

233

• Similmente otteniamo:

• Θ(n.log(n)) per il riconoscimento di wcwR (NB: più della MT! E’ possibile fare meglio?)• Θ(log2(n)) per la ricerca binaria• …• Costo a criterio di costo logaritmico = Costo a criterio di costo costante * log(n)? • Costo a criterio di costo logaritmico = Costo a criterio di costo costante * log(Costo a

criterio di costo costante )?• Spesso ma non sempre:• Per il calcolo di 22n

costo a criterio di costo logaritmico ≥ 2n (complessità temporale ≥complessità spaziale)

• Esiste un criterio per scegliere il criterio?– A buon senso (!):– Se l’elaborazione non altera l’ordine di grandezza dei dati di ingresso, la memoria allocata

inizialmente (staticamente?) può non variare a run-time ---> non dipende dai dati ---> una singola cella è considerabile elementare e con essa le operazioni relative ---> criterio di costo costante OK

– Altrimenti (fattoriale, 22n

, ricorsioni “feroci”, …) indispensabile criterio logaritmico: l’unico “garantito”!

234

Le relazioni tra le complessità relative ai diversi modelli di calcolo

• Lo stesso problema risolto con macchine diverse può aver complessità diverse• Può darsi che per P1 il modello M1 sia meglio del modello M2 ma per P2

succeda il contrario (ricerca binaria, accesso diretto, oppure accesso e memorizzazione sequenziale [riconoscimento di wcwR]

• Non esiste un modello migliore in assoluto• Non esiste un analogo della tesi di Church per la complessità …• Però:• E’ possibile stabilire almeno almeno una relazione -di maggiorazione- a priori

tra le complessità di diversi modelli di calcolo.• Teorema (tesi) di correlazione polinomiale (in analogia con la tesi di Church):

– Sotto “ragionevoli” ipotesi di criteri di costo (il criterio di costo costante per la RAM non è “ragionevole”in assoluto!) se un problema è risolvibile mediante un modello di calcolo M1 con complessità (spazio/temporale) C1(n) allora è risolvibile da qualsiasi altro modello di calcolo M2 con complessità C2(n) ≤ P2(C1(n)), essendo P2 un opportuno polinomio

235

Prima di dimostrare il teorema (non più tesi!) nel caso MT-RAM, valutiamone l’impatto:

• E’ vero che i polinomi possono anche essere n1000, ma è sempre meglio dell’”abisso” esponenziale (nk contro 2n)

• Grazie al teorema di correlazione polinomiale possiamo parlare della classe dei problemi risolvibili in tempo/spazio polinomiale (non di quelli risolvibili in tempo quadratico!): la classe non dipende dal modello adottato

• Grazie a questo risultato -e ad altri importanti fatti teorici- si è da tempo adottata l’analogia:

– classe dei problemi “trattabili” in pratica = classe dei problemi risolvibili in tempopolinomiale : P

– La teoria include in P anche i problemi con complessità n1000 (comunque sempre meglio di quelli a complessità esponenziale), ma l’esperienza pratica conferma che i problemi di interesse applicativo (ricerche, cammini, ottimizzazioni, …) che sono in P hanno anche grado del polinomio accettabile

– (similmente vedremo tra poco che la relazione di complessità tra MT e RAM è“piccola”)

236La correlazione (temporale) tra MT e RAM:1: Da MT (a k nastri) a RAM

• La memoria della RAM simula la memoria della MT:1 cella RAM per ogni cella di nastro di MTPerò, invece di usare blocchi di memoria RAM per simulare ogni nastro, associamo un blocco -di k celle- ad ogni k-pla di celle prese per ogni posizionedi nastro, + un blocco “di base”:

Blocco 0 K+1 celle per memorizzare stato e posizione delle k testine

Blocco 1 K celle per memorizzare il primosimbolo di ogni nastro

Blocco i K celle per memorizzare l’i-esimo simbolo di ogni nastro

237• Una mossa della MT è simulata dalla RAM:

Blocco 0

Blocco 1

Blocco i

• Lettura:

• Viene esaminato il contenuto del blocco 0 (pacchetto di k+1 accessi, c.(k+1)

mosse)

• Vengono fatti k accessi indiretti in k blocchi per esaminare il contenuto delle celle in corrispondnza delle testine

• Scrittura:

• Viene cambiato lo stato

• Vengono aggiornati, mediante STORE indiretti, i contenuti delle celle corrispondenti alla posizione delle testine

• Vengono aggiornati, nel blocco 0, i valori delle posizioni delle k testine

Una mossa di MT richiede h.k mosse di RAM:

A criterio di costo costante TR Θ (TM)

A criterio di costo logaritmico [quello “serio”] TR Θ (TM.log(TM) (un accesso indiretto a i costa log(i)

238La correlazione (temporale) tra MT e RAM:

2: Da RAM a MT(in un caso semplice ma centrale: riconoscimento di linguaggi senza usare MULT e DIV:

la generalizzazione è banale)• Il nastro principale della MT:

$ ij # M[ij ] $ $ ik # M[ik ] $

• NB: – Le varie celle RAM sono tenute in ordine– Inizialmente il nastro è vuoto ---> in un generico istante vi si trovano memorizzate

solo le celle che hanno ricevuto un valore (tramite una STORE)– ij e M[ij] sono rappresntati in codifica binaria

• Ulteriori nastri:– Un nastro contiene M[0] (in binario)– Un nastro di servizio

239• Una mossa della RAM è simulata dalla MT:

$ ij # M[ij ] $ $ ik # M[ik ] $

• Esaminiamone un campione:• LOAD h:

– Si cerca il valore h nel nastro principale (se non si trova: errore)– Si copia la parte accanto, M[h] in M[0]

• STORE h:– Si cerca h. Se non si trova si “crea un buco” usando il nastro di servizio– Si memorizza h e si copia M[0] nella parte accanto (M[h]); si ricopia la parte

successiva dal nastro di servizio– Se h esiste già si copia M[0] nella parte accanto (M[h]); ciò può richiedere l’uso del

nastro di servizio se il numero di celle già occupate non è uguale a quelle di M[0].• ADD* h:

– Si cerca h; si cerca M[h]; …• Con facile generalizzazione:• Simulare una mossa di RAM può richiedere alla MT un numero di mosse

maggiorabile da c. lunghezza del nastro principale.

240• A questo punto:• Lemma: la lunghezza del nastro principale è limitata superiormente da una

funzione Θ(TR)

Ogni “cella ij-esima” della RAM richiede nel nastro l(ij) + l(M[ij ]) (+2) celle del nastro.

Ogni “cella ij-esima” esiste nel nastro se e solo se la RAM ha eseguito almeno una STORE su di essa.

La STORE è costata alla RAM l(ij) + l(M[ij ]) ---->

Per riempire r celle, di lunghezza complessiva

alla RAM occorre un tempo almeno proporzionale allo stesso valore.

Dunque, per simulare una mossa della RAM, la MT impiega un tempo al più Θ(TR); una mossa di RAM costa almeno 1; se la RAM ha complessità TR esegue al più TR mosse ---> la simulazione completa della RAM da parte della MT costa al più Θ(T2

R).

])[()(,1

iMlilrj

j +∑=

$ ij # M[ij ] $ $ ik # M[ik ] $

241

Alcune puntualizzazioni e avvertimenti conclusivi

• Attenzione al parametro di dimensione dei dati:– lunghezza delle stringa di ingresso (valore assoluto)– valore del dato (n)– numero di elementi di una tabella, di nodi di un grafo, di righe di una matrice, …– …– tra tali valori sussistono certo relazioni, ma non sempre esse sono lineari (il

numero n richiede una stringa di ingresso di lunghezza log(n)!).• La ricerca binaria implementata con una MT viola il teorema di correlazione

polinomiale??• Attenzione all’ipotesi: riconoscimento di linguaggio ---> dati non già in

memoria ---> complessità almeno lineare.• Operazioni dominanti (e.g. I/O): complessità lineare rispetto alle operazioni

dominanti e quadratica in complesso?• Caso pessimo e caso medio nei casi pratici (Quicksort, compilazione, …:

eccezioni?)

242

Apriamo infine -fuori programma- una piccola finestra su aspetti avanzati ma estremamente rilevanti della complessità del calcolo

• Alcune domande importanti:– Esistono limiti inferiori alla complessità?– Aumentando la complessità si aumenta (sempre) la classe dei problemi risolvibili?

(se spendo di più ottengo di più?)– Esiste una sorta di “classe universale di complessità” (tutti i problemi risolvibili si

possono risolvere all’interno di una certa classe)– Come si definisce una “classe di complessità?– Ha senso, e se sì, come, definire la complessità di macchine nondeterministiche?– L’introduzione del nondeterminismo può cambiare la complessità di soluzione dei

problemi?– ...

243

Concentriamoci sulla computazione nondeterministica

• In primis: come si definisce?– La computazione più veloce?– La più lenta?– E se alcune comoputazioni non terminano e altre sì?– Solo le computazioni che accettano?– La computazione più veloce tra quelle che accettano … se ce ne sono!

• Che significato pratico hanno le computazioni nondeterministiche, visto che le macchine reali sono deterministiche?

• Per rispondere rifacciamoci al tema generale di computazione nondeterministica: modello per parallelismo, ricerca “cieca” tra diverse vie, …

• Il grande impatto pratico di questo tema nasce proprio dal fatto ….

244

• … che moltissimi problemi di grande interesse pratico hanno semplice, naturale ed “efficiente” soluzione in termini nondeterministici:

– Il cammino hamiltoniano in un grafo– La soddisfacibilità di formule logiche proposizionali (requisiti su sistemi finiti)– ….

• Caratteristica che accomuna la soluzione di tutti questi problemi è che è “difficile” trovare la soluzione ma è facile verificare se una possibile soluzione lo è effettivamente:

– se un diavoletto mi dice “prova questa”, verificare se la “soffiata” è giusta o no non è difficile ---->

– tipici problemi risolti in maniera esaustiva: le “provo tutte”– in modo nondeterministico: scelgo (ND) una possibile soluzione; verifico se lo è.– Ovviamente passando alla versione deterministica, provarle tutte diventa molto

oneroso (si ricordi la visita degli alberi)• Se ne ricava una -grandissima- classe di problemi (contenente gli esempi di

sopra e decine di migliaia di altri problemi):

245• NP: la classe dei problemi risolvibili nondeterministicamente in tempo

polinomiale• P: la classe dei problemi risolvibili deterministicamente in tempo polinomiale (i

problemi trattabili)• La grande domanda: P = NP??• Molto probabilmente no! Però …• Se P = NP potremmo risolvere in maniera “efficiente” un’enorme quantità di

problemi oggi intrattabili o affrontati con euristiche, casi particolari, ecc.• Il concetto di (NP) completezza: un “rappresentante” della classe racchiude in

sé l’essenza di tutti i problemi della classe: troviamo la soluzione per esso e l’abbiamo trovata per tutti!

• Il bello è che nell’enorme congerie di NP, una grandissima quantità di problemi è a sua volta anche NP-completa: basterebbe risolverne uno in tempo polinomiale (deterministicamente) e P sarebbe = NP; basterebbe provare per uno solo di essi che è intrattabile e tutti gli altri lo sarebbero pure!

• Infine: nondeterminismo non è sinonimo di casualità però … le affascinanti prospettive della computazione probabilistica.