C. Gaibisso Programmazione di Programmazione di calcolatoricalcolatori
Lezione IVEsistono problemi non
risolvibili?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 1
C. Gaibisso
Problemi & funzioniProblemi & funzioni
Programmazione di Calcolatori: Esistono problemi non risolvibili? 2
estrarre l’informazione implicita a cui siamo interessati dall’informazione
esplicita in nostro possesso
“calcolare” una delle funzioni che realizza tale estrazione
Risolvere un problema:
C. Gaibisso Problemi risolvibili e funzioni Problemi risolvibili e funzioni calcolabilicalcolabili
Programmazione di Calcolatori: Esistono problemi non risolvibili? 3
• Funzioni calcolabili:
una funzione è calcolabile se
esiste un algoritmo che la
calcola
• Problemi risolvibili:
un problema è risolvibile se
esiste un algoritmo che lo
risolve
C. Gaibisso
EsempioEsempio
Programmazione di Calcolatori: Esistono problemi non risolvibili? 4
• Funzione:
f : N x N→N
Start
Stop
N1, N2
N1 > N2si
N1no
N2
• Problema:
Qual è il massimo tra due numeri
interi?
C. Gaibisso
EsempioEsempio
Programmazione di Calcolatori: Esistono problemi non risolvibili? 5
Informazione esplicita
Informazione implicita
0, 0 0
1, 0 1
0, 1 1
…. ….
158, 641 641
…. ….
2.856, 567 2.856
…. ….
C. Gaibisso
IdeaIdea
Programmazione di Calcolatori: Esistono problemi non risolvibili? 6
1. “contiamo” gli algoritmi
2. “contiamo” le funzioni
3. se il “numero” delle funzioni dovesse risultare “maggiore” del “numero” degli algoritmi allora esisterebbe almeno una funzione non calcolabile, e, di conseguenza, almeno un problema non risolvibile
C. Gaibisso
Equipotenza e numerabilitàEquipotenza e numerabilità
Programmazione di Calcolatori: Esistono problemi non risolvibili? 7
• L’insieme dei numeri pari Npari è numerabile:
infatti la funzione f: Npari →N
definita da f(n) = n/2 è biunivoca
• Insiemi equipotenti:
A e B sono equipotenti, A B, se e
solo se esiste una funzione biunivoca
f : A→B• Insiemi numerabili:
A è numerabile se e solo A B
N
C. Gaibisso
Equipotenza e numerabilitàEquipotenza e numerabilità
Programmazione di Calcolatori: Esistono problemi non risolvibili? 8
• Ovviamente:
se A è numerabile e B A allora B è
numerabile
più informalmente
qualsiasi sottoinsieme di un insieme
numerabile è numerabile
C. Gaibisso
Insiemi numerabiliInsiemi numerabili• Enumerazione:
Programmazione di Calcolatori: Esistono problemi non risolvibili? 9
N Elementi di A
0 a0
1 a1
2 a2
…. ….
…. ….
n an
… ….
C. Gaibisso
Quanti sono gli algoritmi?Quanti sono gli algoritmi?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 10
Nozione intuitiva di algoritmo• è una sequenza finita di istruzioni
• ogni istruzione è costruita a partire da un alfabeto di dimensione finita
• ogni istruzione nella sequenza è codificata con una quantità finita di informazione
• deve esistere un agente di calcolo C capace di eseguire le istruzioni dell’algoritmo
• C deve avere capacità di memorizzazione
• …..
C. Gaibisso
Quanti sono gli algoritmi?Quanti sono gli algoritmi?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 11
• L’insieme S delle stringhe di lunghezza finita costruite a partire da un alfabeto di dimensione finita è numerabile
1.definisco un ordinamento tra i caratteri dell’alfabeto (in modo analogo a quanto avviene per i caratteri dell’alfabeto della lingua italiana)
2.enumero tutte le stringhe di lunghezza finita costruite a partire dall’alfabeto in ordine di lunghezza crescente
3.enumero le stringhe di eguale lunghezza in ordine lessicografico
C. Gaibisso
EsempioEsempio
Programmazione di Calcolatori: Esistono problemi non risolvibili? 12
N Elementi di
S 0 a
1 b
2 c
3 aa
4 ab
5 ac
6 ba
7 bb
… ….
39 aaaa
… …
•Alfabeto {a, b, c}
C. Gaibisso
Quanti sono gli algoritmi?Quanti sono gli algoritmi?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 13
• L’insieme A degli algoritmi costruiti a partire dallo stesso alfabeto è numerabile
ovvio in quanto A S
C. Gaibisso
Quante sono le funzioni?Quante sono le funzioni?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 14
• L’insieme delle funzioni
F0,1 { f | f : N → {0,1}} F
non è numerabile
• F0,1 B, con B insieme delle stringhe binarie di lunghezza infinita
funzione
f(0) = 1
f(1)=0
f(2)=1
f(3)=1
… f(n)=0
…
stringa 1 0 1 1 … 0 …
C. Gaibisso
Quante sono le funzioni?Quante sono le funzioni?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 15
• L’insieme B delle stringhe binarie di lunghezza inifinita non è numerabile
• se così non fosse potrei enumerare l’insieme di tali stringhe
dimostreremo che esiste almeno una stringa mancante da qualsiasi enumerazione
C. Gaibisso Quante sono Quante sono lelefunzioni?funzioni?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 16
N Elementi di B0 0 0 0 0 1 1 …
1 0 0 0 1 1 1 …
2 1 1 0 0 1 0 …
3 1 1 1 0 0 1 …
4 0 0 0 0 1 0 …
5 1 1 1 1 1 1 …
6 0 0 1 0 1 0 …
7 1 1 0 1 0 0 …
8 0 1 0 1 0 1 …
9 1 1 0 1 0 1 …
… .. ..
.
...
.
...
1. consideriamo una qualsiasi enumerazione
1 1 1 1 0 0 …
4. in quanto tale, dovrebbe comparire nella enumera-zione
2. consideriamone la diagonale
3. complementiamo tale diagonale, ottenendo una nuova stringa binaria di lunghezza infinita
C. Gaibisso
Quante sono leQuante sono lefunzioni?funzioni?
Programmazione di Calcolatori: Esistono problemi non risolvibili? 17
7. di conseguenza possiamo affermare che non esistono enumerazioni per B
N Elementi di B0 0 0 0 0 1 1 …
1 0 0 0 1 1 1 …
2 1 1 0 0 1 0 …
3 1 1 1 0 0 1 …
4 0 0 0 0 1 0 …
5 1 1 1 1 1 1 …
6 0 0 1 0 1 0 …
7 1 1 0 1 0 0 …
8 0 1 0 1 0 1 …
9 1 1 0 1 0 1 …
… .. ..
.
...
.
...
1 1 1 1 0 0 …
5. supponiamo compaia nella posizione i-esima, la 3a per esempio
6. per costruzione, se la 3a cifra nella diagonale complemen-tata è 1 (risp., 0) il bit alla intersezione della 3a
colonna e della 3a riga nella enume-razione è 0 (risp., 1) da cui l’assurdo
C. Gaibisso
ConcludendoConcludendo
Programmazione di Calcolatori: Esistono problemi non risolvibili? 18
• se l’insieme delle stringhe binarie di lunghezza finita (B) non è numerabile allora l’insieme delle funzioni da N in {0, 1} (F0,1 ) non è numerabile
• l’insieme degli algoritmi (A) numerabile
• se l’insieme delle funzioni da N in {0, 1} (F0,1 ) non è numerabile
allora l’insieme delle funzioni (F) non è numerabile
C. Gaibisso
ConcludendoConcludendo
Programmazione di Calcolatori: Esistono problemi non risolvibili? 19
• se l’insieme degli algoritmi (A) è nume-rabile e l’insieme delle funzioni (F) non è numerabile allora esiste almeno una funzione non calcolabile
• se esiste almeno una funzione non calcolabile allora esiste almeno un problema non risolvibile