G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione IV
Esistono Problemi non
Risolvibili?
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
1
G. Amodeo,
C. Gaibisso
Problemi e funzioni
Risolvere un problema
Estrarre dalla codifica dell’informazione
esplicita (quella in nostro possesso)
informazione imlicita (quella a cui siamo
interessati)
Calcolare una funzione che associa informazione
esplicita a informazione implicita
Risolvere un problema è
sinonimo di calcolare una
funzione
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
2
G. Amodeo,
C. Gaibisso
Problemi risolvibili e funzioni calcolabili
• Problemi risolvibili:
un problema è risolvibile se esiste un
algoritmo che lo risolve
• Funzioni calcolabili:
una funzione è calcolabile se esiste
un algoritmo che la calcola
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
3
G. Amodeo,
C. Gaibisso
Esempio
• Problema:
Qual è il massimo tra due numeri interi?
• Funzione:
Start
f : N x N→N
N1, N2
N1
si
N1 > N2
no
N2
Stop
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
4
G. Amodeo,
C. Gaibisso
Esempio
Informazione
Esplicita
0, 0
Informazione
Implicita
0
1, 0
0, 1
….
158, 641
1
1
….
641
….
2.856, 567
….
….
2.856
….
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
5
G. Amodeo,
C. Gaibisso
Idea
• “Contiamo” gli algoritmi
• “Contiamo” le funzioni
• Se le funzioni dovessero essere in
“numero maggiore” degli algoritmi
allora ne dedurremmo che non
tutte le funzioni sono calcolabili
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
6
G. Amodeo,
C. Gaibisso
Insiemi numerabili
• Insieme numerabile:
 un insieme A è numerabile se e solo se esiste
f : A→B  N biettiva
o, in altre parole,
 se e solo se A  B  N
• Insieme dei numeri pari Npari è numerabile:
per provare questa affermazione è sufficiente
provare che la funzione f: Npari →N definita da
f(n) = n/2 è biettiva
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
7
G. Amodeo,
C. Gaibisso
Insiemi numerabili
• Se un insieme I è numerabile allora
esiste una enumerazione per I
N
Elementi di I
0
i0
1
2
i1
i2
….
….
….
n
….
in
…
….
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
8
G. Amodeo,
C. Gaibisso
Quanti sono gli algoritmi
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
• …..
Programmazione di Calcolatori: Cosa vuol dire scrivere un programma
9
G. Amodeo,
C. Gaibisso
Quanti sono gli algoritmi?
• L’insieme A degli algoritmi è 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 gli algoritmi in ordine di lunghezza
crescente
3. enumero gli algoritmi di eguale lunghezza in
ordine lessicografico
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
10
G. Amodeo,
C. Gaibisso
Esempio
• Alfabeto  {a, b, c}
N
Elementi di A
0
a
1
b
2
c
3
aa
4
ab
5
ac
6
ba
7
bb
…
….
39
aaaa
…
…
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
11
G. Amodeo,
C. Gaibisso
Quante sono le funzioni?
• L’insieme delle funzioni
F  { f | f : N → {0,1}}
non è numerabile
• F  B, l’insieme delle stringhe binarie di
lunghezza infinita
funzione
f(0) = 1
f(1)=0
stringa
1
0
f(2)=1 f(3)=1
1
1
…
f(n)=0
…
…
0
…
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
12
G. Amodeo,
C. Gaibisso
Quante sono le funzioni?
• L’insieme B delle stringhe binarie di
lunghezza inifinita non è numerabile
• se così non fosse potrei
enumerare l’insieme di tali
stringhe.
dimostreremo che esisterà
almeno una stringa mancante da
qualsiasi enumerazione
considereremo
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
13
G. Amodeo,
C. Gaibisso
Quante sono le funzioni
1. Consideriamo una
generica enumerazione
2. Consideriamone la
diagonale
3. Complementiamo tale
diagonale, otteniamo una
stringa binaria di
lunghezza infinita
4. In quanto tale, dovrebbe
comparire nella
enumerazione
N
Elementi di I
0
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
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
0
…
14
G. Amodeo,
C. Gaibisso
Quante sono le funzioni
5. Supponiamo compaia
nelle generica posizione i
(la III nel nostro esempio)
N
Elementi di I
0
0
0 0 0 1 1 …
1
0
0 0 1 1 1 …
6. Per costruzione, se la iesima cifra della diagonale
complementata è 1(risp.,
0) il bit all’intersezione
della i-esima colonna e
della i-esima riga nella
enumerazione è 0 (risp.,
1) da cui l’assurdo
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 …
7. Ne concludiamo che non
esistono enumerazioni
per B
9
1
1 0 1 0 1 …
…
..
.. .. .. .. ..
1
1
1
1
0
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
0
…
15
G. Amodeo,
C. Gaibisso
Concludendo
• Quando provo a mettere in
corrispondenza biunivoca funzioni ed
algoritmi, esiste sempre almeno una
funzione (quella identificata dalla
diagonale complementata) alla quale
non posso associare un algoritmo
• Ne concludo che esistono funzioni non
calcolabili e quindi problemi non
risolvibili
Programmazione di Calcolatori: Esistono Problemi non Risolvibili?
16