U prublema di cumpressione di dati, in a so forma più simplice, pò esse in relazione cù i numeri è e so notazioni. I numeri ponu esse indicati da numeri ("ondeci" per u numeru 11), espressioni matematiche ("dui in u XXimu" per 1048576), espressioni di stringa ("cinque nove" per 99999), nomi propiu ("numeru di a bestia" per 666, "annu di a morte di Turing" per u 1954), o combinazioni arbitrarie di elli. Ogni designazione hè adattata per quale l'interlocutore pò determinà chjaramente di quale numeru parlemu. Ovviamente, dite à u vostru interlocutore "fattoriale di ottu" più efficace di a notazione equivalente "quaranta milla trè centu vinti". Una quistione logica nasce quì: quale hè a notazione più corta per un numeru datu?
U filòsufu Bertrand Russell hà publicatu in u 1908 , chì tocca à u tema di a notazione numerica da u latu oppostu: Chì ghjè u numeru più chjucu chì ùn hà micca bisognu di ottanta lettere ?
Un tali numeru deve esse: da ottanta lettere è spazii russi pudete fà solu 3480 designazioni, chì significa chì cù ottanta lettere pudete designà micca più di 3480 numeri. Questu significa chì hè impussibile di designà un certu numaru micca più di 3480 in questu modu.
Questu significa chì stu numeru currisponde à a designazione "u più chjucu numeru per quale ottanta lettere ùn sò micca abbastanza", chì hà solu 78 lettere! Da una banda, stu numeru deve esse; per d 'altra banda, s'ellu esiste stu numeru, allura a so designazione ùn currisponde à questu. Paradossu !
A manera più faciule di scaccià stu paradossu hè di riferite à l'informalità di notazioni verbali. Cum'è, se solu un settore di espressioni definitu specificamente era permessu in a notazione, allora "u più chjucu numeru per quale ottanta lettere ùn sò micca abbastanza" ùn saria micca una notazione valida, mentre chì notazioni praticamente utili cum'è "fattoriale di ottu" resterebbe accettabile.
Ci sò modi furmali per discrìviri a sequenza (algoritmu) di l'azzioni nantu à i numeri? Ci sò, è in abbundanza - sò chjamati linguaggi di prugrammazione. Invece di notazioni verbali, avemu aduprà prugrammi (per esempiu, in Python) chì mostranu i numeri necessarii. Per esempiu, per cinque nove u prugramma hè adattatu print("9"*5). Continueremu à esse interessatu à u prugramma più curtu per un numeru datu. A durata di un tali prugramma hè chjamatu numeri; hè u limitu teoricu à quale un numeru datu pò esse cumpressu.
Invece di u paradossu di Berry, pudemu avà cunsiderà un simile: Chì ghjè u numeru più chjucu chì un prugramma di kilobyte ùn hè micca abbastanza per pruduce?
Ragiunàmu in u listessu modu cum'è prima: ci sò 2561024 testi kilobyte, chì significa chì micca più di 2561024 numeri pò esse pruduciutu da prugrammi kilobyte. Questu significa chì un certu numaru micca più grande di 2561024 ùn pò micca esse derivati in questu modu.
Ma scrivemu un prugramma in Python chì genera tutti i testi di kilobyte pussibuli, li eseguisce per l'esekzione, è s'ellu pruduce un numeru, poi aghjunghje stu numeru à u dizziunariu di quelli raggiungibili. Dopu avè verificatu tutte e 2561024 pussibulità, ùn importa micca u tempu, u prugramma cerca u più chjucu numeru chì manca da u dizziunariu è stampa quellu numeru. Sembra ovviu chì un tali prugramma si mette in un kilobyte di codice - è pruducerà u numeru stessu chì ùn pò micca esse pruduciutu da un prugramma kilobyte!
Chì ci hè avà? Ùn pò più esse attribuita à l'informalità di a notazione !
Sè vo site cunfusu da u fattu chì u nostru prugramma hà bisognu di una quantità astronomica di memoria per travaglià - un dizziunariu (o array di bit) di 2561024 elementi - allora pudete fà a stessa cosa senza ellu: per ognunu di i numeri 2561024, à turnu. , passa per tutti i 2561024 prugrammi pussibuli, finu à chì ùn ci hè micca adattatu. Ùn importa micca chì una tale ricerca durà assai tempu: dopu avè verificatu menu di (2561024) 2 pariglii da u numeru è u prugramma, finisce è truvà quellu numeru assai cari.
O ùn finirà micca ? Infatti, trà tutti i prugrammi chì saranu pruvati, ci saranu while True: pass (è i so analoghi funziunali) - è a materia ùn anderà più in là di pruvà un tali prugramma!
A cuntrariu di u paradossu di Berry, induve a cattura era in l'informalità di a notazione, in u sicondu casu avemu una riformulazione ben disfrazata. . U fattu hè chì hè impussibile di determinà a so pruduzzioni da un prugramma in un tempu finitu. In particulare, Kolmogorov cumplessità : ùn ci hè un algoritmu chì permette, per un numeru datu, di truvà a durata di u prugramma più curtu chì stampa stu numeru ; chì significa chì ùn ci hè micca suluzione à u prublema di Berry - per truvà a durata di a designazione verbale più corta per un numeru datu.
Source: www.habr.com