Le successioni di Goodstein: limiti pratici e limiti teorici dei calcolatori

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.