MATEMATICA - NUMERI COMPUTABILI

Riconducibile a Minsky ed equivalente a quella di Turing, la definizione di numero computabile è la seguente: “un numero computabile è un numero per il quale esiste una macchina di Turing che, dato un intero n inizialmente presente sul nastro, termina l’esecuzione in un numero finito di passi, con la cifra n-esima scritta sul nastro”. In altre parole un numero computabile è un numero reale che può essere calcolato con una precisione arbitraria da un programma di lunghezza finita su un computer (più genericamente su una macchina di Turing).

Turing ha dimostrato che tutti i numeri algebrici (le soluzioni di equazioni polinomiali) sono computabili. Sono poi computabili molti numeri irrazionali non algebrici (detti trascendenti) come il numero di nepero e, il pi-greca, ecc. Dato poi che qualsiasi programma della macchina di Turing è associabile biunivocamente ad un numero intero (grande a piacere) va da sè che l'insieme di tutti i programmi costruibili è numerabile, da cui anche l'insieme dei numeri computabili è numerabile. L'implicazione di questo è notevole: dato che R ha una cardinalità superiore al numerabile esistono infiniti numeri reali non computabili, nemmeno di principio... questo significa, per ribadire il concetto, che esistono numeri reali per i quali non è possibile conoscerli nemmeno stabilendo un'approssimazione plausibile!

I numeri computabili hanno poi altre interessanti caratteristiche: considerati x ed y numeri computabili, la relazione di identità x=y non è computabile in assoluto, ossia non può esistere una macchina di Turing che decide sempre il valore di verità di tale asserzione, per qualsiasi x ed y. Ai programmatori di lunga data è infatti ben nota la regola di chiudere i cicli di ripetizione dei programmi con ">" o "<" e mai con un "=" perchè si rischia di non uscire mai dal loop.

marcomattiucci.it

Matematica: