Անկյունագծայնացում կոչվող տեխնիկայի վրա հիմնվող մաթեմատիկական ապացույցները կարող են ծայրահեղորեն հակասական լինել, սակայն դրանք օգնում են բացահայտել ալգորիթմների սահմանները։
Ալգորիթմներն այժմ ամենուր են։ Դրանք օպտիմալացնում են մեր երթևեկը, մշակում վճարումները և համակարգում ինտերնետի ծանրաբեռնվածությունը։ Թվում է՝ ցանկացած խնդրի համար, որը հնարավոր է ներկայացնել հստակ մաթեմատիկական տերմիններով, կա ալգորիթմ, որն առնվազն սկզբունքորեն կարող է լուծել այն։
Սակայն դա այդպես չէ․ որոշ պարզ թվացող խնդիրներ ալգորիթմները երբեք չեն կարող լուծել։ Ինֆորմատիկայի ոլորտի ռահվիրա Ալան Թյուրինգը մոտ մեկ դար առաջ ապացուցել է նմանատիպ «անհաշվարկելի» խնդիրների առկայությունն այն նույն աշխատությունում, որտեղ սահմանել է հաշվարկման մաթեմատիկական մոդելը, ինչը դարձել է ժամանակակից ինֆորմատիկայի հիմքը։
Թյուրինգն այս բեկումնային արդյունքը գրանցեց հակաինտուիտիվ մի ռազմավարության միջոցով․ նա սահմանեց խնդիր, որը խափանում է այն լուծելու յուրաքանչյուր փորձ։
«Ես հարցնում եմ, թե ինչ ես անում, ապա ասում եմ՝ «ոչ, ես մեկ այլ բան եմ անելու»», – ասում է Ռահուլ Իլանգոն՝ Մասաչուսեթսի տեխնոլոգիական ինստիտուտի տեսական ինֆորմատիկայի ֆակուլտետի շրջանավարտ։
Թյուրինգի ռազմավարությունը հիմնված էր մաթեմատիկական անկյունագծայնացում կոչվող տեխնիկայի վրա, որն ուշագրավ պատմություն ունի։ Ահա Թյուրինգի՝ դրա հիմքում ընկած տրամաբանության պարզեցված բացատրությունը։
Տողերի տեսություն
Անկյունագծայնացումը բխում է սովորական խնդրի լուծման համար կիրառվող մի խելացի հնարքից․ տրված են կա՛մ 0, կա՛մ 1 արժեքներով բիթերից բաղկացած տողեր։ Մի շարք հավասար երկարության նման տողերից հնարավո՞ր է արդյոք նորը կազմել, որը ցանկում չկա։
Պարզագույն տարբերակը տողերը հերթով դիտարկելն է։ Ենթադրենք՝ հինգ տող ունենք, որոնցից յուրաքանչյուրում՝ հինգ բիթ։ Սկսենք ցուցակում փնտրել 00000։ Եթե այն չկա, կարող ենք չշարունակել։ Եթե կա, անցնենք 00001-ին և կրկնենք նույն գործընթացը։ Սա բավականին պարզ է, սակայն դանդաղ՝ երկար տողերով մեծ ցուցակների համար։
Անկյունագծայնացումը այլընտրանքային տարբերակ է, որը բիթ առ բիթ ստեղծում է պակասող տողը։ Սկսենք ցուցակում առաջին տողի առաջին բիթից՝ նրա հակառակ արժեքը գրի առնելով, և այն կդառնա նոր տողի առաջին բիթը։ Հետո նշենք երկրորդ տողի երկրորդ բիթի հակառակը, որը կլինի նոր տողի երկրորդ բիթը․ սա կրկնենք մինչև ցուցակի ավարտը։ Այսպես, ամեն հաջորդ բիթի ժխտման միջոցով ստացվող նոր տողը յուրաքանչյուր նախնական տողից տարբերվում է առնվազն մեկ բիթով։ ” գուցե սենց մի բան (նրանք նաև անկյունագիծ են կազմում, որից էլ առաջացել է այս տեխնիկայի անվանումը՝ անկյունագծային)։
Անկյունագծայնացումը կիրառելիս անհրաժեշտ է ուսումնասիրել ցանկում յուրաքանչյուր տողից ընդամենը մեկական բիթ, ինչի շնորհիվ էլ այն մյուս մեթոդներից ավելի արագ է։ Բայց դրա մեծագույն ուժն այն է, թե ինչպես այն կարող է աշխատել անվերջության դեպքում։
«Տողերն այժմ կարող են անսահման լինել, ցանկը՝ նույնպես, և այս մեթոդը կրկին կաշխատի», – նշել է Ռայան Ուիլյամսը՝ Մասաչուսեթսի տեխնոլոգիական ինստիտուտի տեսական ինֆորմատիկայի մասնագետ։
Առաջին մարդը, որ կիրառեց սա, Գեորգ Կանտորն էր՝ մաթեմատիկական բազմությունների տեսության հիմնադիրը։ 1873 թ․-ին Կանտորը անկյունագծայնացումը օգտագործեց՝ ապացուցելու, որ որոշ անվերջություններ ավելի մեծ են, քան մյուսները։ Վեց տասնամյակ անց Թյուրինգը անկյունագծայնացման Կանտորի տարբերակը հարմարեցրեց հաշվարկման տեսությանը, ինչն ակնհայտորեն հակասական դարձրեց այն։
Սահմանափակումների խաղ
Թյուրինգը ցանկանում էր ապացուցել մաթեմատիկական այնպիսի խնդիրների գոյությունը, որոնք որևէ ալգորիթմ չի կարող լուծել, այսինքն՝ խնդիրներ, որոնք հստակորեն սահմանված մուտքային և ելքային տվյալներ ունեն, սակայն չունեն մուտքայինից ելքայինին հասնելու ստույգ ճանապարհ։ Նա այս ընդհանրական խնդիրը հստակեցրեցեց՝ կենտրոնանալով բացառապես որոշումների կայացման այնպիսի խնդիրների վրա, որտեղ մուտքային տվյալը 0-ներից և 1-երից կազմված ցանկացած տող է, իսկ ելքայինը՝ 0 կամ 1։
Որոշելը, թե արդյոք թիվը պարզ է (բաժանվում է միայն 1-ի և ինքն իր վրա), որոշման կայացնելու խնդրի մի օրինակ է. ինչ-որ թիվ ներկայացնող մուտքային տողի դեպքում, օրինակ, ելքային ճիշտ տարբերակը 1 է, եթե թիվը պարզ է, և 0՝ եթե թիվը պարզ չէ։ Մեկ այլ օրինակ է համակարգչային ծրագրերի կոդերում «շարահյուսական» սխալների (համարժեք են լեզվում քերականական սխալներին) առկայությունը ստուգելը։ Այդտեղ մուտքային տողերը կոդեր են տարբեր ծրագրերի համար․ բոլոր ծրագրերը կարելի է ներկայացնել այս ձևով, քանի որ դրանք հենց այսպես էլ պահպանվում և աշխատում են համակարգիչներում։ Նպատակը ելքայինում 1 ունենալն է, եթե կոդը շարահյուսական սխալ պարունակում է, և 0՝ եթե սխալ չի պարունակում։
Ալգորիթմը խնդիրը լուծում է, միայն եթե հնարավոր ցանկացած մուտքի համար ճշգրիտ ելք ունի․ եթե այն թեկուզ մեկ անգամ ձախողում է, նշանակում է՝ տվյալ խնդրի դեպքում դա ընդհանուր օգտագործման ալգորիթմ համարվել չի կարող։ Սովորաբար նախ հստակեցնում ես՝ ինչ խնդիր ես ուզում լուծել, ապա՝ փորձում գտնել ալգորիթմ, որը կլուծի այն։ Անլուծելի խնդիրների որոնման ճանապարհին Թյուրինգը այս տրամաբանությունը գլխիվայր շրջեց․ նա բոլոր հնարավոր ալգորիթմների անսահման ցուցակ պատկերացրեց և անկյունագծայնացման միջոցով այնպիսի համառ խնդիր կազմեց, որը ցուցակում յուրաքանչյուր ալգորիթմի կհակասեր։
Պատկերացնենք 20 հարցերից բաղկացած անհավասար, խարդախ մի խաղ, որում կոնկրետ միտք ունենալուց սկսելու փոխարեն խաղացողը պատճառ է փնտրում՝ յուրաքանչյուր հարցի «ոչ» պատասխանելու համար։ Խաղի ավարտին նա ի վերջո մի առարկա է բնութագրում՝ դրան բացառապես չբնութագրող հատկանիշներով։
Թյուրինգի անկյունագծայնացման ապացույցը այս խաղի մի տարբերակ է, որում հնարավոր ալգորիթմների անսահման ցուցակում շարունակաբար այսպիսի հարցեր են պտտվում՝ փորձելով պարզել՝ «արդյո՞ք այս ալգորիթմը կարող է լուծել այն խնդիրը, որը, ըստ մեր պնդման, անհաշվարկելի է»։
«Սրանք «անսահմանության հարցեր» լինեն կարծես», – ասում է Ուիլյամսը։
Խաղում հաղթելու համար Թյուրինգին պետք էր այնպիսի խնդիր կազմել, որի պատասխանը բոլոր ալգորիթմների համար «ոչ» կլիներ։ Այսինքն՝ գտնել մուտքային այնպիսի տվյալ, որը սխալ արդյունքի կբերե առաջին ալգորիթմով, մեկ ուրիշ տվյալ, որը կձախողեր երկրորդը, և այդպես շարունակ։ Նա դրանք գտավ՝ կիրառելով մի հնարք, որը ոչ վաղ անցյալում Կուրտ Գյոդելն էր օգտագործել՝ ապացուցելու, որ այնպիսի ինքնավերաբերական արտահայտությունները, ինչպիսին է, օրինակ, «այս պնդումը հնարավոր չէ ապացուցել»-ը, խարխլում է մաթեմատիկայի հիմքերը։
Առանցքային գաղափարն այն էր, որ յուրաքանչյուր ալգորիթմ (կամ ծրագիր) կարելի է ներկայացնել 0-ներով և 1-երով տողի տեսքով։ Ինչպես և սխալների ստուգման ծրագրի օրինակում, սա նշանակում է, որ մի ալգորիթմը կարող է մյուսի կոդն օգտագործել՝ որպես մուտքային տվյալ։ Ալգորիթմը որպես մուտքային տվյալ սկզբունքորեն կարող է նույնիսկ իր իսկ կոդն օգտագործել։
Սրա օգնությամբ մենք կարող ենք սահմանել մի անհաշվարկելի խնդիր, ինչպիսին Թյուրինգի ապացույցում է․ «Ալգորիթմի կոդը որպես մուտքային տող կիրառելիս ելքայինը պիտի հավասար լինի 1-ի, եթե ալգորիթմը 0 է դուրս բերում, երբ իր սեփական կոդն է ներմուծվում․ հակառակ դեպքում այն հավասար է 0-ի»: Յուրաքանչյուր ալգորիթմ, որը կփորձի լուծել այս խնդիրը, կսխալվի առնվազն մեկ անգամ, մասնավորապես այն տվյալի դեպքում, որը համապատասխանում է հենց իր կոդին։ Սա նշանակում է, որ այս կամակոր խնդիրը որևէ ալգորիթմով չի կարող լուծվել։
Ի՞նչ չի կարող անել ժխտումը
Ինֆորմատիկայով զբաղվող գիտնականները դեռևս ամբողջովին չէին կիրառել անկյունագծայնացման ուժը։ 1965 թ․-ին Յուրիս Հարթմանիսը և Ռիչարդ Սթերնսը Թյուրինգի փաստարկի օգնությամբ ապացուցեցին, որ ոչ բոլոր հաշվարկելի խնդիրներն են նմանատիպ բարդության․ դրանցից որոշները մյուսներից անհամեմատ բարդ են։ Սա սկիզբ դրեց հաշվարկելիության բարդության տեսությանը, որն ուսումնասիրում է հաշվողական խնդիրների բարդությունները։
Սակայն վերոնշյալ տեսությունը նաև բացահայտում է Թյուրինգի հակասական մեթոդի սահմանափակումները։ 1975 թ․-ին Թեոդոր Բեյքերը, Ջոն Գիլը և Ռոբերտ Սոլովեյն ապացուցեցին, որ այդ տեսության շատ բաց հարցեր երբեք չեն կարող լուծվել միայն անկյունագծայնացմամբ։ Դրանցից հիմնականը «P ընդդեմ NP դասի» խնդիրն է, որի առաջ քաշած հարցն այն է, թե արդյոք հեշտությամբ ստուգելի լուծումներ ունեցող բոլոր խնդիրները նույնքան հեշտությամբ կարող են լուծվել համապատասխան ալգորիթմներով։
Անկյունագծայնացմանի թույլ կողմերը անմիջական հետևանքն են վերացականության բարձր մակարդակի, որն այն այդքան ուժեղ է դարձնում։ Թյուրինգի ապացույցը որևէ անհաշվարկելի խնդիր չի ներառում, որը գործնականում կարող է առաջանալ, այլ փոխարենը տեղում նման խնդիր է հորինում։ Անկյունագծայնացման մյուս ապացույցները նույնպես հեռու են իրական աշխարհից, ուստի չեն կարող լուծել հարցեր, որտեղ իրական աշխարհին առնչվող մանրամասները նշանակություն ունեն։
«Նրանք հաշվարկները հեռավորության վրա են կատարում, – ասել է Ուիլյամսը։ – Պատկերացրեք մեկին, ով վիրուսների հետ է աշխատում՝ միայն հերմետիկ տուփում դրանց ձեռք տալով»։
Անկյունագծայնացման ձախողումը նախանշան էր, որ «P ընդդեմ NP դասի» խնդրի լուծումը երկարատև է լինելու։ Սակայն անկախ իր սահմանափակումներից՝ անկյունագծայնացումը մնում է բարդության տեսության մասնագետների զինանոցի առանցքային գործիքներից մեկը։ 2011 թ․-ին Ուիլյամսն այն օգտագործեց մի շարք այլ տեխնիկաների հետ՝ ապացուցելու, որ հաշվարկման սահմանափակ կոնկրետ մոդելը չի կարող առանձնակի բարդ խնդիրներ լուծել․ այս արդյունքին հետազոտողները չէին կարողանում հասնել 25 տարի։ Այն հեռու էր «P ընդդեմ NP դասի» խնդրի լուծումը լինելուց, այդուհանդերձ զգալի առաջընթաց էր։
Եթե ուզում եք ապացուցել, որ ինչ-որ բան անհնար է, մի՛ թերագնահատեք ընդամենը «ոչ» ասելու ուժը։
Բեն Բրուբեյքերն անկախ գիտական լրագրող է, ում աշխատանքները հրապարակվել են Quanta Magazine, Scientific American և The Conversation պարբերականներում, ինչպես նաև իր «Measuring in Reflection» բլոգում: Բրուբեյքերը գիտությունների թեկնածուի գիտական աստիճան է ստացել ֆիզիկայի ոլորտում Յեյլի համալսարանից և հետթեկնածուական հետազոտություն անցկացրել Բոլդերի Կոլորադոյի համալսարանում:
Թարգմանիչ՝ Իվետա Ավագյան (Iveta Avagyan) © Բոլոր իրավունքները պաշտպանված են: