Don't take life too seriously: it's just a temporary situation

Computabili (numeri)

Teoria dell'informazione  Vari 

Si dicono “computabili” i numeri reali che possono essere calcolati con precisione arbitraria da un programma di lunghezza finita.

Possono essere definiti in modo equivalente formalizzando un algoritmo per calcolarli tramite funzioni ricorsive, macchine di Turing o lambda calcolo.

 

Il concetto fu introdotto da Turing nel 1936 e prescinde dai dettagli del linguaggio di programmazione e del calcolatore impiegato. Possiamo usare il linguaggio che preferiamo e la macchina che vogliamo: cambierà la velocità del calcolo, non il risultato, perché è possibile dimostrare che qualsiasi coppia di calcolatore e linguaggio equivale a una macchina di Turing, nel senso che le due macchine possono produrre gli stessi risultati.

 

La definizione di Minsky, equivalente a quella di Turing, è: “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”. La base di rappresentazione è irrilevante: possiamo prendere quella che vogliamo, perché comunque, data la macchina di Turing di partenza, possiamo costruirne un’altra che generi abbastanza cifre nella base nella quale lavora, poi le converta in un’altra base.

 

La definizione moderna si basa invece sulla generazione delle cifre del numero, sino a una precisione richiesta, per evitare sottili problemi posti dall’arrotondamento di funzioni trascendenti. Fissato n > 0, si richiede quindi la generazione di un intero k tale che Definizione dell'approssimazione di n, dove x è il numero desiderato.

 

Esistono anche varie altre definizioni equivalenti, ma quale che sia la definizione adottata, il principio base è sempre la generazione di una sequenza potenzialmente infinita di cifre da parte di una macchina con un numero finito di stati o di un programma con un numero finito di istruzioni.

 

Turing mostrò come calcolare le radici di un polinomio, e quindi tutti i numeri algebrici, con programmi di lunghezza finita. Per i numeri irrazionali il calcolo può procedere generando le cifre una dopo l’altra, fino alla precisione desiderata.

I numeri computabili includono quindi i numeri algebrici e infiniti numeri trascendenti (per esempio, π può essere calcolato con precisione arbitraria con programmi relativamente semplici). I programmi di lunghezza finita sono però un’infinità numerabile, quindi la maggior parte dei numeri reali non è computabile: l’unico modo per esprimerli o anche solo approssimarli con precisione arbitraria è tramite una sequenza infinita e non periodica di cifre.

 

Un tipico esempio di numero non computabile è la costante di Chaitin Ω.

 

La definizione si estende facilmente ai numeri complessi: i numeri complessi sono computabili se sono computabili sia la parte reale che quella immaginaria.

 

I numeri computabili formano un campo reale chiuso rispetto alle quattro operazioni, all’estrazione di radice e all’elevamento a potenza, ma non hanno tutte le proprietà dei numeri reali.

Per cominciare, non si può definire una relazione d’ordine computabile, nel senso che non può esistere alcuna macchina di Turing che data la descrizione degli stati di una qualsiasi macchina T che calcola il numero x, stabilisca in un numero finito di passi se x > 0.

Per lo stesso motivo la relazione x = y non è computabile. Non è decidibile in un numero finito di passi il problema di stabilire se due numeri definiti tramite due diversi algoritmi siano uguali.

Viceversa è computabile la relazione x > y, ma solo se è noto a priori che i due numeri sono differenti.

Un’altra importante differenza è che il minimo limite superiore di una sequenza crescente di reali computabili non è necessariamente computabile. Una sequenza con questa stravagante proprietà è nota come “sequenza di Specker”, perché Ernst Specker ne costruì il primo esempio nel 1949: dato un insieme di numeri naturali distinti an, ricorsivamente enumerabile ma non decidibile, la sequenza qn, definita come Definizione del termine n-esimo della sequenza, è formata da numeri razionali positivi, è crescente e limitata (perché Limite superiore per i valori della sequenza), ma il minimo limite superiore non è computabile. La dimostrazione si basa sul fatto che se tale limite fosse computabile, si potrebbe costruire una funzione r(n) tale che Limite superiore per il valore assoluto della differenza tra due valori della sequenza per tutti i valori di n e m maggiori di r(n) e questo permetterebbe di definire una procedura di decisione per l’insieme, che per ipotesi non è decidibile, tramite un numero finito di approssimazioni successive.

Vedi anche

Numero di Chaitin.

Bibliografia

  • Chaitin, Gregory;  Metamaths, Londra, Atlantic Books, 2007.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.