Programmazione.it v6.2
Ciao, per farti riconoscere devi fare il login. Non ti sei ancora iscritto? Che aspetti, registrati adesso!
Info Pubblicità Collabora Autori Sottoscrizioni Preferiti Bozze Scheda personale Privacy Archivio Libri Corsi per principianti Chat Forum
Il numero di Gödel
Scritto da Mario Rossi il 08-10-2009 ore 12:24
Intel Software
Il sistema di compressione di dati più efficiente in assoluto è la godelizzazione, anche se purtroppo, al momento, non è utilizzabile: essa consente di trasformare qualsiasi produzione di un linguaggio formale in un unico numero, detto appunto numero di Gödel per tale input.

Questo sistema è talmente efficiente da consentire di memorizzare l'intero contenuto della Bibbia in un unico numero: quest'ultimo però deve essere alquanto grande ed è talmente complesso da calcolare, persino con gli attuali elaboratori, da non poter essere ancora ottenuto.

Benché l'algoritmo operi su numeri interi, la difficoltà nasce dalla necessità di usare milioni di cifre di precisione numerica, intesa come numero di cifre significative. Messo a punto dal matematico Kurt Gödel, il sistema di codifica e decodicfica dei dati in sé è relativamente semplice.

Si considerano sequenzialmente i singoli caratteri del documento (o byte del file) da codificare e la sequenza dei numeri primi naturali a partire dal 2. Ciascun byte, o il valore ASCII di ciascun carattere, o ciascun elemento della sequenza, verrà usato come esponente del numero primo corrispondente, e tutti tali valori andranno moltiplicati tra di loro.

Supponiamo di voler codificare la sequenza formata dai valori 4, 1 e 2. Il primo valore sarà l'esponente del primo numero primo, quindi 24=16. Il secondo valore eleverà il secondo numero primo: 31 = 3. I valori successivi vengono usati come esponenti dei numeri primi successivi: 52=25. In fine tutti questi valori vengono moltiplicati tra loro: 16x3x25=1200. In questo caso 1200 è la rappresentazione godelizzata della sequenza 4, 1, 2.

Poiché il numero trovato tenderà a essere molto elevato, si potrà memorizzarlo o trasmetterlo come somma o differenza di altre potenze, come ad esempio: 2113717811-216. Il sistema è decisamente ingegnoso ed è un vero peccato che la tecnologia non sia ancora in grado di sfruttarlo.
Precedente: Una falla nel sistema di autodistruzione dei dati
Successiva: Jamorea, gestione di file PDF per dispositivi mobili
Intervento di Roberto Della Fornace a.k.a. lambis del 08-10-2009 ore 22:03, Ardea (RM)
Plebeo
Plebeo
(2 interventi)
Iscritto il 23-10-2007
sarà perché non si conosco sufficienti numeri primi??? :P
Intervento di Peppe Berello a.k.a. berello del 16-10-2009 ore 18:14, Roma (RM)
Plebeo
Plebeo

(5 interventi)
Iscritto il 14-05-2001
lambis ha scritto:
sarà perché non si conosco sufficienti numeri primi??? :P

In realtà il motivo è un altro: si può dimostrare (e anche piuttosto facilmente: cerca il "principio della piccionaia" o "dei cassetti" su Wikipedia) che non è possibile comprimere qualsiasi dato della quantità che si vuole.

Ogni informazione, attraverso l'elaborazione, può essere più o meno compressa, ma mai oltre un valore. Ho letto (ma non conosco l'argomento) che tale limite di compressione è collegato all'entropia del segnale (cioè dell'informazione che si vuole comprimere). Al di sotto di quel valore non si può scendere, indipendentemente dall'algoritmo usato.

Buona giornata!
Intervento di Lorenzo C a.k.a. lorenzoc del 16-10-2009 ore 23:47, Roma (RM)
Plebeo
Plebeo
(5 interventi)
Iscritto il 03-09-2009
Non capisco in che senso la godelizzazione sia un meccanismo "efficiente" per rappresentare dei dati... A me sembra il meccanismo meno efficiente!!

E` vero che la Bibbia puo` essere rappresentata da un solo numero naturale attraverso una opportuna codifica, la godelizzazione appunto, ma poi il numero di Goedel della Bibbia sara` cosi` grande da richiedere piu` spazio della Bibbia stessa per essere memorizzato!

(PS: Penso che quando si parla di efficienza di uno schema di codifica, non abbia senso considerare singole istanze, ma solo classi infinite di esempi.)
Intervento di Roberto Della Fornace a.k.a. lambis del 18-10-2009 ore 17:44, Ardea (RM)
Plebeo
Plebeo
(2 interventi)
Iscritto il 23-10-2007
lorenzoc ha scritto:
Non capisco in che senso la godelizzazione sia un meccanismo "efficiente" per rappresentare dei dati... A me sembra il meccanismo meno efficiente!!

E` vero che la Bibbia puo` essere rappresentata da un solo numero naturale attraverso una opportuna codifica, la godelizzazione appunto, ma poi il numero di Goedel della Bibbia sara` cosi` grande da richiedere piu` spazio della Bibbia stessa per essere memorizzato!

(PS: Penso che quando si parla di efficienza di uno schema di codifica, non abbia senso considerare singole istanze, ma solo classi infinite di esempi.)

Si lorenz ma rappresentato come esponente fattoriale (come scritto nell'articolo) non rappresenta una grande occupazione di memoria. :P
Intervento di Lorenzo C a.k.a. lorenzoc del 18-10-2009 ore 18:09, Roma (RM)
Plebeo
Plebeo
(5 interventi)
Iscritto il 03-09-2009
lambis ha scritto:
lorenzoc ha scritto:
Non capisco in che senso la godelizzazione sia un meccanismo "efficiente" per rappresentare dei dati... A me sembra il meccanismo meno efficiente!!

E` vero che la Bibbia puo` essere rappresentata da un solo numero naturale attraverso una opportuna codifica, la godelizzazione appunto, ma poi il numero di Goedel della Bibbia sara` cosi` grande da richiedere piu` spazio della Bibbia stessa per essere memorizzato!

(PS: Penso che quando si parla di efficienza di uno schema di codifica, non abbia senso considerare singole istanze, ma solo classi infinite di esempi.)

Si lorenz ma rappresentato come esponente fattoriale (come scritto nell'articolo) non rappresenta una grande occupazione di memoria. :P

beh ma se la metti cosi`, allora che lo codifichi a fare?
una codifica ha senso se e` semplice effettuare operazioni elementari sui dati codificati..
se rappresenti i numeri di Goedel in maniera implicita ("esponente fattoriale", come scritto nell'articolo), diventa assai difficile fare aritmetica con questi numeri, ovvero diventa difficile manipolarli per quello che sono: quantita` numeriche.

tanto vale avere la Bibbia in formato ASCII!

mi sembra di non aver colto il punto fondamentale di questo articolo...
qual'e` il vantaggio di una codifica numerica stile Goedel?

Mario: perche` dici che e` un peccato che le tecnologie attuali non lo sfruttino?
come potrebbero sfruttarlo in maniera utile?

:)
Intervento di Andrea Chiarelli a.k.a. andreachiarelli del 02-11-2009 ore 16:47
Plebeo
Plebeo
(9 interventi)
Iscritto il 28-10-2008
Riportiamo il numero di Goedel al suo ambito originario: un meccanismo per identificare univocamente un enunciato in un sistema logico ed utilizzato per la dimostrazione dei suoi teoremi di incompletezza.

Ai fini pratici il numero di Goedel è praticamente inutilizzabile.
Intervento di Lorenzo C a.k.a. lorenzoc del 02-11-2009 ore 23:01, Roma (RM)
Plebeo
Plebeo
(5 interventi)
Iscritto il 03-09-2009
andreachiarelli ha scritto:
Riportiamo il numero di Goedel al suo ambito originario: un meccanismo per identificare univocamente un enunciato in un sistema logico ed utilizzato per la dimostrazione dei suoi teoremi di incompletezza.

Ai fini pratici il numero di Goedel è praticamente inutilizzabile.

Condivido, grazie per la sintesi : )
Copyright Programmazione.it™ 1999-2009. Alcuni diritti riservati. Testata giornalistica iscritta col n. 569 presso il Tribunale di Milano in data 14/10/2002. Pagina generata in 0.733 secondi. Sito ottimizzato per Mozilla Firefox. Powered by Kyron.