Detyra e kompresionit tĂ« tĂ« dhĂ«nave nĂ« formĂ«n e saj mĂ« tĂ« thjeshtĂ« mund tĂ« lidhet me numrat dhe emĂ«rtimet e tyre. Numrat mund tĂ« emĂ«rtohen me numra («njĂ«mbĂ«dhjetë» pĂ«r numrin 11), shprehje matematikore («dy nĂ« njĂ«zet» pĂ«r 1048576), shprehje string («pesĂ« nĂ«ntorë» pĂ«r 99999), emra tĂ« veçantĂ« («numri i bishĂ«s» pĂ«r 666, «viti i vdekjes sĂ« Turingut» pĂ«r 1954), ose kombinime tĂ« rastĂ«sishme tĂ« tyre. Ădo emĂ«rtim qĂ« biseduesi mund ta identifikojĂ« qartĂ« se pĂ«r cilin numĂ«r po flitet Ă«shtĂ« i pranueshĂ«m. ĂshtĂ« e qartĂ« se tĂ« komunikosh «faktorialin e tetë» Ă«shtĂ« mĂ« efektive se emĂ«rtimi ekuivalent «katĂ«rdhjetĂ« mijĂ« e tridhjetë». KĂ«tu lind njĂ« pyetje logjike: cili emĂ«rtim pĂ«r numrin e dhĂ«nĂ« Ă«shtĂ« mĂ« i shkurtĂ«r?
Filozofi Bertrand Russell publikoi në vitin 1908 , i cili trajton çështjen e emërtimeve të numrave nga anë tjetër: cili është numri më i vogël, për të cilin nuk mjaftojnë tetëdhjetë shkronja për ta emërtuar?
Një numër i tillë duhet të ekzistojë: nga tetëdhjetë shkronjat ruse dhe hapësirat mund të krijohen vetëm 3480 emërtime, kështu që, duke përdorur tetëdhjetë shkronja, nuk mund të emërtojmë më shumë se 3480 numra. Kështu, një numër, jo më shumë se 3480, s'mund të emërtohet në këtë mënyrë.
Pra, ky numër do të ketë emërtimin «numri më i vogël, për të cilin nuk mjaftojnë tetëdhjetë shkronja», në të cilin ka gjithsej 78 shkronja! Nga një anë, ky numër duhet të ekzistojë; nga ana tjetër, nëse kjo numër ekziston, emërtimi i tij nuk i përgjigjet. Paradoks!
Mënyra më e thjeshtë për të iu shmangur këtij paradoksi është të referoheni në informalitetin e emërtimeve verbale. Siç duket, nëse në emërtime lejohet vetëm një grup i caktuar shprehjesh, atëherë «numri më i vogël, për të cilin nuk mjaftojnë tetëdhjetë shkronja» nuk do të ishte një emërim i lejueshëm, ndërsa emërtimet praktikisht të dobishme si «faktorialin e tetë» do të mbeteshin të lejueshme.
A ekzistojnë mënyra formale për të përshkruar një sekuencë (algoritmin) e veprimeve mbi numrat? Po, dhe në bollëk - ato quhen gjuhë programuese. Do të përdorim programe (p.sh., në Python) në vend të emërtimeve verbale që shfaqin numrat e nevojshëm. Për shembull, për pesë nëntorët do të funksionojë programi print("9"*5). Do të vazhdojmë të jemi të interesuar për programin më të shkurtër për një numër të caktuar. Gjatësinë e këtij programi e quajm i numrit; ky është një kufi teorik, deri në të cilin një numër i caktuar mund të kompresohet.
Në vend të paradoksit Berry tani mund të shqyrtojmë një të ngjashëm: cili është numri më i vogël, për të cilin një program i vogëlësisë prej kilobyte-ësh nuk është i mjaftueshëm për ta përfituar atë?
Do të argumentojmë ashtu si edhe më parë: ekzistojnë 2561024 tekste prej kilobyte-ësh, për këtë arsye, me programet prej kilobyte-ësh, mund të nxjerrim jo më shumë se 2561024 numra. Prandaj, një numër, jo më i madh se 2561024, nuk mund të përftohet në këtë mënyrë.
Por do tĂ« shkruajmĂ« njĂ« program nĂ« Python qĂ« gjeneron tĂ« gjitha tekstet e mundshme prej kilobyte-Ă«sh, i ekzekuton ato, dhe nĂ«se ato nxjerrin njĂ« numĂ«r, atĂ«herĂ« e shton kĂ«tĂ« numĂ«r nĂ« fjalorin e arritshĂ«m. Pas verifikimit tĂ« tĂ« gjitha 2561024 mundĂ«sive, pa marrĂ« parasysh sa kohĂ« do tĂ« marrĂ« â programi kĂ«rkon se cili Ă«shtĂ« numri mĂ« i vogĂ«l qĂ« mungon nĂ« fjalor dhe e nxjerr atĂ«. Duket e qartĂ« se njĂ« program i tillĂ« do tĂ« pĂ«rfshihet nĂ« njĂ« kilobyte kodi â dhe do tĂ« nxjerrĂ« atĂ« numĂ«r pĂ«r tĂ« cilin njĂ« program prej kilobyte-Ă«sh Ă«shtĂ« i pamundur!
ĂfarĂ« Ă«shtĂ« poshtĂ« kĂ«saj tani? Tani nuk mund ta heqim pĂ«r shkak tĂ« joformalisĂ« sĂ« shĂ«nimeve!
NĂ«se ju shqetĂ«son fakti qĂ« programi ynĂ« do tĂ« kĂ«rkojĂ« njĂ« sasi astronomike memorjeje pĂ«r tĂ« punuar â njĂ« fjalor (ose njĂ« masĂ« bitoresh) prej 2561024 elementĂ«sh â atĂ«herĂ« gjithçka e njĂ«jtĂ« mund tĂ« realizohet edhe pa tĂ«: pĂ«r çdo numĂ«r nga 2561024 me radhĂ« tĂ« provoni tĂ« gjitha 2561024 programet e mundshme, derisa tĂ« gjeni atĂ« tĂ« duhurin. Nuk ka rĂ«ndĂ«si se sa do tĂ« zgjatĂ« njĂ« provĂ« e tillĂ«: pas verifikimit tĂ« mĂ« pak se (2561024)ÂČ palĂ«ve nga numri dhe programi, ajo do tĂ« pĂ«rfundojĂ« dhe do tĂ« gjejĂ« atĂ« numrin e dĂ«shiruar.
Apo nuk do tĂ« pĂ«rfundojĂ«? Sepse ndĂ«r tĂ« gjitha programet qĂ« do tĂ« provohen, do tĂ« gjejmĂ« while True: pass (dhe analogĂ«t e saj funksional) â dhe mĂ« pas verifikimi nga ky program nuk do tĂ« shkojĂ« mĂ« tutje!
NĂ« dallim nga paradoksi Berry, ku pika e ndĂ«rlikuar ishte nĂ« joformalitĂ« e shĂ«nimeve, nĂ« rastin e dytĂ« kemi njĂ« riformulim tĂ« mirĂ« maskuar ĂĂ«shtja Ă«shtĂ« se nuk mund tĂ« pĂ«rcaktohet rendimenti i programit brenda njĂ« kohe tĂ« pĂ«rfunduar. NĂ« veçanti, kompleksiteti Kolmogorov : nuk ka asnjĂ« algoritem qĂ« lejon pĂ«r njĂ« numĂ«r tĂ« caktuar tĂ« gjejĂ« gjatĂ«si e programit mĂ« tĂ« shkurtĂ«r, qĂ« e jep kĂ«tĂ« numĂ«r; dhe, kĂ«shtu, nuk ka zgjidhje as pĂ«r problemin e Berry - gjetjen e gjatĂ«sisĂ« sĂ« shprehjes mĂ« tĂ« shkurtĂ«r fjalĂ«sore pĂ«r njĂ« numĂ«r tĂ« caktuar.
Burimi: habr.com
