Problemi i ngjeshjes së të dhënave, në formën e tij më të thjeshtë, mund të lidhet me numrat dhe shënimet e tyre. Numrat mund të shënohen me numra ("njëmbëdhjetë" për numrin 11), shprehjet matematikore ("dy në të njëzetën" për 1048576), shprehjet e vargut ("pesë nëntë" për 99999), emrat e duhur ("numri i bishës" për 666, "viti i vdekjes së Turingut" për 1954), ose kombinime arbitrare të tyre. Çdo përcaktim është i përshtatshëm me të cilin bashkëbiseduesi mund të përcaktojë qartë se për cilin numër po flasim. Natyrisht, tregoni bashkëbiseduesit tuaj "faktoriali i tetë" më efikas se shënimi ekuivalent "dyzet mijë e treqind e njëzet". Këtu lind një pyetje logjike: cili është shënimi më i shkurtër për një numër të caktuar?
Filozofi Bertrand Russell botoi në 1908 , e cila prek çështjen e shënimit të numrave nga ana e kundërt: Cili është numri më i vogël që nuk kërkon tetëdhjetë shkronja?
Një numër i tillë duhet të ekzistojë: nga tetëdhjetë shkronja dhe hapësira ruse mund të bëni vetëm 3480 përcaktime, që do të thotë se duke përdorur tetëdhjetë shkronja mund të caktoni jo më shumë se 3480 numra. Kjo do të thotë se është e pamundur të caktohet një numër i caktuar jo më shumë se 3480 në këtë mënyrë.
Kjo do të thotë që ky numër do të korrespondojë me përcaktimin "Numri më i vogël për të cilin nuk mjaftojnë tetëdhjetë shkronja", e cila ka vetëm 78 shkronja! Nga njëra anë, ky numër duhet të ekzistojë; nga ana tjetër, nëse ky numër ekziston, atëherë emërtimi i tij nuk korrespondon me të. Paradoks!
Mënyra më e lehtë për të hedhur poshtë këtë paradoks është t'i referohemi informalitetit të shënimeve verbale. Si, nëse vetëm një grup shprehjesh i përcaktuar në mënyrë specifike do të lejohej në shënim, atëherë "Numri më i vogël për të cilin nuk mjaftojnë tetëdhjetë shkronja" nuk do të ishte një shënim i vlefshëm, ndërsa shënimet praktikisht të dobishme si p.sh "faktoriali i tetë" do të mbetej e pranueshme.
A ka mënyra formale për të përshkruar sekuencën (algoritmin) e veprimeve në numra? Ka, dhe me bollëk - ato quhen gjuhë programimi. Në vend të shënimeve verbale, ne do të përdorim programe (për shembull, në Python) që shfaqin numrat e kërkuar. Për shembull, për pesë nëntë programi është i përshtatshëm print("9"*5). Ne do të vazhdojmë të jemi të interesuar për programin më të shkurtër për një numër të caktuar. Gjatësia e një programi të tillë quhet numrat; është kufiri teorik në të cilin mund të kompresohet një numër i caktuar.
Në vend të paradoksit të Berry-t, tani mund të konsiderojmë një të ngjashëm: Cili është numri më i vogël që një program kilobajt nuk mjafton për të nxjerrë?
Ne do të arsyetojmë në të njëjtën mënyrë si më parë: ka 2561024 tekste kilobajt, që do të thotë se jo më shumë se 2561024 numra mund të dalin nga programet kilobyte. Kjo do të thotë se një numër i caktuar jo më i madh se 2561024 nuk mund të nxirret në këtë mënyrë.
Por le të shkruajmë një program në Python që gjeneron të gjitha tekstet e mundshme kilobajt, i ekzekuton ato për ekzekutim dhe nëse nxjerrin një numër, atëherë e shton këtë numër në fjalorin e atyre të arritshëm. Pasi ka kontrolluar të gjitha 2561024 mundësitë, pavarësisht sa kohë duhet, programi kërkon numrin më të vogël që mungon në fjalor dhe e printon atë numër. Duket qartë se një program i tillë do të përshtatet në një kilobajt kod - dhe do të nxjerrë numrin që nuk mund të nxirret nga një program kilobajt!
Çfarë është kapja tani? Nuk mund t'i atribuohet më informalitetit të shënimit!
Nëse jeni të hutuar nga fakti që programi ynë do të kërkojë një sasi astronomike memorie për të punuar - një fjalor (ose grup bit) me 2561024 elementë - atëherë mund të bëni të njëjtën gjë pa të: për secilin nga 2561024 numrat, nga ana tjetër. , kaloni të gjitha 2561024 programet e mundshme, derisa të mos ketë një të përshtatshëm. Nuk ka rëndësi që një kërkim i tillë do të zgjasë shumë: pasi të keni kontrolluar më pak se (2561024) 2 çifte nga numri dhe programi, ai do të përfundojë dhe do të gjejë atë numër shumë të dashur.
Apo nuk do të përfundojë? Në të vërtetë, midis të gjitha programeve që do të provohen, do të ketë while True: pass (dhe analogët e tij funksionalë) - dhe çështja nuk do të shkojë më tej sesa testimi i një programi të tillë!
Ndryshe nga paradoksi i Berrit, ku kapja ishte në informalitetin e shënimit, në rastin e dytë kemi një riformulim të maskuar mirë. . Fakti është se është e pamundur të përcaktohet prodhimi i tij nga një program në një kohë të caktuar. Në veçanti, kompleksiteti Kolmogorov : nuk ka asnjë algoritëm që do të lejonte, për një numër të caktuar, të gjente gjatësinë e programit më të shkurtër që printon këtë numër; që do të thotë se nuk ka zgjidhje për problemin e Berry - të gjesh gjatësinë e përcaktimit verbal më të shkurtër për një numër të caktuar.
Burimi: www.habr.com