Tietojen pakkausongelma yksinkertaisimmassa muodossaan voi liittyä lukuihin ja niiden merkintöihin. Numerot voidaan merkitä numeroilla ("yksitoista" numerolle 11), matemaattiset lausekkeet ("kaksi kahdeskymmenes" 1048576:lle), merkkijonolausekkeet ("viisi yhdeksää" 99999:lle), erisnimet ("pedon numero" hintaan 666, "Turingin kuoleman vuosi" vuodelta 1954) tai niiden mielivaltaisia yhdistelmiä. Mikä tahansa nimitys sopii, jolla keskustelukumppani voi selvästi määrittää, mistä numerosta puhumme. Ilmeisesti kerro siitä keskustelukumppanillesi "kahdeksan tekijä" tehokkaampi kuin vastaava merkintä "neljäkymmentätuhatta kolmesataakaksikymmentä". Tässä herää looginen kysymys: mikä on lyhin merkintä annetulle numerolle?
Filosofi Bertrand Russell julkaisi vuonna 1908 , joka käsittelee numeromerkintöjä vastakkaiselta puolelta: Mikä on pienin numero, joka ei vaadi kahdeksankymmentä kirjainta?
Sellaisen numeron on oltava olemassa: kahdeksastakymmenestä venäläisestä kirjaimesta ja välilyönnistä voit muodostaa vain 3480 nimitystä, mikä tarkoittaa, että käyttämällä kahdeksankymmentä kirjainta voit määrittää enintään 3480 numeroa. Tämä tarkoittaa, että on mahdotonta määrittää tiettyä numeroa, joka on enintään 3480 tällä tavalla.
Tämä tarkoittaa, että tämä numero vastaa nimitystä "pienin numero, jolle kahdeksankymmentä kirjainta ei riitä", jossa on vain 78 kirjainta! Toisaalta tämän numeron on oltava olemassa; toisaalta, jos tämä numero on olemassa, sen nimitys ei vastaa sitä. Paradoksi!
Helpoin tapa hylätä tämä paradoksi on viitata sanallisten merkintöjen epämuodollisuuteen. Kuten, jos vain erikseen määritelty joukko lausekkeita sallittaisiin merkinnässä, niin "pienin numero, jolle kahdeksankymmentä kirjainta ei riitä" ei olisi kelvollinen merkintä, kun taas käytännössä hyödylliset merkinnät kuten "kahdeksan tekijä" pysyisi hyväksyttävänä.
Onko olemassa muodollisia tapoja kuvata lukujen toimintojen järjestystä (algoritmia)? Niitä on, ja runsaasti - niitä kutsutaan ohjelmointikieliksi. Sanallisten merkintöjen sijaan käytämme ohjelmia (esimerkiksi Pythonissa), jotka näyttävät tarvittavat numerot. Esimerkiksi viidelle yhdeksälle ohjelma sopii print("9"*5). Olemme jatkossakin kiinnostuneita lyhyimmästä ohjelmasta tietylle numerolle. Tällaisen ohjelman pituutta kutsutaan numerot; se on teoreettinen raja, johon tietty luku voidaan pakata.
Berryn paradoksin sijasta voimme nyt harkita samanlaista: Mikä on pienin luku, jonka tulostamiseen kilotavuinen ohjelma ei riitä?
Päättelemme samalla tavalla kuin ennenkin: kilotavuisia tekstejä on 2561024, mikä tarkoittaa, että kilotavuohjelmilla voidaan tulostaa enintään 2561024 numeroa. Tämä tarkoittaa, että tiettyä lukua, joka ei ole suurempi kuin 2561024, ei voida johtaa tällä tavalla.
Mutta kirjoitetaan Pythonissa ohjelma, joka luo kaikki mahdolliset kilotavutekstit, ajaa ne suoritettaviksi ja jos ne tulostavat luvun, lisää tämän luvun saavutettavien sanakirjaan. Tarkastettuaan kaikki 2561024 XNUMX XNUMX mahdollisuutta, riippumatta siitä kuinka kauan se kestää, ohjelma etsii sanakirjasta puuttuvan pienimmän luvun ja tulostaa sen. Näyttää ilmeiseltä, että tällainen ohjelma mahtuu kilotavuun koodia - ja tulostaa juuri sen numeron, jota kilotavuohjelma ei pysty tulostamaan!
Mikä saalis nyt on? Sitä ei voi enää selittää merkinnän epämuodollisuudella!
Jos olet hämmentynyt siitä, että ohjelmamme vaatii astronomisen määrän muistia toimiakseen – 2561024 elementin sanakirjaa (tai bittitaulukkoa), voit tehdä saman ilman sitä: jokaiselle 2561024 numerolle vuorostaan , käy läpi kaikki 2561024 mahdollista ohjelmaa, kunnes sopivaa ei löydy. Sillä ei ole väliä, että tällainen haku kestää hyvin kauan: tarkistettuaan alle (2561024)2 paria numerosta ja ohjelmasta, se päättyy ja löytää sen erittäin rakastetun luvun.
Vai eikö se lopu? Kaikkien kokeiltavien ohjelmien joukossa on todellakin while True: pass (ja sen toiminnalliset analogit) - ja asia ei mene pidemmälle kuin tällaisen ohjelman testaus!
Toisin kuin Berryn paradoksissa, jossa saalis oli merkinnän epämuodollisuudessa, toisessa tapauksessa meillä on hyvin naamioitu uudelleenmuotoilu. . Tosiasia on, että on mahdotonta määrittää sen tulostetta ohjelmasta rajallisessa ajassa. Erityisesti Kolmogorovin monimutkaisuus : ei ole algoritmia, joka sallisi tietylle numerolle löytää lyhimmän tämän luvun tulostavan ohjelman pituuden; mikä tarkoittaa, että Berryn ongelmaan ei ole ratkaisua - löytää lyhimmän sanallisen nimityksen pituus tietylle numerolle.
Lähde: will.com