Задача сціску дадзеных у сваёй найпростай форме можа ставіцца да лікаў і іх пазначэнняў. Лічбы можна абазначаць лічэбнікамі (адзінаццаць для ліку 11), матэматычнымі выразамі («два ў дваццатай» для 1048576), радковымі выразамі («пяць дзявятак» для 99999), імёнамі ўласнымі («лік звера» для 666, «год смерці Цьюрынга» для 1954), або адвольнымі іх камбінацыямі. Падыходзіць любое абазначэнне, па якім суразмоўца зможа адназначна вызначыць, пра якую колькасць гаворка. Відавочна, што паведаміць суразмоўцу "фактарыял васьмі" больш эфектыўна, чым эквівалентнае абазначэнне "сорак тысяч трыста дваццаць". Тут узнікае лагічнае пытанне: якое абазначэнне для зададзенага ліку самае кароткае?
Філосаф Бертран Расэл у 1908 апублікаваў , які закранае пытанне абазначэнняў лікаў з супрацьлеглага боку: які самы маленькі лік, для абазначэння якога недастаткова васьмідзесяці літар?
Такі лік павінен існаваць: з васьмідзесяці рускіх літар і прабелаў можна скласці ўсяго 3480 пазначэнняў, значыць, з выкарыстаннем васьмідзесяці літар можна пазначыць не больш за 3480 лікаў. Значыць, нейкі лік, не большы за 3480, пазначыць такім чынам немагчыма.
Значыць, гэтай колькасці будзе адпавядаць абазначэнне "самы маленькі лік, для абазначэння якога недастаткова васьмідзесяці літар", у якім усяго 78 літар! З аднаго боку, гэты лік павінен існаваць; з другога, калі гэты лік існуе, то яго абазначэнне яму не адпавядае. Парадокс!
Самы просты спосаб адмахнуцца ад гэтага парадоксу - спаслацца на нефармальнасць слоўных пазначэнняў. Маўляў, калі б у пазначэннях дапускаўся толькі канкрэтна пэўны набор выразаў, то "самы маленькі лік, для абазначэння якога недастаткова васьмідзесяці літар" не было б дапушчальным абазначэннем, тады як практычна карысныя абазначэнні тыпу "фактарыял васьмі" засталіся б дапушчальнымі.
Ці ёсць фармальныя спосабы апісання паслядоўнасці (алгарытму) дзеянняў над лікамі? Ёсць, і ў багацці - іх называюць мовамі праграмавання. Будзем замест слоўных пазначэнняў выкарыстоўваць праграмы (напрыклад, на Python), якія выводзяць патрэбныя лікі. Напрыклад, для пяці дзявятак падыдзе праграма print("9"*5). Па-ранейшаму будзем цікавіцца самай кароткай праграмай для зададзенага ліку. Даўжыню такой праграмы называюць лікі; гэта тэарэтычная мяжа, да якой зададзены лік можна сціснуць.
Замест парадокса Бэры зараз можна разгледзець аналагічны: які самы маленькі лік, для вываду якога недастаткова кілабайтнай праграмы?
Разважаць будзем гэтак жа, як і раней: існуе 2561024 кілабайтных тэкстаў, значыць, кілабайтнымі праграмамі можна вывесці не больш за 2561024 лікаў. Значыць, нейкі лік, не большы за 2561024, вывесці такім спосабам немагчыма.
Але напішам на Python праграму, якая генеруе ўсе магчымыя кілабайтныя тэксты, запускае іх на выкананне, і калі яны выводзяць нейкі лік - то дадае гэты лік у слоўнік дасягальных. Пасля праверкі ўсіх 2561024 магчымасцяў, колькі б часу гэта ні заняло - праграма шукае, які самы маленькі лік адсутнічае ў слоўніку, і выводзіць гэты лік. Здаецца відавочным, што такая праграма ўкладзецца ў кілабайт кода - і выведзе той самы лік, якое немагчыма вывесці кілабайтнай праграмай!
У чым жа падвох зараз? На нефармальнасць абазначэнняў яго спісаць ужо нельга!
Калі вас бянтэжыць тое, што наша праграма запатрабуе астранамічнай колькасці памяці для працы - слоўнік (або бітавы масіў) з 2561024 элементаў - то можна ўсё тое ж самае ажыццявіць і без яго: для кожнага з 2561024 лікаў па чарзе перабіраць усе 2561024 магчымых праграм, пакуль не знойдзецца прыдатная. Не важна, што такі перабор працягнецца вельмі доўга: пасля праверкі менш за (2561024)2 пар з ліку і праграмы ён бо завершыцца, і знойдзе той самы запаветны лік.
Ці не завершыцца? Бо сярод усіх праграм, якія будуць апрабаваны, сустрэнецца while True: pass (і яе функцыянальныя аналагі) - і далей праверкі такой праграмы справа ўжо не пойдзе!
У адрозненне ад парадокса Бэры, дзе падвох быў у нефармальнасці пазначэнняў, у другім выпадку мы маем добра замаскіраваную перафармулёўку . Справа ў тым, што па праграме немагчыма за канчатковы час вызначыць яе выснову. У прыватнасці, калмагораўская складанасць : няма ніякага алгарытму, які б дазволіў для зададзенага ліку знайсці даўжыню самай кароткай праграмы, якая выводзіць гэты лік; а значыць, няма рашэння і для задачы Бэры - знайсці для зададзенага ліку даўжыню самага кароткага слоўнага абазначэння.
Крыніца: habr.com