C. Gaibisso
Programmazione di calcolatori
Lezione IV
Esistono problemi non
risolvibili?
Programmazione di Calcolatori: Esistono problemi non risolvibili?
1
C. Gaibisso
Problemi & funzioni
Risolvere un problema:
estrarre l’informazione implicita a cui siamo
interessati dall’informazione esplicita in
nostro possesso
“calcolare” una delle funzioni che realizza tale
estrazione
Programmazione di Calcolatori: Esistono problemi non risolvibili?
2
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
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
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
C. Gaibisso
Idea
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
Programmazione di Calcolatori: Esistono problemi non risolvibili?
6
C. Gaibisso
Equipotenza e numerabilità
• 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
• L’insieme dei numeri pari Npari è
numerabile:
infatti la funzione f: Npari →N definita da
f(n) = n/2 è biunivoca
Programmazione di Calcolatori: Esistono problemi non risolvibili?
7
C. Gaibisso
Equipotenza e numerabilità
• Ovviamente:
se A è numerabile e B  A allora B è
numerabile
più informalmente
qualsiasi sottoinsieme di un insieme
numerabile è numerabile
Programmazione di Calcolatori: Esistono problemi non risolvibili?
8
C. Gaibisso
Insiemi numerabili
• Enumerazione:
N
Elementi di A
0
1
a0
a1
2
….
a2
….
….
n
….
an
…
….
Programmazione di Calcolatori: Esistono problemi non risolvibili?
9
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: Esistono problemi non risolvibili?
10
C. Gaibisso
Quanti sono gli algoritmi?
• 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
Programmazione di Calcolatori: Esistono problemi non risolvibili?
11
C. Gaibisso
Esempio
• Alfabeto  {a, b, c}
N
Elementi di S
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?
12
C. Gaibisso
Quanti sono gli algoritmi?
• L’insieme A degli algoritmi costruiti a
partire dallo stesso alfabeto è numerabile
ovvio in quanto A  S
Programmazione di Calcolatori: Esistono problemi non risolvibili?
13
C. Gaibisso
Quante sono le funzioni?
• 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
stringa
1
0
f(2)=1 f(3)=1
1
1
…
f(n)=0
…
…
0
…
Programmazione di Calcolatori: Esistono problemi non risolvibili?
14
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 esiste almeno una
stringa mancante da qualsiasi
enumerazione
Programmazione di Calcolatori: Esistono problemi non risolvibili?
15
C. Gaibisso
Quante sono le
funzioni?
1. consideriamo una qualsiasi
enumerazione
2. consideriamone la
diagonale
3. complementiamo tale
diagonale, ottenendo una
nuova stringa binaria di
lunghezza infinita
4. in quanto tale, dovrebbe
comparire nella enumerazione
N
Elementi di
B
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
…
16
C. Gaibisso
Quante sono le
funzioni?
5. supponiamo compaia nella
posizione i-esima, la 3a per
esempio
6. per costruzione, se la 3a cifra
nella diagonale complementata è 1 (risp., 0) il bit alla
intersezione della 3a colonna
e della 3a riga nella enumerazione è 0 (risp., 1) da cui
l’assurdo
7. di conseguenza possiamo
affermare che non esistono
enumerazioni per B
N
Elementi di
B
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
…
17
C. Gaibisso
Concludendo
• l’insieme degli algoritmi (A) numerabile
• 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
• se l’insieme delle funzioni da N in {0, 1}
(F0,1 ) non è numerabile allora l’insieme
delle funzioni (F) non è numerabile
Programmazione di Calcolatori: Esistono problemi non risolvibili?
18
C. Gaibisso
Concludendo
• se l’insieme degli algoritmi (A) è numerabile 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
Programmazione di Calcolatori: Esistono problemi non risolvibili?
19