De Problem vun der Datekompressioun, a senger einfachster Form, kann op Zuelen an hir Notatioune bezéien. Zuelen kënnen duerch Ziffere bezeechent ginn ("eelef" fir d'Nummer 11), mathematesch Ausdréck ("zwee am zwanzegsten" fir 1048576), String Ausdréck ("fënnef néng" fir 99999), eegen Nimm ("Nummer vum Déier" fir 666,. "Joer vum Turing sengem Doud" fir 1954), oder arbiträr Kombinatioune dovun. All Bezeechnung ass gëeegent, duerch déi de Gespréichspartner kloer bestëmmen kann iwwer wéi eng Zuel mir schwätzen. Natierlech, sot Äre Gespréichspartner "Faktor vun aacht" méi effizient wéi gläichwäerteg Notatioun "véierzegdausenddräihonnertzwanzeg". Eng logesch Fro stellt sech hei: wat ass déi kuerst Notatioun fir eng bestëmmten Zuel?
De Philosoph Bertrand Russell huet 1908 publizéiert , wat d'Fro vun der Zuelennotatioun vun der anerer Säit beréiert: Wat ass déi klengst Zuel déi net aachtzeg Buschtawen erfuerdert?
Esou eng Zuel muss existéieren: vun aachtzeg russesche Buschtawen a Raum kënnt Dir nëmmen 3480 Bezeechnungen ausmaachen, dat heescht datt Dir mat aachtzeg Buschtawen net méi wéi 3480 Zuelen bezeechent. Dëst bedeit datt et onméiglech ass eng gewëssen Zuel net méi wéi 3480 op dës Manéier ze bezeechnen.
Dëst bedeit datt dës Zuel der Bezeechnung entsprécht "déi klengst Zuel fir déi uechtzeg Buschtawen net genuch sinn", déi nëmmen 78 Buschtawen huet! Engersäits muss dës Zuel existéieren; op der anerer Säit, wann dës Zuel existéiert, dann entsprécht hir Bezeechnung net. Paradox!
Deen einfachste Wee fir dëse Paradox ze entloossen ass d'Informalitéit vu verbalen Notatiounen ze referenzéieren. Wéi, wann nëmmen e spezifesch definéiert Set vun Ausdréck an der Notatioun erlaabt wier, dann "déi klengst Zuel fir déi uechtzeg Buschtawen net genuch sinn" wier keng valabel Notatioun, wärend praktesch nëtzlech Notatioune wéi "Faktor vun aacht" akzeptabel bleift.
Ginn et formell Weeër fir d'Sequenz (Algorithmus) vun Aktiounen op Zuelen ze beschreiwen? Et ginn, an am Iwwerfloss - si ginn Programméierungssprooche genannt. Amplaz vu verbale Notatioune benotze mir Programmer (zum Beispill am Python) déi déi erfuerderlech Zuelen weisen. Zum Beispill, fir fënnef Néng ass de Programm gëeegent print("9"*5). Mir wäerten weider am kuerste Programm fir eng bestëmmt Zuel interesséiert ginn. D'Längt vun esou engem Programm gëtt genannt Zuelen; et ass déi theoretesch Limit op déi eng bestëmmten Zuel kompriméiert ka ginn.
Amplaz vum Berry säi Paradox kënne mir elo en ähnlechen betruechten: Wat ass déi klengst Zuel déi e Kilobyte Programm net genuch ass fir erauszekommen?
Mir wäerten op déiselwecht Aart a Weis wéi virdrun begrënnen: et gi 2561024 Kilobyte Texter, dat heescht datt net méi wéi 2561024 Zuele vu Kilobyte Programmer erausginn kënnen. Dëst bedeit datt eng gewëssen Zuel net méi wéi 2561024 net op dës Manéier ofgeleet ka ginn.
Awer loosst eis e Programm am Python schreiwen, deen all méiglech Kilobyte Texter generéiert, se fir d'Ausféierung leeft, a wa se eng Zuel ausginn, da füügt dës Zuel un d'Wierderbuch vun erreechbaren. Nodeems Dir all 2561024 Méiglechkeeten iwwerpréift hutt, egal wéi laang et dauert, sicht de Programm déi klengst Zuel déi am Wierderbuch fehlt a dréckt dës Zuel aus. Et schéngt evident datt sou e Programm an e Kilobyte Code passt - a wäert déi ganz Zuel erausginn déi net vun engem Kilobyte Programm erausgeet!
Wat ass de Fang elo? Et kann net méi un d'Informalitéit vun der Notatioun zougeschriwwen ginn!
Wann Dir duerch d'Tatsaach duerchernee sidd datt eise Programm eng astronomesch Quantitéit un Erënnerung erfuerdert fir ze schaffen - e Wierderbuch (oder Bitarray) vun 2561024 Elementer - da kënnt Dir datselwecht maachen ouni et: fir jiddereng vun den 2561024 Zuelen, am Tour. , gitt duerch all 2561024 méiglech Programmer, bis et kee gëeegent ass. Et ass egal, datt esou eng Sich eng ganz laang Zäit dauert: nodeems Dir manner wéi (2561024)2 Puer vun der Nummer an dem Programm iwwerpréift huet, wäert et ophalen an déi ganz geschätzte Zuel fannen.
Oder wäert et net fäerdeg sinn? Tatsächlech, ënnert all de Programmer déi probéiert ginn, gëtt et while True: pass (a seng funktionell Analoga) - an d'Saach wäert net méi wäit goen wéi sou e Programm ze testen!
Am Géigesaz zum Berry sengem Paradox, wou de Fang an der Informalitéit vun der Notatioun war, hu mir am zweete Fall eng gutt verkleed Reformulatioun . D'Tatsaach ass datt et onméiglech ass seng Ausgab aus engem Programm an enger endlecher Zäit ze bestëmmen. Besonnesch Kolmogorov Komplexitéit : et gëtt keen Algorithmus deen et erlaabt, fir eng bestëmmten Zuel, d'Längt vum kuerste Programm ze fannen deen dës Zuel dréckt; dat heescht datt et keng Léisung fir dem Berry säi Problem ass - d'Längt vun der kürzester verbaler Bezeechnung fir eng bestëmmten Zuel ze fannen.
Source: will.com