![[copertina]](https://i0.wp.com/xmau.com/thumb/8850323611.JPG?w=625)
Ci sono cose che non possiamo fare, almeno in questo universo. In questo libro (A.K.Dewdney, La quadratura del cerchio [Beyond Reason], Apogeo, pag. VII-234, € 15, ISBN 8850323611, trad. Folco Claudi e Gianbruno Guerriero) il buon Dewdney ne espone alcune, più o meno equamente divise tra fisica e matematica. Troviamo così il moto perpetuo, il limite della velocità della luce, l’indeterminazione di Heisenberg, la teoria del caos per quanto riguarda la fisica; la quadratura del cerchio, l’indecidibilità gödeliana, il problema dell’halt di Turing, e i problemi non scalabili. Il testo è abbastanza scorrevole, tranne nel caso della dimostrazione di Gödel che però non sono mai riuscito a trovare in una formulazione chiara, comprensibile e memorizzabile. Diciamo però che mi sarei aspettato uno stile più frizzante: le battute degne di essere ricordate (per un matematico, che ha un sense of humour deviato) sono poche. In definitiva, testo divulgativo valido ma non eccezionale.
Ultimo aggiornamento: 2016-03-31 20:14
Capisco che non volevi essere troppo prolisso, ma da come hai scritto ciò che hai scritto sembrerebbe che la teoria del caos non si possa realizzare, al pari del moto perpetuo.
Quello che non si può fare è invece tenere sotto controllo gli errori che si compiono facendo previsioni sul moto nelle zone instabili dei sistemi caotici (e solo in quelle). In ogni caso si possono sempre fare previsioni statistiche, anzi, quelle vengono meglio tanto piú il moto è instabile.
Per esempio, il sistema solare è un sistema caotico, ma è lo stesso possibile effettuare con precisione previsioni a lungo termine sulle orbite dei pianeti perché il moto di rivoluzione è relativamente stabile, mentre avviene il contrario per la variazione dell’inclinazione dell’asse di rotazione dei pianeti.
Non so se a te sembra sufficiente, ma da quello che ho capito io, che non sono un matematico, la dimostrazione di Gödel avviene pressapoco cosí.
1) Si dia una teoria formale non contraddittoria che includa al suo interno l’aritmetica ordinaria (numeri interi, operazioni di somma e moltiplicazione, principio di induzione) e che usa un numero finito di simboli nella scrittura delle proprie formule.
2) Si elenchino i simboli utilizzati da tale teoria e li si interpretino come cifre di un sistema di scrittura per numeri interi, per esempio, se ci sono quaranta simboli si utilizzerà la base 40.
3) L’interpretazione del punto 2 associa a ciascuna formula esprimibile nella teoria un numero intero. Non a tutti i numeri interi corrisponderà una formula di senso compiuto.
4) Gli assiomi della teoria corrisponderanno a numeri interi che avranno la proprietà di essere “veri” per definizione, le regole di deduzione saranno tradotte in regole aritmetiche (esistenti ma non necessariamente note in forma esplicita) che a partire da un insieme di numeri (quindi di formule) già noti come “veri” o “falsi”, portano a decidere se altri numeri siano “veri” (corrispondenti a formule dimostrabili) o “falsi” (corrispondenti a formule refutabili).
5) Gödel, usando solo le regole di base dell’aritmetica, che sono contenute nella teoria per l’ipotesi (1), riesce a costruire esplicitamente un numero intero che corrisponde a una formula che dice di sé stessa di non essere dimostrabile tramite le regole citate al punto (4). Questa è la parte tecnica della dimostrazione che personalmente non sono in grado di seguire.
6) La formula non può essere refutabile, infatti in tal caso sarebbe anche dimostrabile, e la teoria sarebbe contraddittoria, contrariamente all’ipotesi (1). Allora è necessariamente “vera”, ma proprio per questo non è dimostrabile con le regole aritmetiche corrispondenti alle regole interne della teoria, che risulta dunque incompleta.
7) Siccome la formula è vera la si può aggiungere agli assiomi, ottenendo un’estensione “standard” della teoria di partenza. Siccome non è dimostrabile, si può anche (paradossalmente) aggiungere agli assiomi la sua negazione, ottenendo un’estensione “non standard”.
se proprio vogliamo mettere i puntini sulle iota :-) la teoria del caos afferma che esistono sistemi per cui una deviazione per quanto piccola dalle condizioni iniziali porterà a una differenza arbitrariamente grande (dove per “arbitrariamente” non intendo “all’infinito” ma semplicemente “tanto rispetto ai parametri del sistema”.
La dimostrazione di Gödel come logica la capisco, ma non sono mai stato capace a riuscire a rifarla da solo senza sbirciare.
Ciao .mau.
una dimostrazione semplice del teorema di Godel si puo’ fare come riduzione all’Halting problem, cioe`: se posso dimostrare tutto allora posso scrivere un programma che risolve il problema della fermata.
—————–Teorema di incompletezza di Godel—————————-
Sia un sistema deduttivo contenente:
– modus ponens
– un insieme di assiomi ricorsivo
se il sistema e` non contraddittorio ed in grado di per esprimere frasi
dell’aritmetica in logica del primo ordine(*) allora esistono affermazioni valide per cui non e’ dimostrabile ne’ la validita` ne la falsita`.
(*) le frasi dell’aritmetica in logica del primo ordine sono quelle del tipo:
“Per ogni numero X esiste un numero Y tale che per ogni numero Z esistono numeri W e V per cui e’ vera R(X,Y,Z,W,V)”
cioe’ le frasi composte da una relazione R su alcune variabili e da quantificatori “esiste” e “per ogni” che quantificano su variabili. R e’ una proposizione aritmetica su quelle variabili, tipo “X>Y e W+V*Z”
————————————————————-
Una nota sulle ipotesi:
Il modus ponens e’ quella regola che descrive il processo deduttivo. Ogni sistema deduttivo lo usa come passo di una dimostrazione. Il modus ponens e’ quindi necessario (ma anche sufficiente) come regola per passare da una o piu’ premesse ad una conseguenza. Poiche’ ogni altra regola di inferenza puo’ essere tradotta come applicazione del modus ponens, possiamo ridurci al caso che ci sia solo questo.
Gli assiomi devono essere ricorsivi: cioe` deve esistere una procedura computazionale che mi sa GARANTIRE se un’espressione codificata numericamente e’ un assioma o no. Questa ipotesi e` necessaria, perche’ se non fosse richiesta io potrei prendere come assiomi tutte le frasi valide e buona notte. Il sistema e’ in grado di dimostrarle tutte soltanto dichiarando “e` un assioma”. Sarebbe barare no?
Dalle ipotesi fatte discendono due semplici fatti:
1) Sia H(X,Y,t)=”la macchina di Turing X con input Y termina in t passi”
questa frase e’ esprimibile nell’aritmetica (dimostrarlo formalmente e’ noioso ed e’ tutto un gioco di codifica simile a quello fatto da Godel nell’articolo originale) quindi la frase H(X,Y)=”Esiste t tale che H(X,Y,t)” e’ esprimibile nell’aritmetica in logica del primo ordine. Quindi per ipotesi questa frase e’ esprimibile nel sistema di deduzione che stiamo analizzando.
Ma questa frase e’ proprio l’enunciato dell’Halting problem!!!
2) Tutte le dimostrazioni corrette nel sistema logico sono generabili da un programma. Farlo formalmente e’ un incubo, ma l’idea e’ ovvia. Ogni dimostrazione e’ di fatto un albero binario nel quale in ogni nodo e’ una frase del sistema logico. Alla radice c’e` il teorema dimostrato, mentre alle foglie ci sono gli assiomi. Ogni nodo interno e’ generato dai nodi sottostanti attraverso modus ponens.
Si puo’ verificare con un banale programma che la prova sia corretta: si verifica che le foglie siano assiomi e che il modus ponens sia stato applicato correttamente a tutti i passi risalendo lungo l’albero.
Queste prove possono essere codificate semplicemente come numeri in modo tale che ad ogni numero corrisponda solo una prova.
Quindi sia quindi il seguente tentativo di provatore automatico:
Dimostra(X):
Per N che va da 1 a infinito
Se N codifica una prova corretta che dimostra X restituisci “Vero”
Se N codifica una prova corretta che dimostra Not(X) restituisci “falso”
Questo programma trova SEMPRE una dimostrazione per X o per Not(X) se questa esiste. Visto che il sistema e` non contraddittorio la dimostrazione e’ corretta e quindi corrisponde al valore di verita` di X. Se invece questa dimostrazione non esiste allora il programma va avanti all’infinito.
————————–Colpo di grazia—————————
Se per assurdo assumiamo che l’enunciato del teorema di Godel sia falso allora ogni frase F libera da variabili (quindi sempre vera o sempre falsa) ha una dimostrazione o una dimostrazione della sua negazione.
Ma allora se fissiamo una macchina di Turing M e un input s la frase H(M,s) e` libera da variabili e quindi o e` vera o e` falsa. Percio` Dimostra(H(M,s)) restituisce “Vero” se M si ferma con input s o falso se M non termina.
Ma allora abbiamo scritto un programma finito che termina sempre e che risolve correttamente il problema della fermata!!!!! La CONTRADDIZIONE e` dovuta al fatto che abbiamo supposto la completezza del sistema logico sull’aritmetica.
Spero che questa dimostrazione ti sia piu’ utile, perche’ al contrario di quella di Godel questa isola le parti di codifica e quelle di diagonalizzazione. Qui rimane la codifica, mentre la diagonalizzazione e’ “implicita” nel fatto che diamo per scontato che il problema della fermata non sia decidibile.
Oltretutto questa prova mette in luce che (a meno di tremende inefficienze di calcolo) la “calcolabilita`” e la “dimostrabilita`” sono piu’ o meno la stessa cosa.
> la teoria del caos afferma che esistono sistemi per cui una deviazione per quanto piccola dalle condizioni iniziali porterà a una differenza arbitrariamente grande
Condizione necessaria, ma non sufficiente per avere un sistema “caotico”
Infatti non tutti i sistemi esponenzialmente instabili sono caotici, p. es. il moto libero su alcune superfici infinite a curvatura negativa è integrabile, dunque conoscibile in linea di principio con precisione arbitraria.
In tal caso le orbite si allontanano esponenzialmente, ma non si “mischiano” tra loro in modo complesso.
Per avere un sistema “caotico” occorre anche che le orbite non possano allontanarsi indefinitamente, ma siano costrette a riavvicinarsi a causa di caratteristiche “globali” del moto, quale il confinamento in una regione finita dello spazio delle fasi.