G. Amodeo,C. Gaibisso Programmazione di Programmazione di

CalcolatoriCalcolatori

Lezione IVEsistono Problemi non

Risolvibili?

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 1

G. Amodeo,C. Gaibisso

Problemi e funzioniProblemi e funzioni

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 2

Risolvere un problema è sinonimo di calcolare una

funzione

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

G. Amodeo,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

G. Amodeo,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?

G. Amodeo,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

…. ….

G. Amodeo,C. Gaibisso

IdeaIdea

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 6

• “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

G. Amodeo,C. Gaibisso

Insiemi numerabiliInsiemi numerabili

• Insieme numerabile:

un insieme A è numerabile se e solo

se esiste f : A→B N biettivao, in altre

parole, se e solo se A B N

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 7

• 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

G. Amodeo,C. Gaibisso

Insiemi numerabiliInsiemi numerabili

• Se un insieme I è numerabile allora esiste una enumerazione per I

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 8

N Elementi di I0 i0

1 i1

2 i2

…. ….

…. ….

n in

… ….

G. Amodeo,C. Gaibisso

Quanti sono gli algoritmiQuanti sono gli algoritmi

Programmazione di Calcolatori: Cosa vuol dire scrivere un programma 9

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

• …..

G. Amodeo,C. Gaibisso

Quanti sono gli algoritmi?Quanti sono gli algoritmi?

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 10

• L’insieme A degli algoritmi è numerabile1.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

G. Amodeo,C. Gaibisso

EsempioEsempio

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 11

N Elementi di A

0 a

1 b

2 c

3 aa

4 ab

5 ac

6 ba

7 bb

… ….

39 aaaa

… …

•Alfabeto {a, b, c}

G. Amodeo,C. Gaibisso

Quante sono le funzioni?Quante sono le funzioni?

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 12

• L’insieme delle funzioniF { f | f : N → {0,1}}

non è numerabile

• F B, l’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 …

G. Amodeo,C. Gaibisso

Quante sono le funzioni?Quante sono le funzioni?

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 13

• 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

G. Amodeo,C. Gaibisso

Quante sono le funzioniQuante sono le funzioni

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 14

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. Consideriamo una generica enumerazione

1 1 1 1 0 0 …

4. In quanto tale, dovrebbe comparire nella enumerazione

2. Consideriamone la diagonale

3. Complementiamo tale diagonale, otteniamo una stringa binaria di lunghezza infinita

G. Amodeo,C. Gaibisso

Quante sono le funzioniQuante sono le funzioni

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 15

7. Ne concludiamo che non esistono enumerazioni per B

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 0 …

5. Supponiamo compaia nelle generica posizione i (la III nel nostro esempio)6. Per costruzione, se la i-esima 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

G. Amodeo,C. Gaibisso

ConcludendoConcludendo

Programmazione di Calcolatori: Esistono Problemi non Risolvibili? 16

• 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