Il compito di comprimere i dati nella sua forma più semplice può riguardare i numeri e le loro denominazioni. I numeri possono essere rappresentati con numerali («undici» per il numero 11), espressioni matematiche («due elevato alla ventesima» per 1048576), espressioni testuali («cinque nove» per 99999), nomi propri («numero della bestia» per 666, «anno della morte di Turing» per 1954), o combinazioni arbitrarie di essi. È accettabile qualsiasi denominazione che permetta al tuo interlocutore di identificare inequivocabilmente di quale numero si sta parlando. È chiaro che comunicare all'interlocutore «fattoriale di otto» è più efficiente che utilizzare la denominazione equivalente «quarantamila trecentoventi». Qui sorge una domanda logica: qual è la denominazione più breve per un dato numero?
Il filosofo Bertrand Russell nel 1908 pubblicò , che tocca la questione delle denominazioni dei numeri da un'altra prospettiva: qual è il numero più piccolo per cui non bastano ottanta lettere per rappresentarlo?
Un tale numero deve esistere: con ottanta lettere russe e spazi possiamo formare solo 3480 denominazioni, quindi usando ottanta lettere si possono rappresentare al massimo 3480 numeri. Pertanto, non è possibile rappresentare un numero che sia superiore a 3480 in questo modo.
Pertanto, a questo numero corrisponderà la denominazione «il numero più piccolo per cui non bastano ottanta lettere», che contiene solo 78 lettere! Da un lato, questo numero deve esistere; dall'altro, se questo numero esiste, la sua denominazione non gli corrisponde. Paradossale!
Il modo più semplice per ignorare questo paradosso è fare riferimento all'informalità delle denominazioni verbali. Come se, se nelle denominazioni si ammesso solo un insieme di espressioni specificamente definite, allora «il numero più piccolo per cui non bastano ottanta lettere» non sarebbe una denominazione valida, mentre denominazioni praticamente utili come «fattoriale di otto» resterebbero valide.
Esistono metodi formali per descrivere la sequenza (algoritmo) di operazioni sui numeri? Sì, e in abbondanza — li chiamiamo linguaggi di programmazione. Invece delle denominazioni verbali, utilizzeremo i programmi (ad esempio, in Python) per ottenere i numeri necessari. Ad esempio, per cinque nove è adatta la seguente programma print("9"*5). Continueremo a interessarci al programma più breve per un numero dato. La lunghezza di tale programma viene chiamata del numero; questo è il limite teorico fino al quale un numero dato può essere compresso.
Invece del paradosso di Berry, ora possiamo considerare un analogo: qual è il numero più piccolo per il quale non è sufficiente un programma di chilobyte?
Ragioneremo come prima: ci sono 2561024 testi di chilobyte, quindi con i programmi di chilobyte si possono generare al massimo 2561024 numeri. Pertanto, un certo numero, non maggiore di 2561024, non può essere generato in questo modo.
Ma scriveremo un programma in Python che genera tutti i possibili testi di chilobyte, li esegue e, se producono un certo numero, allora aggiunge questo numero a un dizionario di quelli raggiungibili. Dopo aver verificato tutte le 2561024 possibilità, qualunque sia il tempo necessario—il programma cerca qual è il numero più piccolo assente nel dizionario e lo restituisce. Sembra ovvio che tale programma rientrerà in un chilobyte di codice e produrrà proprio quel numero che non può essere generato da un programma di chilobyte!
Qual è dunque l'inghippo adesso? Non è più possibile attribuire la non formalità delle notazioni!
Se ti preoccupa che il nostro programma richiederà una quantità astronomica di memoria per funzionare—un dizionario (o un array di bit) di 2561024 elementi—si può fare esattamente la stessa cosa anche senza di esso: per ciascuno dei 2561024 numeri, esaminare uno dopo l'altro tutti i 2561024 possibili programmi, finché non si trova quello giusto. Non importa che tale ricerca richiederà molto tempo: dopo aver verificato meno di (2561024)2 coppie di numero e programma, essa terminerà e troverà quel prezioso numero.
O non terminerà? Infatti, tra tutti i programmi che verranno testati, ci sarà while True: pass (e i suoi analoghi funzionali)—e da quel momento in poi il controllo di tale programma non andrà avanti!
A differenza del paradosso di Berry, dove l'inghippo era nella non formalità delle notazioni, nel secondo caso abbiamo una riformulazione ben mascherata Il fatto è che non è possibile determinare il suo output per un programma in un tempo finito. In particolare, la complessità colmogoroviana : non esiste alcun algoritmo che consenta di trovare, per un dato numero, la lunghezza del programma più corto che produce quel numero; quindi, non esiste soluzione nemmeno per il problema di Berry — trovare, per un dato numero, la lunghezza della più breve rappresentazione verbale.
Fonte: habr.com
