Tags:
create new tag
view all tags

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.

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2004-02-05 - AlessandroMei






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback