C. Gaibisso Programmazione di calcolatori Lezione IV Esistono problemi non risolvibili?...

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


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


• 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


• 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


Informazione esplicita

Informazione implicita

0, 0 0

1, 0 1

0, 1 1

…. ….

158, 641 641

…. ….

2.856, 567 2.856

…. ….

C. Gaibisso

IdeaIdea


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à


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


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


N Elementi di A

0 a0

1 a1

2 a2

…. ….

…. ….

n an

… ….

C. Gaibisso

Quanti sono gli algoritmi?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

• …..

C. Gaibisso



• 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


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



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


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


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


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?


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


• 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


• 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

C. Gaibisso Programmazione di calcolatori Lezione IV Esistono problemi non risolvibili?...

Documents

Transcript of C. Gaibisso Programmazione di calcolatori Lezione IV Esistono problemi non risolvibili?...