Università di Torino – Facoltà di Scienze MFN Corso di Studi in Informatica Curriculum SR (Sistemi e Reti)
Algoritmi e Laboratorio a.a. 2009-10 Lezioni
f Eli Gi tti prof. Elio Giovannetti
Lezione 10 – Terminazione dei programmi.
(versione 27/10/09)
Quest' opera è pubblicata sotto una Licenza Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
Correttezza parziale e correttezza totale
• correttezza parziale: un programma è parzialmente corretto rispetto alla sua specifica se, quando termina, fornisce il risultato corretto secondo la specifica.
• Un algoritmo che per alcuni valori dell'input termina con la risposta corretta mentre per altri non termina è un algoritmo solo parzialmente corretto, che di solito non ha molta utilità.
• Il programma while(true);è parzialmente corretto per
AlgELab-08-09 - Lez.17 2 27/10/09
Il programma while(true);è parzialmente corretto per qualunque specifica, ma non serve a molto !
• correttezza totale: un programma è totalmente corretto rispetto alla sua specifica se (per input che soddisfano alla precondizione stabilita dalla specifica) termina sempre, fornendo il risultato corretto secondo la specifica.
• quindi:
correttezza totale = correttezza parziale + terminazione.
Il problema della terminazione dei programmi
• Per stabilire la correttezza totale di un algoritmo (o più concretamente di una procedura) bisogna dimostrare che l'algoritmo (o la procedura) termina per ogni input legale.
• Quindi per stabilire che un algoritmo termina per qualunque input non si eseguel'algoritmo, ma si fa un ragionamento rigoroso (una dimostrazione) avente per oggetto l'algoritmo stesso.
27/10/09 AlgELab-08-09 - Lez.17 3
• Per algoritmi semplici la terminazione può essere evidente, e in tal caso la “dimostrazione” (un ragionamento banale) viene di solito omessa.
• Non faremo dimostrazioni a posteriori della correttezza totale – e quindi della terminazione – di un algoritmo dato, bensì impareremo a scrivere direttamente procedure e algoritmi corretti, costruendo contemporaneamente l’algoritmo e la dimostrazione della sua correttezza.
Esempio
Si vede (si dimostra) facilmente che il programma seguente:
public static void main(String[] args) { System.out.println("immetti un intero: ");
int n = new Scanner(System.in).nextInt();
while(n != 0) { n n 2
27/10/09 AlgELab-08-09 - Lez.17 4
n = n-2;
System.out.println(n);
} }
termina per input pari, non termina per input dispari.
Si vede (si dimostra) facilmente che il metodo seguente:
public static void test(BigInteger n) { while(n.compareTo(BigInteger.ZERO) != 0) {
n = n.subtract(new BigInteger("2"));
} }
d
termina per input pari, non termina per input dispari o negativi.
La sequenza di Collatz
La procedurastatic void scriviSequenzaCollatz(int n) { while(n != 1) {
if(n%2 == 0) n = n/2;
else n = 3*n + 1;
System.out.println(n);
} }
sperimentalmente termina "sempre" (con n = 1).
Cioè: per tutti i numeri naturali per cui è stato provato termina; al maggio 2007 è stato provato per ognuno dei naturali compresi fra 1 e un numero > 4035×1018(fonte wikipedia).
Tuttavia non si è ancora riusciti a dimostrare che esso
Esempio: la sequenza di Collatz.
In altre parole, non si è riusciti a dimostrare che non può esistere un qualche numero per il quale non termina.
Cioè non si è ancora riusciti a capire perchétermina sempre:
il fatto che, per tutti i numeri per cui è stato provato, il calcolo termini sempre, rimane un fatto "misterioso".
27/10/09 AlgELab-08-09 - Lez.17 7
Nota: si confronti tale situazione con quella in cui abbiamo una dimostrazione di terminazione, cioè capiamo perché l'algoritmo termina (ad es. l'esponenziale veloce, che studieremo).
Il problema della fermata del 9.
Terminazione e non-terminazione.
• Se il tram 9 passerà alla fermata, aspettando abbastanza a lungo lo scopriremo. Se lo aspettiamo e non arriva, non sappiamo se passerà oppure se ha cambiato percorso o c'è sciopero.
• Per scoprire se un programma (con un certo input) termina non si può provare ad eseguirlo: infatti se lo vediamo
27/10/09 AlgELab-08-09 - Lez.17 8
p p g
terminare scopriamo ovviamente che termina, ma se non lo vediamo terminare non sappiamo se terminerà.
• Se il programma termina, aspettando abbastanza a lungo (ma non sappiamo quanto a lungo !) lo scopriremo.
• Se il programma non termina, non lo sapremo mai !
• L'unico modo per stabilire che un programma non termina è dimostrare che non termina !
Il problema della fermata o halting problem.
• Spesso, esaminando un programma e ragionando su di esso senza eseguirlo, siamo in grado di stabilire se il programma termina (per un dato input) oppure no.
• È certamente possibile scrivere un programma Stops (o, in italiano, Termina) che riconosca che certi programmi (con certi input) terminano e che certi altri non terminano: ad esempio il programma Stops può leggere il testo del
27/10/09 AlgELab-08-09 - Lez.17 9
p p g p p gg
programma e, se tale testo è semplicemente "while(true);", restituire il risultato "non termina"; ecc.
• Ci chiediamo però se sia possibile scrivere un programma il quale, preso in input un qualunque programma, esaminandone il testo sia in grado di stabilire se, per un dato input, esso termina o no.
Nota Bene
Un programma è un testo o, in forma binaria, una sequenza di bit, e quindi può sempre essere l'input di un altro
programma, eventualmente anche di se stesso.
Ad esempio si può scrivere in C un compilatore C, e poi farlo compilare a se stesso ...
È la tecnica cosiddetta del bootstrap, cioè del sollevarsi
27/10/09 AlgELab-08-09 - Lez.17 10
tirandosi per le stringhe delle proprie scarpe, come il Barone di Münchausen.
È quindi possibile scrivere un programma che prenda in input un altro programma, lo esamini, ecc.
Il problema della fermata o halting problem.
Cioè, il programma Stopsdeve soddisfare alla seguente specifica, contenente un quantificatore universale:
Per tutti(gl'infiniti possibili) programmi Pe input X per P, se Pcon input Xtermina,
allora Stopsstampa "termina"
s Pc n input Xn n t rmin
27/10/09 AlgELab-08-09 - Lez.17 11
se Pcon input Xnon termina, allora Stopsstampa "non termina".
Alternativamente, potremmo specificare Stopscome una procedura con due argomenti P e X che deve restituire true o falsea seconda che P con input X termini oppure no.
Turing, 1936
Indecidibilità del problema della fermata.
Teorema:
Non può esistere un programma (o una macchina) il quale, dato un qualunque programma P e un input X per P, sia sempre in grado di determinare se il programma P eseguito con input
27/10/09 AlgELab-08-09 - Lez.17 12
g m p g mm g p
X termina oppure no.
Cioè non può esistere un programma Stops tale che:
programma
Stopsprogramma P
possibile input X
per P
27/10/09 AlgELab-08-09 - Lez.17 13
non termina Stops
SI se X
NO se X
programma P programma
P
termina
Nota Bene
Il programma Stopsnon può consistere semplicemente nel lanciare l'esecuzione del programma P con input X, poiché, se P non termina, il programma Stops (esattamente come noi) non lo scoprirà mai.
Il programma Stopsdeve evidentemente stabilire se P termina (con input X) senza eseguireP ma solo analizzandone il testo.
d l d P è
27/10/09 AlgELab-08-09 - Lez.17 14
Ad esempio, se il testo di P è:
while(X == 3) X = X;
una semplice analisi, che può essere incorporata in Stops, mostra che se X è 3 il programma P non termina, mentre per X diverso da 3 il programma P termina.
Dimostrazione
Assumiamo che un siffatto Stopsesista, e mostriamo che ciò conduce ad una contraddizione.
Sia dunque Stopsun programma che, per ogni programma P e ogni dato X, produce la risposta SI se il programma P con input X termina, produce la risposta NO se il programma P con input X non termina.
27/10/09 AlgELab-08-09 - Lez.17 15
con input X non termina.
Allora si può facilmente realizzare il programma S rappresentato schematicamente nella slide seguente.
Il programma S:
S
programmaprogramma P
programma
P programma
P
Il programma S crea una seconda copia di P, poi utilizza Stopsper stabilire se P con input P termina (eventualmente generando un errore o un’eccezione)
27/10/09 AlgELab-08-09 - Lez.17 16
S
output Stops
NO while(true) ;
SI NO
Come si comporta il programma S ?
Il programma S, eseguito con input un programma P, dopo aver utilizzato il programma Stops:•non termina se Peseguito con input Ptermina;
•termina se Peseguito con input Pnon termina.
Ora proviamo a dare in input al programma S il programma S stesso, cioè eseguiamo S dandogli un input P coincidente con S stesso.
Come si comporta S con input S ? Basta evidentemente sostituire P con S nella descrizione precedente in blu.
Il programma S eseguito con input S :
•non termina se Seseguito con input Stermina;
•termina se Seseguito con input Snon termina.
Cioè: S con input S non termina se termina, e termina se non termina !
CONTRADDIZIONE !
Conclusione
• Partendo dall'assunzione che il programma Stops esista, ed effettuando un ragionamento corretto, abbiamo derivato (cioè ottenuto, dedotto) una contraddizione.
• Pertanto l'assunzione è "errata": il programma
Stopspnon può esistere ! p
Formulazione java del teorema e della dimostrazione
Teorema: Non può esistere una procedura (metodo statico) static boolean stops(String met, String arg) {… }la quale, se l’argomento metè il testo di un metodo la cui intestazione è della forma
static booleannomeMetodo(String x)
(cioè statico con un solo parametro di tipo String, ecc.), restituisce:
l’ d M d ( )
•truese l’esecuzione di nomeMetodo(arg)termina;
•falsese l’esecuzione di nomeMetodo(arg)non termina.
Dimostrazione (per assurdo).
Supponiamo che il metodo stopsesista, cioè che esista un metodo molto complicato che, analizzando il testo del metodo passatogli nel parametro mete la stringa passatagli nel parametro arg, riesce a capire se met(arg)termina o no.
27/10/09 AlgELab-08-09 - Lez.17 19
Dimostrazione versione Java (continua)
Avremo quindi, ad esempio, la classe seguente:class HaltingProblem {
static boolean stops(String met, String arg) { if(met.contains("(String s)")
&& met.contains("while(s.equals(\"vai\"));")
&& arg.equals("vai")) return false;
else return true;
}}
Il metodo stops scritto sopra è un tentativo, ovviamente scorretto, di implementazione; esso stabilisce che se un metodo contenente l’istruzione while(s.equals(“vai”);
è applicato a una stringa suguale a “vai”, l’esecuzione non termina (il che può essere vero, ma …), altrimenti termina.
27/10/09 AlgELab-08-09 - Lez.17 20
Dimostrazione versione Java (continua)
Supponiamo che si possa raffinare stops fino a renderlo totalmente corretto.Allora potremmo definire, nella stessa classe, il metodo:
static void strano(String metod) { if(stops(metod, metod))
while(true); // ciclo infinito else return;
}
Ora diamo il nome stranoalla stringa costituita dal testo del metodo strano:
static String strano= “static void strano(String metod)”
+ “{if(stops(metod, metod)) while(true); else return;}”
Che cosa succede se invochiamo il metodo stranopassandogli come argomento la stringa strano, cioè il suo stesso testo ?
27/10/09 AlgELab-08-09 - Lez.17 21
Riassumendo, abbiamo la classe:
class HaltingProblem {
static boolean stops(String met, String arg) { }...
static void strano(String metod) { if(stops(metod, metod))
while(true);
while(true);
else return;
}static String strano= “static void strano(String metod) ” + “{if(stops(metod, metod)) while(true); else return;}”
public static void main(String[] a) { strano(strano);
}
27/10/09 AlgELab-08-09 - Lez.17 22
Dimostrazione (fine)
Eseguendo strano(strano)si va a eseguire la chiamata stops(strano, strano); se il metodo stopsè corretto:
• nel caso in cui strano, se applicato a se stesso, termina, la chiamata stops(strano, strano) restituisce true, e quindi il programma stranoentra nel loop infinito. Quindi:
se strano(strano)termina (perché l’ha determinato stops), allora strano(strano)non termina. Contraddizione ! allora strano(strano)non termina. Contraddizione !
• nel caso in cui strano, se applicato a se stesso, non termina, la chiamata stops(strano, strano) restituisce false, quindi il programma stranotermina. Quindi:
se strano(strano)non termina (perché l’ha determinato stops), allora strano(strano)termina. Contraddizione ! Quindi il metodo stopsnon può essere corretto !
27/10/09 AlgELab-08-09 - Lez.17 23
Note
Nella dimostrazione precedente (versione Java), per un rigore completo mancano alcuni dettagli. Ad esempio, occorre precisare che si deve assumere che il metodo static boolean stops(String met, String arg) {… } ammette come argomento il testo di un metodo che:
• non solo deve avere un’intestazione della forma static booleannomeMetodo(String x)
• ma deve anche compilare senza errori nella classe HaltingProblem.
27/10/09 AlgELab-08-09 - Lez.17 24
Turing, 1936
Indecidibilità del problema della fermata.
Una formulazione lievemente diversa ma equivalente.
Nelle slides seguenti si riporta una formulazione lievemente diversa del teorema e della sua dimostrazione, che ad alcuni potrà risultare più comprensibile, ad altri più difficile.
27/10/09 AlgELab-08-09 - Lez.17 25
Indecidibilità del problema della fermata
Teorema:Non può esistere un programma totalmente corretto che, dato un qualunque programma P e un input X per P, stabilisca se il programma P eseguito con input X termina oppure no.
La motivazione della nuova formulazione è il fatto che un
27/10/09 AlgELab-08-09 - Lez.17 26
programma parzialmente correttoper il problema della fermata è facilmente costruibile. Deve essere un programma che, quando termina, dà la risposta corretta al problema (ma in alcuni casi potrebbe non terminare).
Dimostreremo che un tale programma non può essere totalmente corretto, mostrando che ci deve essere almeno un caso in cui non termina.
Cioè non può esistere un programma Stops
totalmente corretto tale che:programma
programma P
possibile input X
per P
27/10/09 AlgELab-08-09 - Lez.17 27
non termina
p g
Stopsstampa “TERMINA” se X stampa
“
NONTERMINA se Xprogramma P programma
P
termina
Un programma Stops
parzialmente corretto.Un programma Stopsparzialmente corretto è un programma che prende come argomenti un programma P e un valore X (che sia un input legale per P), ed è tale che:
• se Stopsapplicato a Pe a Xproduce la risposta TERMINA, allora il programma P, se eseguito su X, termina;
• se Stopsapplicato a Pe a Xdà la risposta NONTERMINA, allora il programma P, se eseguito su X, non termina.
27/10/09 AlgELab-08-09 - Lez.17 28
allora il programma P, se eseguito su X, non termina.
Un tale programma Stopsè facilmente costruibile: basta che esso analizzi il programma determinando alcuni casi ovvi di non-terminazione e di terminazione, e in tutti gli altri casi semplicemente lanci l’esecuzione di Pstesso, stampando poi TERMINAalla fine dell’esecuzione di P(se Ptermina;
ovviamente se P non termina, non stamperà mai nulla …) .
Esempio Java
class Halt {static boolean termina(String metodo, String arg) throws Exception { if(metodo.contains(“while(true);”) && … && … ) {
System.out.println(“NON TERMINA”);
return false;
} else if else if …
…else {
Class[] paramTypes = {String.class};
Method m = Halt.class.getDeclaredMethod(
estraiNome(metodo), paramTypes);
m.invoke(null,arg);
System.out.println(“TERMINA”); return true;
}
Dimostrazione (continua)
Nota Bene: Un programma Stopscostruito come indicato nella slide precedente dà sempre la risposta giusta per P e X tali che P applicato a X termina (infatti in tal caso scrive TERMINA).
Allora ci poniamo la domanda:
è possibile raffinare il programma Stopsin modo che scopra tutti i possibili casi di non terminazione e quindi termini tutti i possibili casi di non-terminazione, e quindi termini sempre, scrivendo TERMINAoppure NONTERMINA? La risposta è NO.
(Di)mostriamo infatti che un tale programma Stopsnon può essere totalmente corretto, cioè non è possibile che dia la risposta corretta NONTERMINAper tutti i programmi che (su dati input) non terminano.
Dimostrazione
La dimostrazione si ottiene costruendo, per mezzo del programma Stopsstesso, una coppia programma-input per la quale StopsNON può dare la risposta corretta, proprio per come è costruito tale strano programma con il suo strano input … (vedi slides successive).
27/10/09 AlgELab-08-09 - Lez.17 31
Il programma S:
S
programmaprogramma P
programma
P programma
P
Il programma Screa una seconda copia di P, poi richiama Stopssu P e P:
•se Stopsdice che P applicato a P non termina, allora Stermina scrivendo anch’esso “NONTERMINA”;
•ma se Stopsdice che P applicato a P termina, allora Snon termina.
27/10/09 AlgELab-08-09 - Lez.17 32
S
output Stops
“NONTERMINA”
while(true) ;
“TERMINA” “NONTERMINA”
Come si comporta il programma S ?
Il programma S, eseguito con input un programma P, si comporta evidentemente nel modo seguente:• se Stopsscrive che Peseguito con input Pnon termina, allora anche Sscrive che Peseguito con input Pnon termina, e poi Stermina;
• se Stopsscrive che Peseguito con input Ptermina, allora Snon termina.
d l l
27/10/09 AlgELab-08-09 - Lez.17 33
Ora proviamo a dare in input al programma S il programma S stesso. Che cosa succede ? Basta sostituire P con S nella descrizione precedente:
• se Stopsscrive che Seseguito con input Snon termina, allora Scon input Stermina (scrivendo che S eseguito con input Snon termina);
• se Stopsscrive che Seseguito con input Stermina, allora Seseguito con input Snon termina.
Conclusione
• Se il programma Stopsscrivesse che S applicato a S “NON TERMINA”, in realtà S applicato a S terminerebbe, e quindi il programma Stopsnon sarebbe neppure parzialmente corretto.
• Se il programma Stopsscrivesse che S applicato a S
“TERMINA”, in realtà S applicato a S non terminerebbe, e
i di h i t il St bb
27/10/09 AlgELab-08-09 - Lez.17 34
quindi anche in questo caso il programma Stopsnon sarebbe parzialmente corretto.
• Quindi, se il programma Stopsè parzialmente corretto, non termina, e quindi non è totalmente corretto.
Altri problemi insolubili:
problemi la cui insolubilità si deduce d ll’i l bilità d l bl d ll f t dall’insolubilità del problema della fermata.
27/10/09 AlgELab-08-09 - Lez.17 35
Il problema della totalità (terminazione totale).
Teorema: Non può esistere un programma o procedura (o una macchina) AlwaysStopsche, dato un qualunque programma P, sia sempre in grado di determinare se il programma P termina per ogni possibile input Xoppure no.
Dimostrazione:
Se un tale AlwaysStops esistesse, allora sarebbe possibile costruire il programma o procedura Stops di cui abbiamo appena dimostrato l’impossibilità.
27/10/09 AlgELab-08-09 - Lez.17 36
Dimostrazione
Consideriamo il programma Stops(P, X) seguente:
• Prende il testo del programma Pe dell’input Xe genera il testo di un nuovo programma Qche:
•effettua un input che ignora, poi richiama Psu X;
• esegue il programma AlwaysStopssu Q;
• ne prende il risultato trueo falsee lo restituisce a sua volta come risultato; Q
Cioè, schematicamente:
Stops(P, X) = AlwaysStops(“read(Y); P(X)”) Si noti che il programma read(Y); P(X)
• termina per qualunque input Yse e solo se P(x)termina;
• non termina per nessun Yse e solo P(x)non termina.
Quindi se AlwaysStops“dice” che il programma read(Y); P(x) termina per qualunque y, automaticamente dice anche che P(x)termina, e realizza correttamente la funzione Stops.
27/10/09 AlgELab-08-09 - Lez.17 37
Dimostrazione (fine).
• Ma la funzione Stopsnon può esistere, quindi nemmeno la funzione alwaysStopspuò esistere.
27/10/09 AlgELab-08-09 - Lez.17 38
versione Java
Se, per assurdo, esistesse la procedura static booleanalwaysStops(String met) allora sarebbe possibile definire la procedura static booleanstops(String met, String arg) { String met2 = “static void nuovoMet(int Y) {“+ “System in read(); ” System.in.read();
+ estraiNome(met) + “(“ + arg + “) }” ; if(alwaysStops(met2)) return true else return false;
}
che risolverebbe il problema della fermata.
27/10/09 AlgELab-08-09 - Lez.17 39
Equivalenza di programmi su un particolare input.
Non può esistere un programma (o una macchina) Eq(P, Q, X) il quale, dati due qualsiasi programmi P eQ e un qualsiasi input X, sia sempre in grado di determinare se i due programmi Pe Q, eseguiti con input X, si comportano nello stesso modo (cioè terminano entrambi restituendo lo stesso risultato o entrambi non terminano) oppure no.
Dimostrazione:
Se un tale Eqqesistesse, allora applicandolo a una terna di pp argomenti data da:
1) un qualunque programma P,
2) un programma Q che non termina, ad es. della forma while(true),
3) un input X per P,
riusciremmo a stabilire se P non termina o termina per X, quindi risolveremmo il problema della fermata.
Dunque Eqnon può esistere.
27/10/09 AlgELab-08-09 - Lez.17 40
Importante problema insolubile:
equivalenza di programmi.
Non può esistere un programma Equiv(P, Q) il quale, dati due qualsiasi programmi P eQ, sia sempre in grado di stabilire se i due programmi Pe Qsono equivalenti(cioè se, per qualsiasi input X, i programmi Pe Qeseguiti con input Xrestituiscono lo stesso "risultato").
Dimostrazione:
Se un tale Equivesistesse, allora esisterebbe anche il programma AlwaysStops, di cui abbiamo appena dimostrato l’impossibilità:
AlwaysStops(P) = equiv(P’, P’’) dove P’è il programma read(x); P(x) ; return;
P’’ è il programma read(x); return;
Nota: a rigore, il programma P’ deve essere costruito in modo da “assorbire” gli eventuali output di P(x) verso l’esterno.
Nota
Ci sono molti altri problemi algoritmici insolubili (indecidibili).
Se chiamiamo “non banale” una proprietà degli algoritmi che sia posseduta da alcuni algoritmi ma non da tutti, allora:
data una proprietà non banale della relazione fra input e output degli algoritmi, il problema di stabilire se un dato algoritmo gode di quella proprietà è generalmente un problema insolubile (Teorema di Rice).
problema insolubile (Teorema di Rice).
L’uso di uno specifico linguaggio di programmazione non influisce sui risultati di indecidibilità (essi valgono su un qualunque modello di calcolo che formalizzi il comportamento di un computer con capacità di memoria illimitata).
Tutta questa materia sarà oggetto del corso di Fondamenti.
Inquadramento storico del risultato di Turing e sue conseguenze.
27/10/09 AlgELab-08-09 - Lez.17 43
Preliminari: richiami di logica.
• La lingua naturale in cui si esprime la matematica può venire sostituita da un linguaggio artificiale con sintassi rigida, come quella dei linguaggi di programmazione;
• tutte le regole puramente logiche del ragionamento corretto possono essere tradotte in un insieme di regole meccaniche (regole per la logica predicativa);
• ogni teoria matematica viene tradotta in un insieme di
27/10/09 AlgELab-08-09 - Lez.17 44
ogni teoria matematica viene tradotta in un insieme di assiomi e/o regole da aggiungersi alle regole logiche;
• ogni dimostrazione di un teorema può, in linea di principio, essere trascritta in una derivazioneformale, cioè in un
"calcolo" puramente meccanico in cui si applicano solo le regole logiche e le regole e assiomi della teoria;
• se esteso a tutti i campi del sapere e della vita, il metodo realizzerebbe l'ideale del "Calculemus !" di Leibnitz ...
David Hilbert, Königsberg, 8 settembre 1930
Für uns gibt es kein Ignorabimus, und meiner Meinung nach auch für die Naturwissenschaft überhaupt nicht. Statt des törichten Ignorabimusheiße im Gegenteil unsere Losung:
wir müssen wissen, wir werden wissen.
27/10/09 AlgELab-08-09 - Lez.17 45
traduzione:
Per noi non ci sono ignorabimus, e a mio parere anche nella scienza non ce n'è assolutamente nessuno. Invece dello sciocco ignorabimus, sia al contrario il nostro motto:
dobbiamo sapere, e sapremo.
Soluzione finale ?
Una volta individuato un insieme sufficientemente potente di assiomi per una teoria, tutti i problemi della teoria
avrebbero potuto essere risolti in linea di principio meccanicamente: una "soluzione finale" ai problemi della matematica ...
27/10/09 AlgELab-08-09 - Lez.17 46
Henry Poincaré, già nel 1905, ironizzava:
Ainsi c'est bien entendu, pour démontrer un théorème, il n'est pas nécessaire ni même utile de savoir ce qu'il veut dire. On pourrait remplacer le géomètre par le piano à raisonner imaginé par Stanley Jevons ; ou, si l'on aime mieux, on pourrait imaginer une machine où l'on introduirait les axiomes par un bout pendant qu'on recueillerait les théorèmes à l'autre bout, comme cette machine légendaire
27/10/09 AlgELab-08-09 - Lez.17 47
de Chicago où les porcs entrent vivants et d'où ils sortent g transformés en jambons et en saucisses. Pas plus que ces machines, le mathématicien n'a besoin de comprendre ce qu'il fait.
Henri Poincaré, « Les mathématiques et la logique » in Revue de Métaphysique et de Morale, 1905, p. 815-835
traduzione:
Dunque è chiaro, per dimostrare un teorema non è necessario e nemmeno utile sapere che cosa vuol dire. Si potrebbe rimpiazzare il "geométra" (cioè il matematico studioso di geometria) con il "pianoforte logico" immaginato da Stanley Jevons; o, se si preferisce, si potrebbe immaginare una macchina dove da una parte si introdurrebbero gli assiomi, e
27/10/09 AlgELab-08-09 - Lez.17 48
macchina dove da una parte si introdurrebbero gli assiomi, e dalla parte opposta si raccoglierebbero i teoremi: come in quella leggendaria macchina di Chicago dove i maiali entrano vivi ed escono trasformati in prosciutti e salsicce.
Il matematico non ha bisogno di sapere quello che sta facendo più di quanto ne abbiano queste macchine.
Kurt Gödel, 1930
Scrive il famoso articolo
"Über formal unentscheinbare Sätze der Principia Mathematica und verwandter Systeme I"
(Sulle proposizioni formalmente indecidibili dei Principia Mathematica e sistemi affini I")
27/10/09 AlgELab-08-09 - Lez.17 49
Come abbiamo visto, pochi anni dopo:
Turing, 1936
Indecidibilità del problema della fermata.
Teorema:
Non può esistere un programma (o una macchina) il quale, dato un qualunque programma P e un input X per P, sia sempre in grado di determinare se il programma P eseguito con input
27/10/09 AlgELab-08-09 - Lez.17 50
g m p g mm g p
X termina oppure no.
Conseguenze: incompletezza logica.
Assumiamo che si possa stabilire un insieme computabiledi assiomi di una teoria dei programmi che sia completo, cioè che permetta di dedurre, per qualunque proposizione della teoria, o la proposizione stessa o la sua negata, e che sia consistente(o coerente), cioè non permetta di dedurre una contraddizione (come una proposizione e la sua negata).
Allora si può scrivere un programma F il quale, dato un
P d l' l
27/10/09 AlgELab-08-09 - Lez.17 51
programma P e un input X, generi uno dopo l'altro tutti gl'infiniti teoremi della teoria, ad esempio in ordine crescente rispetto alla lunghezza della dimostrazione.
Poiché il sistema è completo, prima o poi F genererà o il teorema "P con input X termina", o il suo negato "P con input X non termina": ma così il programma F risolve il problema della fermata, il che abbiamo dimostrato essere impossibile !
Nota
• Un insieme di assiomi (e/o di regole di inferenza) si dice computabilese è un insieme finito oppure, nel caso sia infinito, se gli assiomi (e/o regole) sono generabili in modo meccanico, senza saltarne nessuno, da un programma (che ovviamente non termina).
27/10/09 AlgELab-08-09 - Lez.17 52
Turing e Gödel.
Un insieme computabile (i logici dicono effettivo) di assiomi consistente e completo per una teoria generale dei programmi non può esistere !
Ogni insieme di assiomi di una teoria dei programmi che sia effettivo e consistente non può essere completo: vi sarà sempre qualche proposizione tale che né essa né la sua negata sono derivabili dagli assiomi: cioè vi sarà sempre qualche proposizione indecidibile.
qualche proposizione indecidibile.
È una forma particolare del famoso primo teorema di Gödel, che in realtà riguarda qualunque insieme (effettivo) di assiomi (per un linguaggio aritmetico) da cui si possano derivare le usuali proprietà dell'addizione e della moltiplicazione.
Per questi argomenti vedi i testi di Logica, ad esempio:
Gabriele Lolli, Incompletezza, ed. Il Mulino
Sommario
• Per stabilire che un algoritmo non termina non si può semplicemente eseguirlo.
• Il problema della fermata è quello di trovare un algoritmo, anche se molto complicato, il quale sia in grado, dato un qualunque programma P e un input P per X, di determinare se P con input X termina.
• Si dimostra che un tale algoritmo non può esistere, cioè che Si dimostra che un tale algoritmo non può esistere, cioè che il problema della fermata è un
problema algoritmico insolubile.
• Una conseguenza di ciò è l'incompletezza, nel senso della logica, di ogni teoria assiomatica dei programmi.
