per questi esistono programmi che li risolvono
(almeno in teoria)
in generale?
problemi non calcolabili
per certi problemi non esiste un programma che li risolve
si dimostra in due modi:
problemi di decisione
serve una definizione formale di problema
per semplicità: solo problemi con soluzione 0/1
ogni altro problema ha una sua versione così:
problemi di decisione su interi
dato del problema: intero
risultato: sì o no
formalizzazione?
formalizzazione
per alcuni interi la soluzione è 1
per tutti gli altri è 0
esempio:
rappresentazione dei problemi
problema = insieme di interi
interi per cui la soluzione è 1
cardinalità
problema=insiemi di interi
quindi:
|problemi| = |insiemi di interi|
il numero dei problemi non è contabile
numero dei programmi
programma = sequenza di caratteri
(anche il ritorno a capo è un carattere)
|programmi| = |interi|
contabile
non calcolabilità
|problemi| > |programmi|
per definizione:
ci sono problemi per i quali non c'è un programma
sì ma...
basato su: problema=insieme di interi
che problema è {1,5,29,31,52,100,102,109}?
alcuni insiemi non hanno un senso
nessuna utilità pratica
non è che quelli non risolvibili sono tutti così?
premessa
un programma Python sta su un file
può leggere un file qualsiasi:
s=open('nomefile').read()
anche se stesso?
programma che legge se stesso
| stesso.py: | |
s=open('stesso.py').read()
print s
|
|
apre e legge il file, poi lo stampa
era solo una premessa
il problema della fermata
while i!=10: print i i=i+1
se i≤10 il programma termina
altrimenti va avanti all'infinito
se non termina?
sarebbe utile saperlo prima
es: Word non risponde
ci sta solo mettendo del tempo o è entrato in un ciclo infinito?
secondo caso: errore nel programma
idea: scrivere un programma che verifica se questo può succedere
il problema della fermata
scrivere un programma che risolve questo problema
il programma del problema della fermata
fermata.py legge un file
in quel file c'è un altro programma
fermata.py lo legge, poi:
complicato?
fermata.py è un programma che legge un file
solo che nel file c'è un altro programma
esempio: vediamo se ci sono while in altro.py
s=open('altro.py').read()
m=search('while', s)
if m:
print 'ci sono while'
non basta…
problema della fermata, in generale
se non ci sono cicli o chiamate a funzione termina sempre
ma anche se ci sono cicli può terminare:
while x<10: print x x=x+1
programma con ciclo che termina sempre
non c'è modo di eseguirlo?
fermata.py esegue il programma in esame altro.py
se questo termina, stampa 1
se non termina?
anche dopo due ore:
come faccio a sapere che non finirà fra 2 secondi?
analisi del programma
while i<10: print i i=i+1
termina sempre
while i!=10: print i i=i+1
termina solo se i≤10
necessaria un'analisi del programma per capirlo
problema indecidibile
non esiste un programma che risolve il problema della fermata
non c'è modo di realizzare fermata.py
dimostrazione per assurdo: assumiamo che esista
dimostrazione per assurdo
diciamo che fermata.py esiste
lo modifichiamo così:
| fermata.py | modificato.py | |
|---|---|---|
f=open('altro.py')
…
print '0'
…
print '1'
…
|
⇒ ⇒ |
f=open('altro.py')
…
quit()
…
while 1:
pass
…
|
cosa fa modificato.py?
| fermata.py | modificato.py | ||
|---|---|---|---|
|
1
2 3 |
f=open('altro.py')
…
print '0'
…
print '1'
…
|
⇒ ⇒ |
f=open('altro.py')
…
quit()
…
while 1:
pass
…
|
se altro.py termina:
riassumendo…
cosa fa modificato.py: riassunto
ulteriore modifica
si cambia la riga di lettura:
f=open('altro.py') ⇒ f=open('modificato.py')
comportamento: uguale, ma con modificato.py al posto di altro.py…
quando modificato.py legge se stesso
conclusione
modificato.py termina se non termina
e viceversa
contraddizione
fermata.py non esiste
altri problemi indecidibili
si dimostra per riduzione dal problema della fermata a loro
se fossero decidibili lo sarebbe anche il problema della fermata
linea di dimostrazione
si considera un programma che legge un altro programma
si fa in modo che faccia il contrario di quello che dovrebbe verificare
gli si fa leggere se stesso
autoreferenzialità
per dimostrare che un problema è indecidibile serve un problema che riguardi i programmi
poi si assume che il programma esista, e gli si fa leggere il programma stesso
paradossi
sempre basati sulla autoreferenzialità
paradosso del coccodrillo
un coccodrillo ha catturato un bambino, ma ora promette di lasciarlo andare se il padre indovinerà cosa farà il coccodrillo
il padre ha detto che non lo lascerà andare
affermazioni vere e false
questa frase è falsa
non si può dire che è vera
non si può dire che è falsa
insiemi di insiemi
famiglia = insieme di persone
insieme di famiglie = insieme di insiemi di persone
un insieme può contenere altri insiemi
ma…
paradosso di Russell
T = { S | S ∉ S }
insiemi degli insiemi che non contengono se stessi
domanda: T ∈ T?
soluzione al paradosso di Russell
impedire l'autoreferenzialità
costruire gli insiemi da elementi semplici
poi insiemi da questi, ecc.
vieta affermazioni come S ∈ S
affermazioni vere e affermazioni false
in matematica:
ne esistono di più complicate!
affermazioni più complesse
tempo per dimostrarle: 358 anni e 39 anni
P=NP: non si sa, da 42 anni
premio per la soluzione: $1000000
il programma di Hilbert
(semplificando molto)
fra le altre cose:
ogni affermazione matematica si può dimostrare essere o vera o essere falsa?
teorema di incompletezza di Gödel:
certe affermazioni non possono essere né dimostrate né confutate