SeminarioBernardi2001 < Commissioni/Scientifica

---+++ 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.

[[%ATTACHURL%/SeminarioBernardiLucidi.doc][Lucidi]],
[[%ATTACHURL%/SeminarioBernardiCalcoli.doc][Calcoli]].

This topic: Commissioni/Scientifica > WebHome > SeminariDivulgativi > SeminarioBernardi2001
Topic revision: r2 - 2004-02-05 - AlessandroMei