Il problema della compressione dei dati, nella sua forma più semplice, può riguardare i numeri e le loro notazioni. I numeri possono essere indicati con numeri ("undici" per il numero 11), espressioni matematiche ("due nel ventesimo" per 1048576), espressioni stringa ("cinque nove" per 99999), nomi propri ("numero della bestia" per 666, "anno della morte di Turing" per il 1954), o combinazioni arbitrarie degli stessi. È adatta qualsiasi designazione con cui l'interlocutore possa determinare chiaramente di quale numero stiamo parlando. Ovviamente ditelo al vostro interlocutore "fattoriale di otto" più efficiente della notazione equivalente "quarantamilatrecentoventi". Qui sorge una domanda logica: qual è la notazione più breve per un dato numero?
Il filosofo Bertrand Russell pubblicò nel 1908 , che tocca la questione della notazione dei numeri dal lato opposto: Qual è il numero più piccolo che non richiede ottanta lettere?
Deve esistere un tale numero: da ottanta lettere e spazi russi si possono ricavare solo 3480 designazioni, il che significa che con ottanta lettere non si possono designare più di 3480 numeri. Ciò significa che è impossibile designare un certo numero non più di 3480 in questo modo.
Ciò significa che questo numero corrisponderà alla designazione "il numero più piccolo per il quale non bastano ottanta lettere", che ha solo 78 lettere! Da un lato questo numero deve esistere; d'altra parte, se questo numero esiste, la sua designazione non gli corrisponde. Paradosso!
Il modo più semplice per liquidare questo paradosso è fare riferimento all’informalità delle notazioni verbali. Ad esempio, se nella notazione fosse consentito solo un insieme di espressioni specificatamente definito, allora "il numero più piccolo per il quale non bastano ottanta lettere" non sarebbe una notazione valida, mentre notazioni praticamente utili come "fattoriale di otto" rimarrebbe accettabile.
Esistono modi formali per descrivere la sequenza (algoritmo) di azioni sui numeri? Esistono e in abbondanza si chiamano linguaggi di programmazione. Invece delle notazioni verbali, utilizzeremo programmi (ad esempio in Python) che visualizzano i numeri richiesti. Ad esempio, per cinque nove il programma è adatto print("9"*5). Continueremo ad interessarci al programma più breve per un dato numero. La lunghezza di tale programma viene chiamata numeri; è il limite teorico al quale un dato numero può essere compresso.
Invece del paradosso di Berry, possiamo ora considerarne uno simile: Qual è il numero più piccolo che un programma in kilobyte non è sufficiente a produrre?
Ragioneremo come prima: ci sono 2561024 kilobyte di testi, il che significa che non possono essere emessi più di 2561024 numeri dai programmi kilobyte. Ciò significa che non è possibile derivare in questo modo un certo numero non superiore a 2561024.
Ma scriviamo un programma in Python che generi tutti i possibili testi in kilobyte, li esegue per l'esecuzione e, se restituisce un numero, aggiunge questo numero al dizionario di quelli raggiungibili. Dopo aver controllato tutte le 2561024 possibilità, non importa quanto tempo impiega, il programma cerca il numero più piccolo mancante nel dizionario e stampa quel numero. Sembra ovvio che un programma del genere entrerà in un kilobyte di codice e produrrà proprio il numero che non può essere emesso da un programma da kilobyte!
Qual è il problema adesso? Non può più essere attribuito all’informalità della notazione!
Se sei confuso dal fatto che il nostro programma richiederà una quantità astronomica di memoria per funzionare - un dizionario (o array di bit) di 2561024 elementi - allora puoi fare la stessa cosa senza di essa: per ciascuno dei 2561024 numeri, a turno , esamina tutti i 2561024 programmi possibili, finché non ne trovi uno adatto. Non importa che tale ricerca durerà a lungo: dopo aver controllato meno di (2561024)2 coppie dal numero e dal programma, finirà e troverà quel numero tanto caro.
Oppure non finirà? Infatti, tra tutti i programmi che verranno provati, ce ne sarà while True: pass (e i suoi analoghi funzionali) - e la questione non andrà oltre il test di un programma del genere!
A differenza del paradosso di Berry, dove il problema stava nell'informalità della notazione, nel secondo caso abbiamo una riformulazione ben mascherata . Il fatto è che è impossibile determinare l'output di un programma in un tempo finito. In particolare, la complessità di Kolmogorov : non esiste un algoritmo che permetta, per un dato numero, di trovare la lunghezza del programma più breve che stampa quel numero; il che significa che non esiste soluzione al problema di Berry: trovare la lunghezza della designazione verbale più breve per un dato numero.
Fonte: habr.com