Detyra e kompresimit tĂ« tĂ« dhĂ«nave nĂ« formĂ«n e saj mĂ« tĂ« thjeshtĂ« mund tĂ« lidhet me numrat dhe pĂ«rfaqĂ«simet e tyre. Numrat mund tĂ« pĂ«rfaqĂ«sohen me numra («njĂ«mbĂ«dhjetë» pĂ«r numrin 11), shprehje matematike («dy nĂ« njĂ«zetĂ«n» pĂ«r 1048576), shprehje string («pesĂ« nĂ«ntat» pĂ«r 99999), emra tĂ« veçantĂ« («numri i bishĂ«s» pĂ«r 666, «viti i vdekjes sĂ« Turing» pĂ«r 1954), ose kombinime tĂ« tyre tĂ« rastĂ«sishme. Ădo pĂ«rfaqĂ«sim Ă«shtĂ« i pranueshĂ«m, me kusht qĂ« diskutuesi tĂ« jetĂ« i aftĂ« tĂ« pĂ«rcaktojĂ« qartĂ« se cila Ă«shtĂ« numri nĂ« fjalĂ«. ĂshtĂ« e dukshme se t'i thuash diskutuesit «faktoriali i tetë» Ă«shtĂ« mĂ« efikase se sa pĂ«rfaqĂ«simi ekuivalent «dyzet mijĂ« triqind e njĂ«zet». KĂ«tu lind njĂ« pyetje logjike: cila Ă«shtĂ« pĂ«rfaqĂ«simi mĂ« i shkurtĂ«r pĂ«r njĂ« numĂ«r tĂ« caktuar?
Filozofi Bertrand Russell publikoi në 1908 , i cili shqyrton pyetjen e përfaqësimeve të numrave nga një anë tjetër: cili është numri më i vogël për të cilin nuk janë të mjaftueshme tetëdhjetë letra?
Në fakt, ky numër duhet të ekzistojë: me tetëdhjetë shkronjat ruse dhe hapësirat mund të krijohen vetëm 3480 përfaqësime, domethënë, duke përdorur tetëdhjetë shkronja, nuk mund të përfaqësojmë më shumë se 3480 numra. Pra, një numër që është më i vogël se 3480 nuk mund të përfaqësohet në këtë mënyrë.
Kështu, këtij numri do t'i përkasë përfaqësimi «numri më i vogël për të cilin nuk janë të mjaftueshme tetëdhjetë letra», i cili ka gjithsej 78 shkronja! Nga njëra anë, ky numër duhet të ekzistojë; nga ana tjetër, nëse ky numër ekziston, përfaqësimi i tij nuk i korrespondon. Paradoksi!
Mënyra më e thjeshtë për të anashkaluar këtë paradoks është të referohemi në informalitetin e përfaqësimeve verbale. Sipas kësaj logjike, nëse në përfaqësime do të lejohej vetëm një grup i miratur shprehjesh, atëherë «numri më i vogël për të cilin nuk janë të mjaftueshme tetëdhjetë letra» nuk do të ishin përfaqësime të lejuara, ndërsa përfaqësime praktikisht të dobishme si «faktoriali i tetë» do të mbeteshin të lejueshëm.
A ekzistojnĂ« mĂ«nyra formale pĂ«r tĂ« pĂ«rshkruar njĂ« sekuencĂ« (algoritmi) tĂ« veprimeve mbi numrat? Po, dhe nĂ« bollĂ«k â quhen gjuhĂ« programuese. Le tĂ« pĂ«rdorim programe (p.sh., nĂ« Python) nĂ« vend tĂ« pĂ«rfaqĂ«simeve verbale pĂ«r tĂ« prodhuar numrat e nevojshĂ«m. PĂ«r shembull, pĂ«r pesĂ« nĂ«ntat do tĂ« ishte e duhura programi print("9"*5). Edhe njĂ« herĂ«, do tĂ« interesoheshim pĂ«r programin mĂ« tĂ« shkurtĂ«r pĂ«r njĂ« numĂ«r tĂ« caktuar. GjatĂ«sia e kĂ«tij programi quhet i numrit; ky Ă«shtĂ« kufiri teorik deri ku 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 nuk janë të mjaftueshme një program i vogël?
Do të argumentohemi ashtu si më parë: ekzistojnë 2561024 tekste të vogla, domethënë, me programet e vogla mund të prodhojmë jo më shumë se 2561024 numra. Kështu, një numër që është më i vogël se 2561024 nuk mund të prodhohet në këtë mënyrë.
Por le tĂ« shkruajmĂ« njĂ« program nĂ« Python qĂ« gjeneron tĂ« gjithĂ« tekstet e mundshme tĂ« vogla, i ekzekuton ato, dhe nĂ«se ato prodhojnĂ« njĂ« numĂ«r â atĂ«herĂ« e shton kĂ«tĂ« numĂ«r nĂ« fjalorin e arritjes. Pas kontrollimit tĂ« tĂ« gjitha 2561024 mundĂ«sive, sado kohĂ« tĂ« zgjasĂ« â programi kĂ«rkon cila Ă«shtĂ« numri mĂ« i vogĂ«l qĂ« mungon nĂ« fjalor dhe e prodhon atĂ« numĂ«r. Duket e qartĂ« se njĂ« program i tillĂ« do tĂ« futet nĂ« njĂ« kilobajt kodi â dhe do tĂ« prodhojĂ« atĂ« numĂ«r, i cili nuk mund tĂ« prodhohet nga njĂ« program i vogĂ«l!
ĂfarĂ« ka ndodhur tani? Nuk mund tĂ« anashkalohet informaliteti i pĂ«rfaqĂ«simeve!
NĂ«se ju shqetĂ«son fakti se programi ynĂ« do tĂ« kĂ«rkojĂ« njĂ« sasi astronomike memorjeje pĂ«r tĂ« funksionuar â njĂ« fjalor (ose njĂ« matricĂ« bit) me 2561024 elemente â atĂ«herĂ« mund ta realizoni tĂ« gjithĂ« atĂ« edhe pa tĂ«: pĂ«r çdo numĂ«r nga 2561024 tĂ« kontrolloni tĂ« gjitha programet e mundshme tĂ« vogla, derisa tĂ« gjejmĂ« njĂ« tĂ« pĂ«rshtatshme. Nuk ka rĂ«ndĂ«si se sa do tĂ« zgjasĂ« ky kontroll: pasi kontrollimi i mĂ« pak se (2561024)2 çifteve tĂ« numrit dhe programit, ai do tĂ« pĂ«rfundojĂ«, dhe do tĂ« gjejĂ« atĂ« numrin e kĂ«rkuar.
Ose ndoshta nuk do tĂ« pĂ«rfundojĂ«? Sepse midis tĂ« gjithĂ« programeve qĂ« do tĂ« provosh, do tĂ« hasĂ«sh while True: pass (dhe analogĂ«t e saj funksionalĂ«) â dhe mĂ« pas nuk do tĂ« jetĂ« mĂ« e mundur pĂ«r tĂ« vazhduar kontrollin e kĂ«tij programi!
NĂ« kundĂ«rshtim me paradoksin Berry, ku hile ishte informaliteti i pĂ«rfaqĂ«simeve, nĂ« kĂ«tĂ« rast ne kemi njĂ« riformulim tĂ« mirĂ« maskuar tĂ« . Problemi Ă«shtĂ« se me programin nuk Ă«shtĂ« e mundur tĂ« pĂ«rcaktosh produktin e tij brenda njĂ« kohe tĂ« caktuar. NĂ« veçanti, kompleksiteti kolmogorovian : nuk ka asnjĂ« algoritĂ«m qĂ« mund tĂ« gjejĂ« pĂ«r njĂ« numĂ«r tĂ« caktuar gjatĂ«si e programit mĂ« tĂ« shkurtĂ«r qĂ« e printon atĂ« numĂ«r; prandaj, nuk ka asnjĂ« zgjidhje as pĂ«r problemin Berry â tĂ« gjejĂ« pĂ«r njĂ« numĂ«r tĂ« caktuar gjatĂ«si e pĂ«rshkrimit mĂ« tĂ« shkurtĂ«r verbal.
Burimi: habr.com
