Պարադոքսներ տվյալների սեղմման վերաբերյալ

Տվյալների սեղմման խնդիրն իր ամենապարզ ձևով կարող է վերաբերել թվերին և դրանց նշումներին: Թվերը կարելի է նշել թվերով («տասնմեկ» 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 (և դրա ֆունկցիոնալ անալոգները) - և գործն ավելի հեռուն չի գնա, քան նման ծրագրի փորձարկումը:

Ի տարբերություն Բերիի պարադոքսի, որտեղ որսալը նշագրման ոչ պաշտոնականության մեջ էր, երկրորդ դեպքում մենք ունենք լավ քողարկված վերաձեւակերպում. «Խնդիրների դադարեցում». Փաստն այն է, որ սահմանափակ ժամանակում անհնար է որոշել դրա արդյունքը ծրագրից: Մասնավորապես, Կոլմոգորովի բարդությունը անհաշվելիՉկա ալգորիթմ, որը թույլ կտա տվյալ թվի համար գտնել այս թիվը տպող ամենակարճ ծրագրի երկարությունը. ինչը նշանակում է, որ Բերիի խնդրի լուծումը չկա՝ գտնել տվյալ թվի ամենակարճ բառային նշանակման երկարությունը:

Source: www.habr.com