Le successioni di Goodstein: limiti pratici e limiti teorici dei calcolatori
Prof. Claudio Bernardi, Dipartimento di Matematica, Università di Roma "La Sapienza".
Abstract
Ci sono calcoli che, pur coinvolgendo solo numeri naturali, sono
talmente complessi che mettono in difficoltà anche i recenti
calcolatori. Un esempio è dato dalle successioni di Goodstein: si
tratta di successioni di numeri naturali che crescono così rapidamente
che riusciamo ragionevolmente a scriverne solo i primi 4 o 5
termini. Tuttavia, Goodstein ha dimostrato che... le cose non vanno
affatto come sembra. La cosa strana è che la dimostrazione del
teorema di Goodstein coinvolge i numeri infinitamente grandi (numeri
tali che ciascuno di essi esprime una quantita' infinita), anche se
l'enunciato riguarda i numeri naturali. Negli anni '80 Kirby e Paris
hanno dimostrato che il ricorso all'infinito è inevitabile. Più
precisamente, abbiamo a che fare con una funzione che è computabile,
per ogni valore di n, da una macchina finita (purché disponga di
memoria e tempo in quantità adeguata!); ma se ci limitiamo ai numeri
naturali non riusciamo a dimostrare che la nostra macchina fornisce
davvero un risultato per ogni
n. La situazione presenta stretti
legami con il I teorema di incompletezza di Gödel, secondo cui
esistono formule vere per i numeri naturali che non si dimostrano
nelle usuali teorie per l'aritmetica.
Lucidi,
Calcoli.