Macchina Gödel-incompleta
Per macchina Gödel-incompleta si intende una macchina che può operare quanto si reputa necessario, la quale può emettere su un proprio nastro illimitatamente estendibile (in breve: può stampare) stringhe interpretabili come affermazioni sul proprio comportamento, sapendo distinguere entro queste le affermazioni vere.
Diamo un esempio proposto da Raymond Smullyan.
Chiamiamo M una macchina del genere della macchina di Turing in grado di stampare su nastri illimitati stringhe sull'alfabeto di cinque simboli A = {~ ,P ,E , ( , )}. Chiediamo che M possieda la capacità di passare in rassegna tutte le stringhe su A (ad es. secondo l'ordinamento lunghezza crescente-lessicografico).
Diciamo estensione di una stringa W su A la stringa su A della forma W(W). Interessano particolari stringe su A che diciamo autosentenze e una loro interpretazione che le considera affermazioni sul comportamento della stessa M, come indicato nel seguente quadro:
- P(W) la stringa W è stampabile;
- PE(W) l'estensione della stringa W è stampabile;
- ~P(W) la stringa W non è stampabile;
- ~PE(W) l'estensione della stringa W non è stampabile.
Alle autosentenze si può attribuire una valutazione booleana nel modo seguente:
- P(W) è vera se W è stampabile, è falsa altrimenti;
- PE(W) è vera se W(W) è stampabile, è falsa altrimenti;
- ~P(W) è vera se W non è stampabile, è falsa altrimenti;
- ~PE(W) è vera se W(W) non è stampabile, è falsa altrimenti.
Si chiede anche che M possegga dispositivi che le consentano di distinguere le autosentenze vere dalle false. Questa richiesta è resa lecita dal fatto che M è in grado di procedere nella stampa di tutte le stringhe stampabili, ovvero dal fatto che il problema della stampabilità o meno delle stringhe su A è decidibile. Dunque si può chiedere che la macchina M proceda a stampare, oltre alle stringhe non autosentenze stampabili, tutte le autosentenze vere e non le false.
Esaminiamo ora la autosentenza G := "~PE(~PE)".
La G è vera se e solo se l'estensione della "~PE" non è stampabile. Ma questa estensione è la stessa G, quindi la G è vera se e solo se non è stampabile. Dunque aut la G è vera e non stampabile, aut è stampabile e falsa. Ma la seconda alternativa viola la non stampabilità delle autosentenze false. In conclusione G deve essere vera, ma non può essere stampata.
Si osserva anche che la autosentenza "PE(~PE)", negazione della precedente, deve essere falsa e neppure essa può essere stampata. Essa costituisce un esempio di stringa indecidibile per la M, in quanto né essa né la sua negazione possono essere stampate.
La macchina introdotta si può pensare come un caso particolarmente semplice di sistema formale dotato di una certa capacità di riflettere sul proprio comportamento e in grado di dimostrare talune sentenze formulate mediante i 5 simboli dell'alfabeto A. Ora la lettera P va interpretata con l'attributo "dimostrabile" e la stringa "~PE(~PE)" costituisce una autosentenza vera che nel sistema formale non può essere dimostrata.
La macchina introdotta fornisce quindi una traccia per la comprensione del teorema di incompletezza di Gödel.
Essa inoltre, forse, può essere considerata un esempio di limitazione della autoconsapevolezza di un sistema.
Bibliografia[modifica | modifica wikitesto]
- (EN) Raymond M. Smullyan, Gödel's Incompleteness Theorems, Oxford University Press, 1992, ISBN 0-19-504672-2. URL consultato l'11 novembre 2012.
