Marco Mattiucci
Email me
2024-12-11 00:14:48
Una regola che è seguita da pochi ha poco senso come regola.
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.
Cookie(s) & Privacy
Questo sito web, per quanto da me programmato e realizzato in php, non emette cookie, non effettua il profiling dell'utente e non raccoglie vostri dati personali. Alcuni cookie possono essere emessi dal cloud che lo supporta, strumento al di fuori della possibilità di controllo dello scrivente. Per qualsiasi dubbio in proposito smettete immediatamente la navigazione.marcomattiucci.it
Matematica:
- Home(Matematica)
- Th. di Godel
- "The halting problem"
- I Numeri Naturali N
- I Numeri Razionali Q
- La Logica
- I Numeri Irrazionali
- I Numeri Reali R
- I Numeri Transfiniti
- I Numeri Algebrici A
- I Numeri Computabili
- I Numeri Trascendenti
- I Numeri Complessi C
- La funzione exp(x)
- Num. di Eulero
- 2n n positivo
- 2n n negativo
- I Vettori(...)
- Le Matrici(...)
- Le Relazioni(...)
- Le Funzioni(...)
- I Funzionali(...)
- Gli Insiemi(...)
- Le Sequenze(...)
- I Grafi(...)
- (working-on)