Il problema della compressione dei dati, nella sua forma più semplice, può riguardare numeri e le loro rappresentazioni. I numeri possono essere rappresentati con numerali ("undici" per il numero 11), espressioni matematiche ("due alla ventesima" per 1048576), espressioni stringa ("cinque nove" per 99999), nomi propri ("numero della bestia" per 666, "anno della morte di Turing" per 1954), o combinazioni arbitrarie di essi. Qualsiasi rappresentazione che consenta all'interlocutore di identificare senza ambiguità di quale numero si parla è valida. È evidente che comunicare all'interlocutore "fattoriale di otto" è più efficace rispetto alla rappresentazione equivalente "quarantamila trecentoventi". Qui sorge una domanda logica: qual è la rappresentazione più breve per un dato numero?
Il filosofo Bertrand Russell pubblicò nel 1908 , che affronta il problema delle rappresentazioni dei numeri da un'altra prospettiva: qual è il numero più piccolo per il quale non sono sufficienti ottanta lettere?
Un tale numero deve esistere: con ottanta lettere russe e spazi è possibile formare solo 3480 rappresentazioni, quindi utilizzando ottanta lettere è possibile rappresentare non più di 3480 numeri. Pertanto, esiste un certo numero, non superiore a 3480, che non può essere rappresentato in questo modo.
Pertanto, a questo numero corrisponderà la rappresentazione "il numero più piccolo per il quale non sono sufficienti ottanta lettere", che consiste di sole 78 lettere! Da una parte, questo numero deve esistere; dall'altra, se questo numero esiste, la sua rappresentazione non gli corrisponde. Paradosso!
Il modo più semplice per ignorare questo paradosso è richiamare l'informalità delle rappresentazioni verbali. Dunque, se nelle rappresentazioni fosse ammesso solo un insieme specifico di espressioni, allora "il numero più piccolo per il quale non sono sufficienti ottanta lettere" non sarebbe una rappresentazione valida, mentre rappresentazioni pratiche come "fattoriale di otto" rimarebbero valide.
Esistono metodi formali per descrivere una sequenza (algoritmo) di azioni sui numeri? Sì, e in abbondanza — si chiamano linguaggi di programmazione. Useremo invece le rappresentazioni testuali programmi (ad esempio, in Python) che producono i numeri desiderati. Ad esempio, per cinque nove si adatta il programma print("9"*5). Continuiamo a cercare il programma più breve per un dato numero. La lunghezza di tale programma si chiama del numero; è il limite teorico fino a cui un dato numero può essere compresso.
Invece del paradosso di Berry, ora possiamo considerare un paradosso analogo: qual è il numero più piccolo per il quale non è sufficiente un programma da un kilobyte?
Razionalizzeremo esattamente come prima: esistono 2561024 testi di un kilobyte, quindi con programmi da un kilobyte si possono generare non più di 2561024 numeri. Pertanto, esiste un certo numero, non superiore a 2561024, che non può essere prodotto in questo modo.
Ma scriviamo un programma in Python che genera tutti i possibili testi di un kilobyte, li esegue e, se producono un certo numero, lo aggiunge a un dizionario di risultati raggiungibili. Dopo aver controllato tutte le 2561024 possibilità, indipendentemente dal tempo che ci vorrà, il programma cerca quale sia il numero più piccolo assente nel dizionario e lo produce. Sembra ovvio che un tale programma rientrerà in un kilobyte di codice — e produrrà quel numero che non è possibile generare con un programma di un kilobyte!
Qual è, quindi, la trappola ora? Non si può più liquidare l'informalità delle rappresentazioni!
Se vi preoccupa il fatto 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 tutto ciò senza di esso: per ciascuno dei 2561024 numeri provare ogni programma possibile di 2561024, finché non ne si trova uno adatto. Non importa che la ricerca duri molto a lungo: dopo aver confrontato meno di (2561024)2 coppie di un numero e un programma, finirà per completarsi, e troverà quel numero segreto.
O non si concluderà? Dopo tutto, tra tutti i programmi che saranno testati, ci sarà anche while True: pass (e i suoi analoghi funzionali) — e la verifica di tale programma non andrà avanti!
A differenza del paradosso di Berry, dove la trappola risiedeva nell'informalità delle rappresentazioni, nel secondo caso abbiamo una riformulazione ben mascherata . Infatti, non è possibile determinare l'output di un programma in un tempo finito. In particolare, la complessità di Kolmogorov : non esiste alcun algoritmo in grado di determinare, per un dato numero, la lunghezza del programma più breve che lo produce; pertanto, non esiste soluzione neanche per il problema di Berry — trovare per un numero dato la lunghezza della rappresentazione verbale più breve.
Fonte: habr.com
