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

Hartmanis e Stearns (congettura di)

Algebra  Congetture  Teoria dell'informazione 

La congettura di Hartmanis e Stearns afferma che se per un numero irrazionale esiste un algoritmo capace di generare le cifre in tempo lineare (ovvero, capace di generare un numero di cifre proporzionale al numero di operazioni elementari eseguite), il numero è trascendente.

 

Nel calcolare il numero di passi si può supporre che ciascuna delle quattro operazioni abbia un “costo” unitario, ma solo per numeri fino a una dimensione prefissata (di solito si considera l’operazione sulla singola cifra come unità di misura). Ovvero, si possono per esempio sommare numeri di dimensione arbitrariamente grande, ma l’operazione costa un numero di passi proporzionale al numero di cifre (e per moltiplicazione e divisione la crescita del numero di passi rispetto alle cifre è anche più rapida).

 

I pochi algoritmi del genere noti permettono di generare solo alcuni esempi particolarmente semplici di numeri trascendenti, come il numero di Liouville, ma nessun numero irrazionale algebrico.

Sembra estremamente difficile dimostrare che l’esistenza di un algoritmo del genere implichi la trascendenza, anche se la congettura è molto plausibile.

 

Sfortunatamente non vale l’inverso, ovvero, non è detto che per ogni numero trascendente debba esistere un algoritmo capace di generare le cifre in tempo lineare, anzi, non si conoscono algoritmi del genere per i numeri trascendeti di maggior interesse. Persino l’algoritmo di David H. Bailey, Peter Benjamin Borwein e Simon Plouffe (v. π) permette di generare una singola cifra in un tempo che cresce più che linearmente con la posizione della cifra.

Vedi anche

Numeri trascendenti.

Contattami

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