6 x 9 = 42

“Ho sempre detto che c’era qualcosa di fondamentalmente sbagliato nell’universo…” (Arthur Dent)

Numeri al Confine

Posted by scardax su novembre 9, 2008

NB: questo post é l’ideale continuazione del precedente Diagonalizzando.

I numeri sono una cosa alla quale siamo talmente abituati che spesso ci stupiamo di quanto a lungo se ne possa parlare, e quante cose interessanti ne escano. Numeri interi, frazioni, numeri reali, numeri complessi, immaginari, algebrici, veri e propri pilastri come pigreco… Ma possiamo veramente “conoscere” tutti i numeri?

Una domanda del genere ci lancia direttamente in uno dei campi più belli dell’Informatica, nato come molti altri dal genio del matematico Inglese Alan Turing (per la cui biografia mi riservo un prossimo post): quello dei numeri computabili, o calcolabili. Un numero viene detto computabile se, in maniera molto sintetica ed informale, possiamo scrivere un programma per computer che permetta di calcolarne le cifre decimali. A prima vista, potremmo pensare che quasi tutti i numeri reali siano computabili: del resto, lo sono i numeri razionali (quelli che si possono scrivere come una frazione del tipo m/n), e lo sono anche molti irrazionali come pigreco (per il quale esistono qualcosa come venti formule per calcolarne i decimali) o la radice quadrata di due.

Eppure, ecco la sorpresa: la maggior parte dei numeri reali sono… non calcolabili! Per dimostrarlo, partiamo dalla definizione che abbiamo dato prima: un numero calcolabile é un numero per il quale possiamo scrivere un programma che stampi su schermo le sue cifre decimali. Ora, i programmi per computer sono enumerabili, ovvero é possibile associare a ciascuno di essi un numero naturale che lo identifichi univocamente. Un modo per farlo é il seguente:

  1. Scriviamo il nostro programma in un qualche pseudolinguaggio (o anche un vero linguaggio di programmazione come il Java o il C).
  2. Il linguaggio sarà composto da un alfabeto di simboli finito: ad esempio le lettere dell’alfabeto, lo spazio, le parentesi graffe e qualche altro carattere speciale. Possiamo assegnare a ciascun simbolo un numero particolare (ad esempio il suo valore ASCII).
  3. Sostituiamo ogni simbolo del programma scritto in pseudolinguaggio con il valore associato: otterremo un numero naturale che lo identifica!

Facciamo un esempio con la stringa “Ciao mamma“: usando la tabella ASCII (in cui la A corrisponde a 97, lo spazio a 32 e cosi via) otteniamo il numerale “6710597111321099710910997”.

Poiché i programmi sono numerabili, e ad ogni numero calcolabile é associato un programma, ne segue che anche i numeri calcolabili sono numerabili: possiamo assegnargli ad esempio lo stesso numero che identifica il programma. Pero’, nell’articolo linkato ad inizio pagina abbiamo dimostrato che i reali non sono numerabili: se cerchiamo di identificarli con i naturali, possiamo ottenere facilmente un numero reale che non abbiamo considerato. Ne segue che la maggior parte dei numeri reali non sono calcolabili!

E questo é solo l’inizio del problema. Fra i numeri non calcolabili, possiamo distinguerne due categorie: quelli definibili (ovvero per i quali possiamo trovare un’espressione matematica che li identifichi, magari indirettamente) e quelli non definibili, ovvero che non possono neanche essere espressi con i termini matematici! Con un’argomentazione simile alla precedente possiamo dedurne che la maggior parte dei numeri reali sono non definibili:

  1. Un numero definibile é un numero identificato univocamente da una qualche formula matematica.
  2. L’insieme delle formule matematiche sono numerabili.
  3. I numeri definibili sono enumerabili, mentre i reali no: i numeri definibili sono un sottoinsieme neanche troppo grande dell’insieme dei Reali!

Ora, é chiaro che, se un numero del quale non possiamo calcolare le cifre decimali ma che possiamo comunque esprimere con una formula matematica puo’ essere utile in qualche ragionamento teorico, un numero che non é neanche esprimibile é, sostanzialmente, inutile!

In effetti, esiste una corrente matematica chiamata Costruttivismo che considera “veri” solo i numeri definibili. Ma é lecito approssimare i reali con i soli numeri definibili? E con questa domanda, concludo il post! 😀

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

 
%d blogger hanno fatto clic su Mi Piace per questo: