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.


This topic: Commissioni/Scientifica > WebHome > SeminariDivulgativi > SeminarioBernardi2001
Topic revision: r2 - 2004-02-05 - AlessandroMei
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback