ՀԱՇՎԱՐԿԵԼԻՈՒԹՅԱՆ ԲԱՐԴՈՒԹՅԱՆ ՏԵՍՈՒԹՅԱՆ ՀԻՄՆԱԴՐՈՒՅԹՆԵՐԸ

Ա. Ա. Չուբարյան Հ. Գ. Մովսեսյան Ս. Մ. Սայադյան

ՀԱՇՎԱՐԿԵԼԻՈՒԹՅԱՆ

ԲԱՐԴՈՒԹՅԱՆ ՏԵՍՈՒԹՅԱՆ

ՀԻՄՆԱԴՐՈՒՅԹՆԵՐԸ

ԵՐԵՎԱՆԻ ՊԵՏԱԿԱՆ ՀԱՄԱԼՍԱՐԱՆ

Ա. Ա. Չուբարյան Հ. Գ. Մովսեսյան Ս. Մ. Սայադյան

ՀԱՇՎԱՐԿԵԼԻՈՒԹՅԱՆ

ԲԱՐԴՈՒԹՅԱՆ ՏԵՍՈՒԹՅԱՆ

ՀԻՄՆԱԴՐՈՒՅԹՆԵՐԸ

Ուսումնական ձեռնարկ

ԵՐԵՎԱՆ

ԵՊՀ ՀՐԱՏԱՐԱԿՉՈՒԹՅՈՒՆ

ՀՏԴ 510.5(07) ԳՄԴ 22.12ց7 Չ 810 Հրատարակության է երաշխավորել ԵՊՀ ինֆորմատիկայի և կիրառական մաթեմատիկայի ֆակուլտետի գիտական խորհուրդը

Չ 810

Ա. Ա. Չուբարյան, Հ. Գ. Մովսեսյան, Ս. Մ. Սայադյան Հաշվարկելիության բարդության տեսության հիմնադրույթները/ Ա. Ա. Չուբարյան, Հ. Գ. Մովսեսյան, Ս. Մ. Սայադյան: -Եր., ԵՊՀ հրատ., 2017, 62 էջ:

Սույն ձեռնարկը պատրաստված է մագիստրոսների համար պրոֆեսոր Ա. Չուբարյանի կողմից կարդացվող համապատասխան դասընթացի հիման վրա: Դասախոսությունների գրառումները, լրացումները, խմբագրումը կատարել են Հ. Մովսեսյանը և Ս. Սայադյանը: Հեղինակները հայտնում են խորհին շնորհակալություն ՀԱԱ թղթակից անդամ, ֆիզիկամաթեմատիկական գիտությունների դոկտոր Ի. Դ. Զասլավսկուն օգտակար դիտողությունների և խորհուրդների համար:

ՀՏԴ 510.5(07) ԳՄԴ 22.12ց7

1ՏBՀ 978-5-8084-2213-1

Զ ԵՊՀ հրատ., 2017 Զ Հեղ խումբ, 2017

ԲՈՎԱՆԴԱԿՈՒԹՅՈՒՆ

Ներածություն ................................................................................................5 81. Թյուրինգյան հաշվարկների բարդության հիմնական բնութագրիչները ............................................................................................7 1.1. Թյուրինգի մեքենաների սահմանումը ..............................................7 1.2. Բարդության բնութագրիչները ........................................................11 82. Բարդության բնութագրիչների հիմնական կապը ..............................14 83. Սիմետրիայի ճանաչման խնդրի բարդության ստորին գնահատական.............................................................................................20 84. Բարդության բնութագրիչների «մեռյալ գոտիները» (խոռոչները) ...26 85. Բարդության բնութագրիչի հիմնական հայտանիշը ըստ Բլյումի .....33 86. Թյուրինգի մեքենաների համարակալում............................................35 87. Ցեյտինի, Ռաբինի և Բլյումի թեորեմները ...........................................38 88. Դետերմինացված և ոչ դետերմինացված Թյուրինգի մեքենաներ ...45 89. , դասերի սահմանումը: Հանգեցում ............................................48 810. Կուկի–Կարպի–Լևինի թեորեմը ..........................................................55 Գրականություն ...........................................................................................61

ՆԵՐԱԾՈՒԹՅՈՒՆ

Ինչպես հայտնի է, «ընթացակարգ» (ալգորիթմ) հասկացության տարբեր ճշգրտումները` Թյուրինգի մեքենաները, կարգընթաց ֆունկցիաները բոլոր ֆունկցիաների դասում առանձնացնում են միևնույն` հաշվարկելի ֆունկցիաների դասը: Հաշվարկելի ֆունկցիայի գաղափարը հնարավորություն է տալիս որոշակիորեն տարբերակելու էֆեկտիվորեն լուծվող խնդիրները ոչ-էֆեկտիվորեն լուծվող խնդիրներից: Ստացված են մի շարք կարևոր արդյունքներ որոշ խնդիրների անլուծելիության մասին: Բնական է ենթադրել, որ գոյություն ունեն էֆեկտիվության, ինչպես նաև ոչ էֆեկտիվության տարբեր աստիճաններ: Ինտուիտիվորեն պարզ է, որ հաշվարկները կարող են լինել ինչպես պարզ, այնպես էլ բարդ: Հետևաբար, որևէ ֆունկցիայի հաշվարկելիության փաստը նշելուց բացի, հետաքրքիր է որոշել նաև, թե այն ինչքանով «պարզ» կարող է հաշվարկվել: Այսպիսի մոտեցումը հանգեցնում է հաշվարկելի ֆունկցիաների դասակարգմանը ըստ դրանց «բարդության»: Մյուս կողմից, ոչ-էֆեկտիվորեն հաշվարկելի ֆունկցիաների դասում ապրիորի նույնպես հնարավոր է որոշակի դասակարգում ըստ ոչ-էֆեկտիվության տարբեր աստիճանների: Այս դասընթացում կսահմանափակվենք միայն ըստ Թյուրինգի հաշվարկելիության դիտարկումով: Ըստ Թյուրինգի հաշվարկելի ֆունկցիաների համար որպես բարդության բնութագրիչներ կարող են հանդես գալ. ա) Թյուրինգի մեքենայի աշխատանքի քայլերի քանակը (կամ որ նույնն է`մեքենայի աշխատաժամանակը): բ) աշխատանքի ընթացքում օգտագործվող բջիջների քանակը (զբաղեցրած հիշողության ծավալը):

գ) ժապավենի որոշակի իմաստով սահմանված մաշվածության աստիճանը: դ) գլխիկի շարժման ուղղության փոփոխությունների քանակը և այլն: Դասընթացում տրվում է տարբեր բնութագրիչների փոխադարձ կապը: Բերվում են լոգարիթմական, գծային, քառակուսային բարդություններով հաշվարկվող ֆունկցիաների օրինակներ: Հատուկ ուշադրություն է դարձվում լայն կիրառություն ունեցող բառերի սիմետրիայի ճանաչման խնդրի բարդության ստորին գնահատականի վրա: Ապացուցվում է, որ օպտիմալ հաշվարկների բարդության բնութագրիչների արժեքների համար գոյություն ունեն, այսպես կոչված, «մեռյալ գոտիներ» (խոռոչներ), որտեղ դրանք չեն կարող հայտնվել: Ապացուցվում է նաև, որ գոյություն ունեն կամայական աստիճանի «բարդ» հաշվարկելի ֆունկցիաներ, ինչպես նաև օպտիմալ հաշվարկ չունեցող ֆունկցիաներ: Վերջում տրվում են հայտնի P և ՀP դասերի սահմանումները, այդ դասերին պատկանող խնդիրների օրինակներ, խնդիրների հանգեցման գաղափարները, ՀP-լրիվ դասի սահմանումը, ինչպես նաև Կուկի–Կարպի–Լևինի հանրահայտ թեորեմը:

81. ԹՅՈՒՐԻՆԳՅԱՆ ՀԱՇՎԱՐԿՆԵՐԻ ԲԱՐԴՈՒԹՅԱՆ

ՀԻՄՆԱԿԱՆ ԲՆՈՒԹԱԳՐԻՉՆԵՐԸ

1.1. Թյուրինգի մեքենաների սահմանումը Թյուրինգի մեքենայի բաղադրիչ մասերն են`ժապավենը, գրողկարդացող գլխիկը և ղեկավարող սարքը (նկ. 1): ⋯

⋯

Նկ. 1.

Մեքենան աշխատում է ժամանակի առանձին = 0, 1, 2, … պահերին: Ժապավենը բաժանված է բջիջների, և ժամանակի յուրաքանչյուր պահին ամեն մի բջջում գտնվում է ճիշտ մեկ նիշ = } ( ≥ 2) մուտքի այբուբենից: ժապավենը աջից և { , ,…, ձախից անվերջաձիգ է: Հետագայում միշտ կենթադրենք, որ առանձ= Λ դատարկ նիշը, և նացված է մուտքի այբուբենի նիշերից մեկը` ժամանակի յուրաքանչյուր պահին ժապավենի վերջավոր թվով բջիջներում կարող են գրված լինել դատարկ նիշից տարբերվող նիշեր: Λ պարունակող բջիջներն անվանում ենք դատարկ: Գրող-կարդացող գլխիկը կարող է շարժվել ժապավենի վրայով և ժամանակի յուրաքանչյուր պահին դիտարկում է մեկ բջիջ: Ղեկավարող սարքը ժամանակի յուրաքանչյուր պահին , , … , } ( ≥ 1 , ≥ 0 ) վերջավոր գտնվում է = { , , … , բազմության վիճակներից որևէ մեկում: Մեքենայի աշխատանքի

պրոցեսում ղեկավարող սարքը, ելնելով իր վիճակից և գլխիկի կողմից դիտարկվող նիշից, կարող է հաջորդ պահի համար ա) փոխել գլխիկի կողմից դիտարկվող բջիջի նիշը, բ) թողնել գլխիկի դիրքը նույնը կամ տեղափոխել այն դիտարկվող բջջին հարևան աջ կամ ձախ բջիջը, գ) փոխել իր վիճակը: Այժմ տանք Թյուրինգի մեքենայի մաթեմատիկական նկարագիրը: Դիցուք ունենք երկու բազմություններ՝ } ( ≥ 2) մուտքի այբուբենը, որում առանձ= { , ,…, նացված է մեկը` = Λ դատարկ նիշը և , , … , } ( ≥ 1, ≥ 0) վիճակների բազմու= { , ,…, թյունը, որում -ն սկզբնական վիճակն է և { , … , } վիճակներից յուրաքանչյուրը եզրափակիչ վիճակներն են: Դիտարկենք հետևյալ արտապատկերումները. ∶ × ⟶ ∶ × ⟶ ∶ × ⟶ {Ա, Ձ, Տ}, }: որտեղ` = { , , … , Սահմանում: , բազմությունների և , , արտապատկերումների հնգյակն անվանենք Թյուրինգի մեքենա և նշանակենք 〈 , , , , 〉: Ենթադրենք Թյուրինգի մեքենայի ղեկավարող սարքը (կամ ուղղակի Թյուրինգի մեքենան) -րդ պահին գտնվում է / ∈ / վիճակում, իսկ գրող-կարդացող գլխիկը դիտարկում է / ∈ / նիշը պարունակող բջիջը (նկ. 1): Նկարագրենք այդ դեպքում մեքենայի աշխատանքի քայլը՝

1. Երբ ∈ \ , աշխատանքը ընդհատվում է և հետագայում կասենք, որ մեքենան դադարացրել է աշխատանքը եզրափակիչ վիճակում: 2. Երբ ∈ , կատարվում է հետևյալը. ա) ( + 1)-րդ պահին գրող-կարդացող գլխիկի դիտարկված բջիջում նիշի փոխարեն գրվում է ′ = ( , ) նիշը (չի բացառվում ′ = դեպքը), բ) ( + 1)-րդ պահին մեքենան անցնում է ′ = ( , ) վիճակի, գ) ( + 1) -րդ պահին գրող-կարդացող գլխիկը դիտարկում է նույն բջիջը, եթե ( , ) = Տ, հարևան աջ բջիջը, երբ ( , ) = Ա և հարևան ձախ բջիջը, երբ ( , ) = Ձ: Սահմանում: Յուրաքանաչյուր պահին ժապավենի աշխատանքային գոտի անվանենք ժապավենի այն մինիմալ հատվածը, որը պարունակում է ժապավենի բոլոր ոչ-դատարկ բջիջները և դիտարկվող բջիջը: Օրինակներ՝

Նկատենք, որ ժապավենի շտրիխավորված մասի առաջին և վերջին բջջիջները դատարկ չեն: Փակագծով սահմանափակված է աշխատանքային գոտին: Սահմանում: Թյուրինգի մեքենայի -րդ պահի «ընդհանուր աշխատանքային վիճակ» (կամ աշխատանքային վիճակ) ասելով կհասկանաք հետևյալ «երկհարկանի» բառը. … … , ( )

որտեղ,

,

-րդ պահի աշխատանքային գոտում

պարունակվող բառն է և գլխիկը ( ) վիճակում դիտարկում է տառը պարունակող բջիջը: Եթե = 0 պահին Թյուրինգի մեքենայի ժապավենի վրա գրվում է որևէ ոչ դատարկ նիշով սկսվող բառը, գլխիկը գտնվում է -ի առաջին տառի վրա վիճակում, ապա միարժեքորեն որոշվում է այդ մեքենայի ընդհանուր վիճակների հետևյալ հաջորդականությունը. ,

,…

(1)

որտեղ -ն =0 պահին Թյուրինգի մեքենայի աշխատանքային վիև աշխատանքային գոտում գրված է բառը), իսկ ճակն է ( (0) = -ն = պահի մեքենայի աշխատանքային վիճակն է, որը ստաց-ից, այդ մեքենայի վերը նշված վում է = − 1 պահի վիճակից` աշխատանքի սկզբունքի համաձայն: աշխատանքային վիճակն այնպիԵթե որևէ = պահին սին է, որ ( ) ∈ \ (մեքենան ավարտում է աշխատանքը), ապա ասում ենք, որ T մեքենան կիրառելի է բառի նկատմամբ (գրում ենք ! ( )) և տալիս է պահին աշխատանքային գոտում գրված ՛ բառը որպես պատասխան (գրում ենք ( )= ): Եթե (1) հաջորդականությունը անվերջ է, այսինքն ոչ մի պահի համար ( )-ն եզրափակիչ չէ, ապա ասում ենք, որ մեքենան կիրառելի չէ այդ բառի նկատմամբ, և գրում ենք ∤ ( ) : Այսպիսով, յուրաքանչյուր Թյուրինգի մեքենա իրականացնում է (հաշվում է) որոշակի բառային արտապատկերում (բառային ֆունկցիա):

1.2. Բարդության բնութագրիչները Թյուրինգի մեքենայի աշխատանքի բարդությունը բառի նկատմամբ կարելի է բնութագրել հետևյալ մեծություններով` Սահմանում: 1. մեքենայի ժամանակային բարդություն բառի նկատմամբ անվանում են T մեքենայի աշխատանքի տևողությունը /քայլերի քանակը/ բառի վրա աշխատելիս` մինչև որևէ եզրափակիչ վիճակ ընկնելը, եթե ! ( ) և անվերջ` հակառակ դեպքում: մեքենայի ժամանակային բարդությունը բառի նկատմամբ նշանակում ենք ( ): 2. մեքենայի ծավալային բարդություն բառի նկատմամբ անվանում ենք ժապավենի՝ 0-ից մինչև ( ) պահերի աշխատանքային գոտիները պարունակող մինիմալ հատվածի բջիջների քանակը, եթե ! ( ) և անվերջ` հակառակ դեպքում: մեքենայի ծավալային բարդությունը բառի նկատմամբ նշանակում ենք ( ): 3. T մեքենայի տատանումների բարդություն բառի նկատմամբ անվանում ենք 0-ից մինչև ( ) պահը գլխիկի շարժման ուղղության փոփոխությունների քանակը, եթե ! ( ) և անվերջ` հակառակ դեպքում: մեքենայի տատանումների բարդությունը բառի նկատմամբ ( ): նշանակում ենք 4. մեքենայի մաշվածության բարդություն բառի նկատմամբ անվանում ենք գլխիկի կողմից բջիջի սահմանների հատումների մաքսիմալ քանակը ( ) ժամանակում, եթե ! ( ) և անվերջ` հակառակ դեպքում: մեքենայի մաշվածության բարդությունը բառի նկատմամբ նշանակում ենք ( )-ով:

Ներմուծում ենք նաև հետևյալ մեծությունները. ( ) = max ( ) , | |

( ) = max

( ),

( ) = max

( ),

| | | |

( ) = max | |

( ),

որտեղ | |-ով նշանակված է բառի երկարությունը: Օրինակ: Դիտարկենք երկու Թյուրինգի մեքենաներ, որոնք ունար այբուբենում գրված յուրաքանչյուր բնական թվի համար ստանում են նրա բինար (երկուական) ներկայացումը:

Նկ. 2.

որտեղ ∈ { 0, 1}, 1 ≤ ≤ , = ]log [ և գնահատենք այդ մեքենաների բարդության բնութագրիչները: մեքենայի աշխատանքը կազմակերպում ենք հետևյալ ձևով. գլխիկը 1-ը տեսնելիս այն փոխարինում է 1′ -ով, գնում ձախ, և դատարկ բջիջում գրում է 0, այնուհետև վերադառնում է մինչև 1′-ը, հաջորդ 1-ը փոխարինում 1′-ով, գնում ձախ, ձախ կողմում գրված 0-ին գումարում 1 և այդպես շարունակ: -րդ ցիկլում մեքենան կարդում է տրված բառի -րդ 1-ը, այն փոխարինում է 1′-ով գնում ձախ, ձախ կողմում գրված երկուական թվին գումարում 1, գալիս աջ` մինչև ամենաաջ 1′-ը և դիտարկում հաջորդ 1-ը`արդեն ( + 1)-րդ ցիկլում: Այս Թյուրինգի մեքենայի բարդության բնութագրիչների արժեքները հետևյալներն են`

( )=

+ ]log

[+ 2∼ ,

( )= 2 +2∼ , ( )= 2 +1∼ , ≤2

( + log =

)≤ ( +

+ 1) + 2 log

+ 2 log

∼

:

մեքենան աշխատում է նույն սկզբունքով, միայն յուրաքանչյուր -րդ ցիկլում երկուական ներկայացման հերթական 1-ը գումարելուց հետո այդ ներկայացումը ամբողջությամբ արտագրում է մեկ բջիջ դեպի աջ (ունար ներկայացման հերթական ջնջված 1-ի տեղը): Դժվար չէ համոզվել, որ այս մեքենայի բարդության բնութագրիչների գնահատականներն են` ( ) ∼ log , ( )∼ , ( )∼ , ( ) ∼ log :

82. ԲԱՐԴՈՒԹՅԱՆ ԲՆՈՒԹԱԳՐԻՉՆԵՐԻ ՀԻՄՆԱԿԱՆ ԿԱՊԸ

Այսուհետև կդիտարկենք ամենուրեք (բոլոր բառերի վրա) կիրառելի Թյուրինգի մեքենաներ: 〈 , , , , 〉 Թյուրինգի մեքենան կանվանենք Սահմանում: ամենուրեք շարժունակ, եթե : × → {Ա, Ձ}, այսինքն` Թյուրինգի մեքենայի գլխիկը տեղում մնալու հրաման երբեք չի ստանում: Լեմմա Ցանկացած Թյուրինգի մեքենայի համար կարելի է կառուցել ամենուրեք ին համարժեք (այսինքն` նույն ֆունկցիան հաշվող) շարժունակ Թյուրինգի մեքենա, որի բարդության բնութագրիչները չեն գերազանցում -ի բարդության բնութագրիչներին: Ապացույց. Դիցուք T մեքենայի ծրագրում ունենք հրամանների խումբ. → Տ →

Տ

⋯ →

Տ

→ Ա(Ձ) ( > 1) = 1 դեպքը նշանակում է, որ այստեղ տեղում մնալու գործողություն չկա: > 1 դեպքում նշված հրամանների խումբը փոխարինենք համապատասխանաբար այսպիսի հրամաններով. →

Ա(Ձ)

→

Ա(Ձ)

⋯ → →

Ա(Ձ) Ա(Ձ)

Եթե գործողությունը կատարվի մեքենայի ծրագրում հանդիպող «տեղում մնալու» հրամանների բոլոր խմբերի հետ, ապա արդյունքում կստացվի մի ′ մեքենա, որը համարժեք է -ին, և ամենուրեք շարժունակ է: Հեշտ է համոզվել նաև, որ ( ) = ( ), ( )= ( ), ( ) ≤ ( ), ( ) = ( ):  Դիցուք ունենք T Թյուրինգի մեքենան: Համարակալենք նրա ժապավենի բջիջների սահմանները, օրինակ, հետևյալ եղանակով. ⋯ -4 -3 -2 -1

5⋯

Նկ. 3.

որևէ սահմանի վերագրում ենք 0 համարը, նրանից աջ` հաջորդաբար 1, 2, 3, … բնական թվերը, նրանից ձախ` − 1, −2, −3, … բացասական ամբողջ թվերը: Այսուհետև կենթադրենք, որ = 0 պահին մեքենային տրվող բառը ժապավենի վրա գրվում է 0 համարի սահմանից աջ: Սահմանում: Թյուրինգի մեքենայի հետք -րդ սահմանի վրա բառի վրա աշխատելիս կանվանենք հետևյալ բառը. ( ) = (1) (2) (3) … ( ), որտեղ -ն -րդ սահմանի հատումների մաքսիմալ արժեքն է, ( )-ն մեքենայի` -րդ սահմանի -րդ անգամ հատման վի(1 ≤ ≤ ) ճակն է, իսկ ɛ=

+, −,

եթե i-րդ սահմանի առաջին հատման ուղղությունը եղել է ձախից աջ, հակառակ դեպքում:

( ) հետքը ∀ -ի համար վերջավոր է, քանի որ -ն ամենուրեք կիրառելի Թյուրինգի մեքենա է: ( ) հետքի երկարություն ասելով կհասկանանք նրա մեջ պարունակվող վիճակների քանակը և կնշանակենք = | ( )|: Պարզ է, որ ( )=

| ( )| = ∈

∈

( )

( )

( ) = max ∈

( )

որտեղ ( )-ն ժապավենի՝ 0-ից մինչև ( ) պահերի բոլոր աշխատանքային գոտիները պարունակող մինիմալ հատվածի բջիջների բազմությունն է: ( )-ի բառով զբաղեցրած բջիջներից դեպի աջ և դեպի ձախ գտնվող մասերը անվանենք օժանդակ աշխատանքային գոտի: Այն կազմված է երկու մասից. աջակողմյան և ձախակողմյան աշխատանքային գոտիներից. ΔՁ

⋯

( )

ΔԱ

Λ

( )

Λ ⋯ ( ) Նկ. 4.

Եթե Δ ( ) = ΔՁ ( ) ∪ ΔԱ ( ), ապա՝ | ( )| = | | + |Δ ( ), որտեղ | ( )|-ն և |Δ ( )| համապատասխան բազմությունների հզորություններն են: Լեմմա (օժանդակ աշխատանքային գոտում հետքերի վերաբերյալ) ամենուրեք կիրառելի Թյուրինգի մեքենայի աշխատանքի ընթացքում օժանդակ աշխատանքային գոտու ոչ մի երկու սահմանների վրա հետքերը համընկնել չեն կարող:

Ցույց տանք, որ ∀ ≠ համար, որտեղ -րդ և -րդ սահմանները պատկանում են Δ ( ) օժանդակ աշխատանքային գոտուն, ( ) ≠ ( ): Պարզ է, որ եթե սահմաններից մեկը պատկանում է ձախակողմյան օժանդակ գոտուն, մյուսը` աջակողմյանին, ապա նրանց հետքերը չեն համընկնում նշանի պատճառով: Հետևաբար, բավական է լեմման ապացուցել միայն այն դեպքի համար, երբ երկու սահմաններն էլ պատկանում են կամ աջակողմյան, կամ ձախակողմյան օժանդակ գոտուն: Որոշակիության համար ենթադրենք , ∈ ΔԱ ( ): Կատարենք հակասող ենթադրություն. ∃ , ∈ ΔԱ ( ), որ ( ) = ( ): Որոշակիության համար ընդունենք, որ < : Ցույց տանք, որ այդ դեպքում մեքենայի աշխատանքի պրոցեսը կլինի անվերջ: Իրոք, քանի որ -րդ սահմանն առաջին անգամ հատելիս մեքենան գտնվում է որևէ (1) վիճակում և աջ շարժվելով դիտարկում է առաջին Λ նիշը, և նույն ձևով` -րդ սահմանը առաջին անգամ հատելիս այն գտնվում է նույն` (1) վիճակում և դիտարկում նույն` Λ նիշը, և բոլոր հետագա հատումների վիճակները համընկնում են, ապա երկու դեպքում էլ մեքենան կկատարի նույն գործողությունները [ , ] և [ , 2 − ] հատվածներում: Հետևաբար, (2 − )-րդ սահմանը մեքենան առաջին անգամ կհատի (1) վիճակում և կդիտարկի Λ նիշը, հետևաբար, համանման եղանակով կձևափոխի նաև [2 − , 3 − 2 ] հատվածի պարունակությունը և այսպես շարունակ: Այսինքն, ստացվում է, որ մեքենան իր աշխատանքի ընթացքում պարբերաբար աջ է շարժվում, դիտարկելով [ + ( − ), + ( − )] հատվածները ∀ ≥ 0 համար: Ստացվում է, որ մեքենան աշխատում է անվերջ և ( ) = ∞, իսկ դա հակասում է այն պայմանին, որ -ն ամենուրեք կիրառելի մեքենա է: Ստացված հակասությունն էլ ապացուցում է լեմման:

Թեորեմ բարդության բնութագրիչների փոխադարձ կապի մասին (Տրախտենբրոտ) [4] Յուրաքանչյուր Թյուրինգի մեքենայի և բառի համար, եթե ! ( ), ապա տեղի ունեն հետևյալ անհավասարությունները. ( ) ≤ ( ), 1) ( ) + 1, 2) ( ) ≤ 3) ( ) ≤ | | + 2 ( ) , ( ) ( ) , 4) ( ) ≤ որտեղ -ն մեքենայի վիճակների քանակն է, -ը` արտաքին այբուբենի տառերի քանակը: Այսուհետ բարդության բնութագրիչների գրառումներում ինդեքսը բաց է թողնվելու գրառումները չծանրաբեռնելու նպատակով, ենթադրվում է, որ դիտարկվում է միևնույն Թյուրինգի մեքենան: Թեորեմից կբխի, որ մի բնութագրիչի համար վերին (ստորին) գնահատական ունենալով, կարելի է ստանալ նաև մյուս բնութագրիչների համար: 1) և 2) գնահատականներն ակնհայտ են: 3) ( ) = | | + |Δ ( )| ≤ | | + 2 max(|ΔԱ ( )|, |ΔՁ ( )|) ∶ Համաձայն օժանդակ աշխատանքային գոտու հետքերի մասին լեմմայի, Δ ( )-ում կամայական երկու սահմանների վրա հետքերը իրարից տարբեր են: Հետևաբար, |ΔԱ ( )|, (|ΔՁ ( )|) մեծությունը վերևից գնահատվում է բոլոր հնարավոր իրարից տարբեր հետքերի քանակով: Իսկ բոլոր իրարից տարբեր հետքերի քանակը հավասար է ( )

− < ( ) + 1: −1 Հետևաբար` ( ) ≤ | | + 2 ( ) : Երբ Թյուրինգի մեքենան աշխատում է բառի վրա միարժեքորեն որոշվում է մեքենայի ընդհանուր վիճակների հետևյալ վերջավոր հաջորդականությունը. +

( )

+ ⋯+

,

=

,

( ),

ընդ որում եթե ∀ ≠ , ապա

≠

, հետևաբար, քայլերի քանակը

գնահատելու համար բավական է հաշվել բոլոր իրարից տարբեր ընդհանուր վիճակների քանակը: Գնահատենք այդ քանակը վերևից: ( )

⋯

⋯

⋯

Λ ⋯

Նկ. 5.

Աշխատանքային գոտու մաքսիմալ երկարությունը ( ) է, այն լրացնելու բոլոր հնարավոր եղանակների քանակը` ( ) , գլխիկի դիրքի համար կա ( ) հնարավորություն, գլխիկի վիճակի համար՝ հնարավորություն: Հետևաբար, մեքենայի բոլոր իրարից տարբեր ( ) ( ) : Ուրեմն` ( ) ≤ ընդհանուր վիճակների քանակը ≤ ( )

( ) :

83. ՍԻՄԵՏՐԻԱՅԻ ՃԱՆԱՉՄԱՆ ԽՆԴՐԻ ԲԱՐԴՈՒԹՅԱՆ

ՍՏՈՐԻՆ ԳՆԱՀԱՏԱԿԱՆ

Սահմանում. =

,

=

,

,

բառը կոչվում է սիմետրիկ, եթե

, …, այսինքն`

=

∀ ∈ 1,

համար:

Սիմետրիայի ճանաչման խնդիրը Թյուրինգի մեքենայի համար ձևակերպվում է հետևյալ կերպ. կառուցել Թյուրինգի մեքենա, որը {0, 1} այբուբենում ∀ բառի համար իրացնում է հետևյալ ֆունկցիան. ( )=

1, 0,

եթե եթե

սիմետրիկ է, սիմետրիկ չէ,

այսինքն, ստուգում է («ճանաչում է») բառի սիմետրիկությունը: Սահմանում. Կասենք, որ հատկությանը բավարարող համարյա բոլոր բառերը բավարարում են նաև հատկությանը, եթե | ( )| = 1, lim → | ( )| որտեղ ( )-ը հատկությանը բավարարող երկարության բառերի բազմությունն է, ( )-ը հատկությանը բավարարող երկարության այն բառերի բազմությունը, որոնք բավարարում են նաև հատկությանը: «Համարյա բոլոր բառերի համար ( ) -ից տեղի ունի պնդումը» նշանակենք հետևյալ կերպ` ∀ ∈ ( ) ( ): Թեորեմ (Բարզդին) |1| Ցանկացած Թյուրինգի մեքենայի համար, որն իրացնում է ( ) ֆունկցիան, գոյությունի ունի հաստատուն այնպիսին, որ համարյա բոլոր սիմետրիկ բառերի համար տեղի ունի հետևյալ հարաբերությունը. ( ) ≥ | | : Դիտողություն Թեորեմում ( )-ի համար տրվող գնահատականի կարգը «լավացնել» (բարձրացնելու իմաստով) հնարավոր չէ, քանի որ հեշտու20

թյամբ կարելի է կառուցել ( ) ֆունկցիան իրացնող այնպիսի Թյուրինգի մեքենա և նշել այնպիսի հաստատուն, որ ∀ բառի համար տեղի ունենա ( ) ≤ | | անհավասարությունը: Իրոք, այդ մեքենան կարող է աշխատել հետևյալ եղանակով. գլխիկը, դիտարկելով -ը, «հիշում է» այն, անցնում է մինչև բառի վերջը և -ի հետ, այնուհետև -ը «համեմատում է» «համեմատում է» -ի հետ և այլն: Այսպիսով կատարվում է ոչ ավելին, քան քայլ: + + ( − 1) + ( − 2) + ⋯ + 1 ≤ Մինչև թեորեմի ապացույցը տանք մի շարք լրացուցիչ գաղափարներ և ապացուցենք օժանդակ պնդումներ: … … բառը: Սահմանում: Դիցուք ունենք = բառի աջ -հատված ասելով կհասկանանք = … բառը, … բառը: ձախ -հատված ասելով` = … և = … բառերը: ԴիտարԴիցուք ունենք = … բառը: Եվ դիցուք, -ն ( ) ֆունկցիան կենք = … իրացնող որոշակի Թյուրինգի մեքենա է: Այդ դեպքում տեղի ունի հետևյալ լեմման. Լեմմա 1 Եթե և բառերը սիմետրիկ են, իսկ բառը սիմետրիկ չէ (որևէ -ի համար), ապա ( ) ≠ ( ): (Ենթադրվում է, որ մեքենային տրվող բառը «գրվում է» 1, 2, … , համարի բջիջներում): Ապացույց հակասող ենթադրությամբ: Ենթադրենք Ապացուցենք ( ) = ( ): Հեշտ է տեսնել, որ այդ դեպքում ( )= ( )= ( ):

Նկ. 6.

Հետևաբար, մեքենայի աշխատանքը բառի վրա սահմանից ձախ կհամընկնի մեքենայի աշխատանքի հետ բառի վրա, սահմանից աջ` մեքենայի աշխատանքի հետ բառի վրա: Հետևաբար, ժապավենի որ մասում էլ ավարտի իր աշխատանքը մեքենան բառի վրա, նա պետք է ստանա ( ) կամ ( ) ) = 1, քանի որ ( ) = ( ) = 1 ( և արժեքը: Հետևաբար, ( բառերի սիմետրիկության պատճառով): Իսկ դա հակասում է այն բանին, որ բառը սիմետրիկ չէ: Հետևաբար լեմման ապացուցված է: ( , ) -ով նշանակենք հետևյալ Դիցուք -ն որևէ հետք է: բազմությունը. ( , ) = { / -ն սիմետրիկ է & | | = & ( ) = }: Լեմմա 2 ∀

1≤ ≤

համար |

( , )| ≤ 2

Ապացույց նշված հատվածի Ենթադրենք հակառակը` | ( , )|˃2 որևէ -ի համար: Հաշվենք միևնույն -ձախ հատվածն ունեցող երկարությամբ սիմետրիկ բառերի քանակը {0, 1} այբուբենում: Այն : Հետևաբար, մեր ենթադրությունից բխում է, որ հավասար է 2 ∃ , ∈ ( , ) բառեր, այնպիսիք, որ ≠ : Դա նշանակում է, որ բառը սիմետրիկ չէ: Հետևաբար, լեմմա 1-ի համաձայն` ( ) ≠ ( ) : Եկանք հակասության, քանի որ ունեինք, որ

, ∈ ( , ), այսինքն, ( ) = ( ) = : Նշված հակասությունն էլ ապացուցում է լեմմայի պնդումը: Դիտարկենք հետևյալ բազմությունը`

( , ), | |

Որտեղ -ն որևէ բնական հաստատուն է: Լեմմա 3 ∀

հաստատունի և ∀

1≤ ≤

համար |

( )| <

, որտեղ -ն Թյուրինգի մեքենայի ներքին վիճակների քանակն է: Այս լեմմայի ապացույցը անմիջականորեն բխում է լեմմա 2-ից և այն փաստից, որ | | < պայմանին բավարարող բոլոր իրարից -ից: Իրոք` + + ⋯+ տարբեր հետքերի քանակը փոքր է < =2 : Այժմ դիտարկենք հետևյալ բազմությունը. = { / սիմետրիկ է &| | = & +1 (| ( )| < ∃ ∈ ,

Լեմմա 4 ∀ հաստատունի համար +1 − +1 :

|<2

|

Ապացույց Հեշտ է տեսնել, որ =

∪

+ 1 ∪ ⋯∪

Հետևաբար`

+1

:

|≤

|

|

|<2

Քանի որ լեմմա 3-ից ունեինք | սարությունը −

∈

,

համար,

+1 ⋅2

( )|:

անհավակստանանք |

ապա

|<

:

( )-ով նշանակենք բոլոր երկարության սիմետրիկ բառերի = ( )\ բազմությունը: բազմությունը: Դիտարկենք Փաստորեն, +1 = { / սիմետրիկ է & | | = &∀ ∈ , (| ( )| ≥ Լեմմա 5: Գոյությունի ուն հաստատուն այնպիսին, որ | | =1 lim → | ( )| Իրոք, |

|

| ( )|

=

| ( )\ | ( )|

|

=1 −

| (

⋅ ⋅

⋅

|

>1− )

Նշանակենք. +1 − 1 ⋅2

( )=

Եթե ընտրենք -ն այնպես, որ ⋅

⋅ log

նենանք. | > 1 − ( ), | ( )| ( ) = 0: |

որտեղ` ( ) ≥ 0 և lim

→

⋅ ⋅

−

∶ < 0, ապա կու-

Թեորեմի ապացույցը. Համաձայն լեմմա 5-ի, գոյությունի ունի հաստատուն, այնպիսին, որ` | | =1 lim → | ( )| բազմության սահմանումից հետևում է, որ, երբ ∈ , ապա ∀ ∈

սահմանի համար` ( ) ≥

, ( )≥

( )≥ ∈

+1 −

⋅ : Հետևաբար` ⋅

⋅

∶

,

Հետևաբար, որոշակի ընտրության դեպքում կունենանք, որ -ի բոլոր բառերի համար ( )≥

⋅| | =

⋅

: 

84. ԲԱՐԴՈՒԹՅԱՆ ԲՆՈՒԹԱԳՐԻՉՆԵՐԻ «ՄԵՌՅԱԼ ԳՈՏԻՆԵՐԸ»

(ԽՈՌՈՉՆԵՐԸ)

Դիցուք` -ն բառերի որոշակի բազմություն է, և Թյուրինգի մեքենան կիրառվում է -ին պատկանող յուրաքանչյուր բառի վրա: Սահմանում 1. Թյուրինգի մեքենան բառերի բազմության վրա աշխատում է սուբ-լոգարիթմական ժամանակում, եթե` ( ) = (| | ⋅ log | |), ∀ ∈ այսինքն` ( ) lim = 0, | |→ | | ⋅ log | | որտեղ -ն մեքենայի վիճակների քանակն է: Սահմանում 2. Թյուրինգի մեքենան բառերի բազմության վրա աշխատում է գծային ժամանակում, եթե գույություն ունի հաստատուն այնպիսին, որ` ∀ ∈ համար ( ) ≤ ⋅ | |: Թեորեմ «մեռյալ գոտիների» վերաբերյալ (Տրախտենբրոտ, |4|): Եթե -ն որոշակի այբուբենի բոլոր բառերի բազմությունն է, և Թյուրինգի մեքենան բազմության վրա աշխատում է սուբ-լոգարիթմական ժամանակում, ապա այն աշխատում է գծային ժամանակում: Սահմանում 3. Թյուրինգի մեքենան բառերի բազմության վրա աշխատում է սահմանափակ մաշվածությամբ, եթե գույություն ունի հաստատուն այնպիսին, որ՝ ∀ ∈

համար

( )≤

:

Թեորեմն ապացուցելու համար ցույց տանք, որ, եթե մեքենան աշխատում է որոշակի այբուբենի բոլոր բառերի բազմության վրա սուբ-լոգարիթմական ժամանակում, ապա աշխատում է սահմանա26

փակ մաշվածությամբ, որից և կհետևի գծային ժամանակում աշխատելը: Լեմմա 1: տառ պարունակող այբուբենում հատ իրարից գումարը բավարարում է տարբեր բառերի երկարությունների ∑ > ⋅ ⋅ log անհավասարությանը, որտեղ -ն -ից կախված որոշակի դրական հաստատուն է: մեԱպացույց: Ընտրենք ≥ 0 թիվն այնպես, որ (1 − ) ⋅ log ծությունը լինի ամբողջ թիվ: հատ բառերի բազմությունը տրոհենք երկու մասի` (1 − ) ⋅ log -ից փոքր կամ հավասար երկարություն ունեցող («կարճ») բառերի և (1 − ) ⋅ log -ից մեծ երկարությամբ («երկար») բառերի: «Կարճ» բառերի քանակը նշանակենք ( , ) - ով. ( , )≤

+

⋅

=

(

− −1

Հեշտ է տեսնել, որ lim

=

)⋅

− −1

∶

( , )

→

(

)⋅

= 0, այսինքն`«կարճ» բառերի

քանակը էապես քիչ է: «Երկար» բառերի քանակը ( − ( , ))-ն է: Պարզ է, որ > ( − ( , )) ⋅ (1 − ) ⋅ log = =

⋅ log

−

− ⋅ ⋅ log ⋅

⋅

− −1

⋅

− −1 ⋅

− >

− −1

⋅ (1 − ) ⋅ log ⋅ log

=

+ ⋅ log

>

⋅ log

− ⋅ ⋅ log =

⋅ log

Հեշտ է տեսնել, որ

⋅(

⋅ )

− ⋅ log +

⋅ ( − 1)

⋅ ( − 1)

→ ∞, երբ

կանաչափ մեծ -ների համար ∃ (0 <

⋅

=

:

→ ∞, հետևաբար, բավա-

< 1) այնպիսին, որ

> ⋅ ⋅ log

∶

Դիտողություն 1. Եթե լեմմա 1-ում դիտարկվի հատ բառերի այնպիսի բազմություն, որտեղ յուրաքանչյուր բառ կարող է հանդես գալ ամենաշատը երկու անգամ, ապա լեմմայի ապացույցում դատողությունների ընթացքը չի փոխվի, միայն «կարճ» բառերի քանակը ստացվում է 2 ( , ), հետևաբար դարձյալ տեղի ունի

( , )

→ 0, երբ

→∞

պնդումը, և նույնատիպ դատողություններից բխում է, որ ∑ > log , 0 < < 1: Լեմմա 2. Եթե մեքենան աշխատում է բառերի բազմության վրա սահմանափակ մաշվածությամբ, ապա այն աշխատում է այդ բազմության վրա գծային ժամանակում: ( )≤ : Ունենք, որ ∃ ∀ ∈ ( ) ( )≤| |+2⋅ , որտեղ -ն մեքեՔանի որ ∀ ∈ ( ) ≤ ⋅ | |: նայի վիճակների քանակն է, ապա ∃ , որ ∀ ∈ Ակնհայտ է, որ ( ) ≤ ( ) ⋅ ( ) ≤ ⋅ ⋅ | |: Նշանակելով = ⋅ , կստանանք այն, ինչ պետք էր ապացուցել: Լեմմա 3. Դիցուք -ն տրված այբուբենի բոլոր բառերի բազմությունն է: Եթե մեքենան բառերի բազմության վրա աշխատում է սուբ-լոգարիթմական ժամանակում, ապա աշխատում է սահմանափակ մաշվածությամբ:

Ենթադրենք հակառակը. տեղի ունի` ( ) = (| | ⋅ log| |) , բայց ( )-ն սահմանափակ չէ: Դա նշանակում է, որ գոյություն ունի , , … , , … , բառերի հաջորդականություն այնպիսին, որ ∈ , = 1, 2, …, | | < | | < ⋯ < | | ⋯, և` ( )< ( )<⋯< ( )<⋯ (ո) Իրոք, եթե (ճ) պայմանին բավարարող բառերի հաջորդականությունը չլիներ ըստ բառերի երկարությունների աճող, ապա այդպիսի բառերի քանակը կլիներ վերջավոր, հետևաբար և դրանց համար ( )-ն կլիներ սահմանափակ: Դիտարկենք ( ) արժեքը: Դիցուք, այն հասանելի է բառի որևէ -րդ սահմանում.

Δ ( ) Նկ. 7.

-ից աջ կամ -ից ձախ ընկած մասում, ընդհանրապես ասած, հետքերը կարող են համընկնել: Դիցուք, և սահմաններում հետքերը համընկնում են: Որոշակիության համար ընդունենք < < : Կատարենք հետևյալ գործողությունը. ժապավենի [ , ] հատվածը հեռացնենք և ու սահմանները միավորենք (ժապավենի երկու կտրված մասերը նորից «սոսնձենք»): Կստանանք մի նոր բառ, որի վրա սահմանից աջ և ձախ մեքենան կաշխատի նույն ձևով ինչբառի վրա: Հետևաբար, ( )-ն չի փոխվի նոր բառի հապես որ մար և -րդ սահմանը նորից կմնա որպես ( )-ի հասանելիության

սահման (ընդհանրապես, ոչ մի սահմանի հետք չի փոխվի): Այս գործողությունը կրկնենք այնքան անգամ, մինչև որ -ից աջ և -ից ձախ ընկած մասերում այլևս համընկնող հետքեր չլինեն: Դա նշանակում է, որ ամբողջ բառի վրա հետքերը կարող են համընկնել ամենաշատը երկու անգամ՝ մեկը -ից աջ, մյուսը` -ից ձախ ընկած մասերից: Նոր ( )= -ով: Պարզ է, որ ստացված բառը նշանակենք ( ) ∀ = 1, 2, …, համար: Այսինքն կրկին` ( ) < ( ) ⋯ < ( ) < ⋯ : , , … , , … բառերն արդեն կարող են ըստ երկարությունների աճման կարգով դասավորված չլինել, սակայն, այնուամենայնիվ`| | → ∞, երբ → ∞, քանի որ հակառակ դեպքում հաջորդականությունը կլիներ սահմանափակ: ( )-ն ներքևից կարող ենք գնահատել առնվազն | | հատ հետքերի երկարությունների գումարով, որը, համաձայն լեմմա1-ի, մեծ է | | log | |-ից (այստեղ, օգտվում ենք լեմմա1-ի առթիվ արված դիտողություն 1-ից): Հետևաբար` ( ) > | | log | |: Մյուս կողմից ունեինք, որ ( ) = (| | log| |): Հետևաբար, եկանք հակասության: Լեմման ապացուցվեց: Դիտողություն 2. Լեմմա 3-ի պայմանում նշված է, որ Ս-ն տվյալ այբուբենի բոլոր բառերի բազմությունն է: Ցույց տանք, որ այդ սահմանափակումը էական է: Դիտարկենք մի օրինակ, որտեղ առաջին սահմանման պայմանը տեղի ունի, բայց նշված սահմանափակման բացակայության պատճառով սահմանափակ մաշվածությունը առկա չէ: Դիցուք մեքենան աշխատում է հետևյալ տիպի բառերի բազմության վրա. 0 11 0 11 00 1111

0 11 00 1111 000 11111111 0 11 00 1111 … 00 … 0 11 … 1 հետևյալ կերպ. 1-երի վրայով այն պարզապես անցնում է, իսկ ամեն մի 0 -ի հանդիպելիս վերադառնում է մինչև տվյալ խմբի 0 -ների սկիզբ, և այդպես շարունակ. 011 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 ⋯              

                               

. . .

Հաշվենք այս մեքենայի բարդության բնութագրիչները: Նախ հեշտ է տեսնել, որ ( + 1) 2 −2 | = 1 + 2 + ⋯+ + 2 + 2 + ⋯+ 2 = | + < 2−1 <

+ +2 <3⋅2 2 2 ( ) ≤ 1 +2 +⋯+ + 1 + 2 + 2 +⋯+ 2 < −1 <4⋅2 ∶ <2∗ 2 − 1 Հետևաբար, ( ) = (| | log | |), այսինքն սահմանում 1-ի պայմանը տեղի ունի: Բայց ( ) = , որը հասանելի է վերջին հատ 0-ներից առաջին սահմանում: Այսինքն, մաշվածությունը սահմանափակ չէ:

Լեմմա 3-ի և լեմմա 2-ի պնդումներից բխում է «Մեռյալ գոտիների» վերաբերյալ թեորեմի ապացույցը:  Մենք արդեն դիտարկել ենք և log ժամանակային բարդությամբ թյուրինգյան հաշվարկների օրինակներ: «Մեռյալ գոտիների» վերաբերյալ թեորեմի պնդման շնորհիվ, անիմաստ է փնտրել օրինակ

log

բարդությամբ հաշվարկներ ամենուրեք որոշված Թյու-

րինգի մեքենաների դասում:

85. ԲԱՐԴՈՒԹՅԱՆ ԲՆՈՒԹԱԳՐԻՉԻ ՀԻՄՆԱԿԱՆ ՀԱՅՏԱՆԻՇԸ

ԸՍՏ ԲԼՅՈՒՄԻ

( ) թվաբանական ֆունկցիան կոչՍահմանում (Բլյում) |7| ( )և վում է մեքենայի բարդության բնութագրիչ, եթե՝ ա) մեքենայով իրականացվող ֆունկցիաների որոշման տիրույթները համընկնում են և բ) ∀ , բնական թվերի զույգի համար կարելի է ( ) = հավասարումը, թե էֆեկտիվորեն ստուգել՝ տեղի ունի ( ) ֆունկցիայի գրաֆիկը ճանաչելի բազմություն է: ոչ, այսինքն Ցույց տանք, որ վերը սահմանված չորս բարդության բնութագրիչները բավարարում են բ) հատկությանը (ա) հատկությունը ներառված է այդ բնութագրիչների սահմանումներում): 1. ∀ , բնական թվերի համար հեշտ է ստուգել, թե արդյոք տեղի ունի ( ) = հավասարումը, թե ոչ: ∀ , | | ≤ բառի համար մեքենան աշխատացնում ենք ոչ ավելի, քան քայլ: ա) եթե ∀ ((| | ≤ )&( ( ) ≤ )) և ∃ ((| | ≤ )&( ( ) = )), ապա ( ) = բ) եթե ∀ ((| | ≤ )&( ( ) < )), ապա ( ) ≠ գ) եթե ∃ (| | ≤ ) և մեքենան այդ բառի վրա քայլ կատարելով կանգ չի առնում, ապա ( ) ≠ : Մյուս բնութագրիչների համար այդ ստուգումը կատարելու նպատակով օգտվում ենք բարդության բնութագրիչների միջև գոյություն ունեցող կապից (82)՝ ( ) ( )≤ ⋅ ( ) ≡ ( ( )) ( )≤ ( )≤

| | | |

( )

| |+2

( )

≡

( ( ))

( )

| |+2

( )

≡

( ( ))

Օրինակ, ( ) = պայմանի ստուգումը կատարելու ժամանակ բավական է հետևել մեքենայի աշխատանքի սկզբից մինչև

( )-րդ քայլը: Եթե ∀ (| | ≤ ) բառի համար մեքենան կանգ առնի ( ) –ից ոչ ավել քայլերից հետո, ընդ որում max|

( )=

|

,

ապա ( ) = : Հակառակ դեպքում, այսինքն, եթե մեքենան որևէ երկարություն ունեցող բառի վրա ( ) քայլ հետո կանգ չի առնում կամ ∀ (| | ≤ ) բառերի վրա աշխատում է ( )-ից ոչ ավելի քայլ, բայց կանգ առնելուց հետո max ≠ , | |

ապա ( ) ≠ : Այժմ դիտարկենք հետևյալ ֆունկցիան. ( ), որը ցույց է տալիս, թե Թյուրինգի մեքենայի բառի վրա աշխատանքի ընթացքում աշխատանքային գոտու որևէ բջջի պարունակությունը ամենաշատը քանի անգամ է փոփոխվում ( ( ) ժամանակում ), եթե -ն բառի նկատմամբ կիրառելի է, և ∞ հակառակ դեպքում: Նշանակենք. ( ) = max ( ) : | |

Հետագայում (87-ում) ցույց կտրվի, որ բնութագրիչ չէ:

( ) -ը բարդության

86. ԹՅՈՒՐԻՆԳԻ ՄԵՔԵՆԱՆԵՐԻ ՀԱՄԱՐԱԿԱԼՈՒՄ

〈 , , , , 〉 Թյուրինգի մեքենա

Դիցուք տրված է որևէ

} արտաքին այբուբենով, , } վիճակների բազմությամբ

= { , ,⋯, = { , ,⋯,

և , , արտապատկերումներով: Ակնհայտ է, որ այս Թյուրինգի մեքենան կարելի է նկարագրել հետևյալ հնգյակների (հրամանների) հաջորդականությամբ՝ ,

,

,

,

,

,

⋯ ,

,

,

,

,

,

,

,

,

⋯ ,

(1) ,

,

⋮ ,

,

,

,

,

,

⋯ ,

,

,

,

որտեղ ,

= ( ,

)

,

=

,

0≤ ≤

−1

,

=

,

0≤ ≤

−1

Պարզ է, որ հրամանների քանակը ⋅ է: Եթե պայմանավորվենք ∀ Թյուրինգի մեքենայի համար նրա հրամանների (1) համախումբը գրել նշված կարգով, ապա հրաման35

ների առաջին երկու նիշերը կարող ենք չգրել և գրել միայն , ,

,

,

,

,

եռյակների հաջորդականությունը: Ընդ որում, եթե ամեն մի

,

,

,

(

,

=

,0≤ ≤

− 1,

,

=

,0 ≤

,

≤ ( − 1)) եռյակի

փոխարեն գրենք հետևյալ կոդը ( , , ), որտեղ է որոշվում է հետևյալ ձևով. 0, =Տ =Ա = 1, 2, =Ձ ապա (1)-ի փոխարեն կունենանք բնական թվերի եռյակների հաջորդականություն: Յուրաքանչյուր եռյակ փոխարինենք իր կանտորյան համարով (|3)): Նշանակենք այդ համարը ձախ մաս ունեցողի համար

,

-ով:

Այսպիսով Թյուրինգի մեքենան բնութագրում է հետևյալ բնական թվերի համախումբը. , , , , , , ,⋯, , , , ,⋯, , , , , ,⋯, , (2) Նկատենք, որ մինչև այժմ կատարած ձևափոխությունները փոխմիարժեքությունը չեն խախտում: Այժմ ℎ-ով նշանակենք (2) համախմբության գյոդելյան համարը. ) ℎ = ( , , , ,⋯, , Հիշենք, որ գյոդելյան համարի միջոցով վերականգնվում էր հաջորդականության երկարությունը (մեզ մոտ այն ⋅ է) և նրա յուրաքանչյուր անդամը: Հետևաբար, ℎ-ի հետ ունենալով կամ -ի կամ -ի արժեքը կարող ենք միարժեքորեն վերականգնել Թյուրինգի մեքենայի (1) հրամանների համախումբը: Փաստորեն, ∀ Թյուրինգի մեքենային համապատասխանության մեջ է դրվել ( , ℎ) բնական թվերի զույգը: Դիտարկենք այս զույգի կանտորյան համարը: Նշա= ( , ℎ): նակենք այն -ով.

բնական թիվը կանվանենք Թյուրինգի մեքենայի համար: -ի կառուցումից հետևում է, որ ոչ բոլոր բնական թվերին է համապատախանում Թյուրինգի մեքենա (օրինակ, երբ ℎ -ն այնպիսին է, որ այդ գյոդելյան համար ունեցող հաջորդականության երկարությունը պարզ թիվ է): Որպեսզի ստեղծենք նաև → { } համապատասխանությունը, որտեղ -ը բնական թվերի բազմությունն է, { } բոլոր Թյուրինգի մեքենաների բազմությունը, վարվենք հետևյալ կերպ. դիտարկենք որևէ Թյուրինգի «հիմար» մեքենա, օրինակ, այսպիսին. ,

,Տ

,

,Տ ⋮

,

,Տ

Նկ. 8.

Եթե վերը նկարագրված եղանակով որևէ բնական թվին Թյուրինգի մեքենա չի համապատասխանում, ապա նրան համապատասխանեցնենք նկ. 8-ում պատկերված մեքենան: Այսպիսով, ստեղծվեց ⟷ համապատասխանություն: Նշենք, որ այդ համապատասխանությունը փոխմիարժեք չէ. մասնավորապես, նկ. 8-ում մեքենան կունենա մի քանի համարներ: Այսպիսով, մենք ստացանք, որ Թյուրինգի մեքենաների բազմությունը կարելի է համարակալել: Հետագայում ո բնական թվին համապատասխանող Թյուրինգի մեքենան նշանակենք -ով:

87. ՑԵՅՏԻՆԻ, ՌԱԲԻՆԻ ԵՎ ԲԼՅՈՒՄԻ ԹԵՈՐԵՄՆԵՐԸ

Թեորեմ (Ցեյտին) |5| Ցանկացած ( ) արագ աճող ընդհանուր կարգընթաց ֆունկցիայի համար գոյություն ունի ( ) ամենուրեք որոշված էֆեկտիվորեն հաշվվող (ընդհանուր կարգընթաց) ֆունկցիա, որն ընդունում է միայն 0 և 1 արժեքները և որը բավարարում է հետևյալ պայմանին. ( ) ֆունկցիան հաշվող ցանկացած Թյուրինգի մեքենայի համար ∃ բնական թիվ այնպիսին, որ ( ) > ( ): ( ) ( )

Նկ. 9.

Ապացույց: Սահմանենք ( ) ֆունկցիան հետևյալ ձևով. 1, ⌉( ( ) ≤ ( )) ( ) = 1,

( )≤

( )& ( )=0

0,

( )≤

( )& ( )≠0

Ցույց տանք, որ ( )-ը բավարարում է թեորեմի պայմանին: Դիցուք -ն ( ) ֆունկցիան հաշվող որևէ Թյուրինգի մեքենա է և ( ) > ( ): Դի-ն այդ մեքենայի համարն է: Ցույց տանք, որ տարկենք

( )-ն

( )≤

1, եթե ⌉( ( ) = 1, եթե 0,

եթե

( ))

( )≤

( )& ( )=0

( )≤

( )& ( )≠0

ֆունկցիան հաշվող մեքենան Քանի որ ( ) = ( ) ( -ն էր), ապա 2-րդ և 3-րդ դեպքերը տեղի չունեն, այսինքն, տեղի ունի միայն առաջին դեպքը, որը ( ) ֆունկցիայի ամենուրեք որոշված ( ) > ( ): Թեորեմն ապացուցվեց: լինելու շնորհիվ դառնում է  Այս թեորեմի ապացույցը տրվում է ստորին գնահատականների ստացման, այսպես կոչված, «անկյունագծային» եղանակով, որի էությունը կայանում է հետևյալում. Դիտարկվում է այսպիսի աղյուսակ. (0) ≤

⋯

⋯

(0)? (1) ≤

(1)? (2) ≤

⋮

(2)? ⋱ ( )≤

⋮

( )? ⋱

Հերթով ստուգվում են անկյունագծային վանդակներում գրված ( ) ≤ ( ) պայմանները: Եթե պատասխանը դրական է, ապա -ն չի կարող լինել կառուցվելիք ֆունկցիան հաշվող մեքենա և այն «հերքվում է» -րդ քայլում: Կառուցված ֆունկցիան հաշվող Թյուրինգի մեքենայի համար բավարարվում է թեորեմի պայմանը: Կառուցված ( ) ֆունկցիան կարելի է ներկայացնել հետևյալ եղանակով՝ ( ), եթե ( )≤ ( ) ( )= ( ) ≤ ( ) 1, եթե ⌉

մեքենայի հերքման փաստը որտեղ առավել արտահայտվում է առաջին տողի պայմանի կատարման դեպքում: Հետևանք 1: Ցեյտինի թեորեմը ճիշտ է ցանկացած ( ) բարդության բնութագրիչի համար: Ապացույց: Իրոք, եթե ցանկացած , բնական թվերի համար էֆեկտիվորեն ստուգվում է ( ) = պայմանը, ապա էֆեկտիվորեն ստուգվում է նաև ( ) ≤ պայմանը (քանի որ կարելի է հերթով ստուգել ( ) = 0, ( ) = 1, … , ( ) = պայմանները): Իսկ Ցեյտինի թեորեմի ապացույցում օգտագործվեց ( ) բնութագրիչի միայն այդ հատկությունը: Ցեյտինը ստացել է նաև այս թեորեմի պնդման ուժեղացումը: Հետևանք 2: Ցանկացած ( ) արագ աճող ամենուրեք որոշված կարգընթաց ֆունկցիայի համար գոյություն ունի Ց ( ) ամենուրեք որոշված ֆունկցիա (էֆեկտիվորեն հաշվվող), որն ընդունում է միայն ( ) ≥ ( )))1: 0 և 1 արժեքներ և ∀ ( : Ց ⇒ (∃ ∈ Ապացույց: Այս արդյունքը կստանանք որպես հետևանք Ցեյտինի թեորեմից, եթե Թյուրինգի մեքենաների բազմությունը վերահամարակալենք հետևյալ կերպ՝

∈

∃

նշանակում է, որ գոյություն ունեն անվերջ հատ -եր:

Նոր համարները ստացվում են հաջորդաբար սլաքներով շարժվելիս: Այդ դեպքում յուրաքանչյուր Թյուրինգի մեքենա կունենա անվերջ քանակությամբ համարներ: Օրինակ, -ն կստանա 0, 2, 3, 9, … համարները: Հետևաբար, անվերջ քանակությամբ կետերում կստանանք նույն արդյունքը: Հետևանք 3: 85-ում սահմանված ( ) ֆունկցիան բարդության բնութագրիչ չէ: Ապացույց: Հարկավոր է ցույց տալ, որ գոյություն ունեն , ∈ այնպես, որ ( ) = պայմանը էֆեկտիվորեն չի ստուգվում: Դրա համար բավական է ցույց տալ, որ ( )-ի համար Ցեյտինի թեորեմը տեղի չունի: Իրոք, ցույց տանք, որ ցանկացած Թյուրինգի մեքենայի համար կարելի է կառուցել -ին համարժեք ′ Թյուրինգի մեքենա ( ) ≤ 3: ′-ի աշխատանքը համընկնում է -ի աշխաայնպես, որ տանքի հետ սկզբից սկսած մինչև այն է պահը, երբ ժապավենի աշխատանքային գոտու որևէ -րդ բջջի պարունակությունը փոխվում է առաջին անգամ: Դրանից հետո աշխատանքային գոտու ողջ պարունակությունը արտագրվում է աջից` ժապավենի դատարկ մասում, որևէ դատարկ բջջից սկսած -րդ բջջում տեղադրելով նոր նիշը, և ապա անցնում է այն բջջի դիտարկմանը, որը պետք է դիտարկվեր մեքենայի կողմից ( + 1) -րդ պահին: ′ մեքենան այս գործողությունը կատարում է ամեն անգամ, երբ -ն փոխում է որևէ բջջի պա( )-ը կլինի 3-ից ոչ ավերունակությունը: Պարզ է, որ ′-ի համար լի, քանի որ արտագրման գործողության ժամանակ յուրաքանչյուր բջջի պարունակությունը 3-ից ավել անգամ չի փոխվում: Այսպիսով, ( ) ≤ 3, այսինքն ( )-ը Ցեյտինի թեորեմին չի բավարարում: Հետևաբար այն բարդության բնութագրիչ չէ:

Ցեյտինի թեորեմի հաջորդ ընդհանրացումը կատարվել է Ռաբինի կողմից: Թեորեմ (Ռաբին) |8|: Ցանկացած w(ո) արագ աճող ամենուրեք որոշված կարգընթաց ֆունկցիայի համար գոյություն ունի Ռ ( ) ամենուրեք որոշված ֆունկցիա (էֆեկտիվորեն հաշվվող), որը ընդունում է միայն 0 և 1 ար( ) ≥ ( )))2 ժեքներ և ∀ ( : Ռ → (∀ ∈ Ապացույց Ինչպես Ցեյտինի թեորեմի ապացուցման համար, այստեղ ևս կօգտագործվի հերքման եղանակը: Հարմարության համար ներմուծենք Π( ) հերքող ֆունկցիան: Երբ Ռ( ) ֆունկցիայի կառուցման որոշակի քայլում Ռ( ) = ( ), ապա -ն համարվում է հերքված և -ն համարվում է Π( )ի արժեքը, իսկ եթե -ի համար ոչ մի ֆունկցիա չի հերքվում, ապա Π( )-ը որոշված չէ: Ռ( ) ֆունկցիայի սահմանումը կատարվում է ստորև բերվող աղյուսակի հարցումների հիման վրա: Ուշադրություն դարձնենք, որ յուրաքանչյուր սյան մեջ տրվում են մեկ և ավելի հարցումներ: (0) ≤ (0)?

(1) ≤ (1)? (1) ≤ (1)?

(2) ≤ (2)? (2) ≤ (2)? (2) ≤

⋮

⋯

⋯ ( )≤

( )?

( )≤

( )?

( )≤

( )?

(2)? ⋱

⋮

⋱

Սահմանենք Ռ( ) և Π( ) ֆունկցիաները մակածման եղանակով:

∀ ∈ ( )-ով նշանակվում է հետևյալ պնդումը` ∃ ∀ > ( ), այսինքն, գոյություն ունեն միայն վերջավոր հատ -եր, որոնց համար ( )-ն տեղի չունի:

(0) ≤ (0) , ապա Π(0) = 0 և Ռ(0) = = 0 համար, եթե (0), եթե ¬( (0) ≤ (0)), ապա ոչ մի ֆունկցիա չի հերքվում (Π(0) որոշված չէ), իսկ Ռ(0) սահմանվում է «1» կամ «0» (որոշակիության համար վերցնենք Ռ(0) = 1): Ենթադրենք -ից փոքր բոլոր -երի համար Ռ( )-ը որոշված է, և հայտնի են -ից փոքր այն -երը, որոնց համապատասխանող երը արդեն հերքվել են, այսինքն հայտնի է Π(0), Π(1), … , Π( − 1) արժեքների ինֆորմացիան: Ռ( ) և Π( ) -ը սահմանելու համար ստուգվում են հետևյալ հաջորդականության անհավասարումների իսկությունը ( ) ≤ ( ), ( ) ≤ ( ), … , ( ) ≤ ( ): Դրական պատասխանների շարքում ընտրվում է այն նվազագույն -ն ( ≤ ), որը մինչ այդ դեռ չի հերքվել և սահմանվում է և Ռ( ) = ( ): Π( ) = Եթե մինչ այս քայլը չհերքված բոլոր -երի ( ≤ ) համար ճիշտ չէ ( ) ≤ ( ) փաստը, ապա Π( )-ը որոշված չէ և Ռ( ) = 1: Այսպիսով` ( ), եթե Π( ) = ( ≤ ) Ռ( ) = 1, եթե Π( ) որոշված չէ: Քանի որ ցանկացած -ի համար Ռ( )-ը էֆեկտիվորեն հաշվարկվում է (կարգընթաց է), հետևաբար, որոշակի -ի համար Ռ( ) = ( ) ցանկացած -ի համար: Ապացույցը ավարտելու համար բավական է ցույց տալ, որ եթե որևէ -ի համար ∃ ( ( ) ≤ ( )), ապա -ն անպայման հերքվում է, հետևաբար, ∀ ∈ ( ( ) > ( )): Ապացուցենք առավել ուժեղ պնդում` որպեսզի -ն հերքվի, բավական է արգումենտի ( + 1) հատ -ից ոչ փոքր այնպիսի , , …, արժեքների առկայություն, որոնց համար ( ) ≤ ( ) ( = 0, 1, … , ):

Ենթադրենք հակառակը: Այդ դեպքում հերքող ֆունկցիան այդ ( + 1) հատ արժեքների համար պետք է որոշված լինի և ունենա ից փոքր իրարից տարբեր արժեքներ, ինչը հնարավոր չէ: Թեորեմն ապացուցվեց:  Ինչպես և Ցեյտինի թեորեմը, Ռաբինի թեորեմի պնդումը ստույգ է բարդության ցանկացած բնութագրիչի համար: Թեորեմ արագացման մասին (Բլյում) |7|: Ցանկացած ( , ) ընդհանուր կարգընթաց ֆունկցիայի համար գոյություն ունի միայն «0» և «1» արժեքները ընդունող Բ( ) ընդհանուր կարգընթաց ֆունկցիա, որը բավարարում է հետևյալ պայմանին` Բ( ) հաշվարկող ցանկացած Թյուրինգի մեքենայի համար գոյություն ունի նույն Բ( )-ը հաշվարկող այլ Թյուրինգի մեքենա այնպիսի, որ ( )>

∀

, ( ) :

Պարզաբանում: Եթե, օրինակ, ( , ) = 2 , ապա թեորեմը պնդում է, որ գոյություն ունի «0» և «1» արժեքներ ընդունող այնպիսի Բ( ) ֆունկցիա, որ այդ ֆունկցիան հաշվարկող ցանկացած մեքենայի համար կարելի է կառուցել այդ նույն ֆունկցիան հաշվարկող մեքենա այնպիսի, որ ∀

( )>2

( )

:

Թեորեմն ապացուցելու համար նույնպես կիրառվում է անկյունագծային հերքման եղանակը առավել բարդ հարցադրումներով աղյուսակի համար: «Արագացումը» ստացվում է աղյուսակի որոշ մասերում հարցումներ կատարելու «անիմաստության» շնորհիվ: Ապացուցման մանրամասները տես |4)-ում կամ |7)-ում:

88. ԴԵՏԵՐՄԻՆԱՑՎԱԾ ԵՎ ՈՉ ԴԵՏԵՐՄԻՆԱՑՎԱԾ

ԹՅՈՒՐԻՆԳԻ ՄԵՔԵՆԱՆԵՐ

Մինչև այժմ դիտարկված

〈 , , , , 〉 Թյուրինգի մեքենա-

ները դետերմինացված մեքենաներ էին` այն իմաստով, որ յուրաքանչյուր ( , ) զույգի համար ( ∈ , ∈ ) միարժեքորեն որոշվում էր և այն տառը, որը պետք է գրվեր -ի փոխարեն, և հաջորդ քայլին = ( , )∈ վիճակը, և = ( , )∈ համապատասխանող {Ա, Ձ, Տ} գլխիկի շարժման ուղղությունը: Ըստ էության յուրաքանչյուր է պահին Թյուրինգի մեքենայի գործողությունը միարժեքորեն որոշհրաման-հնգյակով, հետևաբար, յուրաքանչյուր վում էր → սկզբնական ընդհանուր վիճակի համար միարժեքորեն էր որոշ, , , … , , … ընդհանուր վիճակների հաջորդականուվում թյունը: 〈 , , 〉 ոչ-դետերմինացված Թյուրինգի մեքենան նկարագրվում է վերը նշված մուտքի այբուբենով, վիճակների բազմությամբ և ⊆ ( × ) × ( × × {Ա, Ձ, Տ}) հարաբերությամբ, համաձայն որի յուրաքանչյուր ( , ) ∈ × զույգին համապատասխանեցվում են ( ≥ 1) հատ ( ) (1 ≤ ≤ ) եռյակներ (անպայման չէ իրարից տարբեր), և հետևաբար ոչ-դետերմինացված Թյուրինգի մեքենան նկարագրվում է հետևյալ տիպի հրամանների համախմբով

∈ ,

,

⋮

∈

և ∈

1≤ ≤ ∈ {Ա, Ձ, Տ}

Պարզ է, որ = 1 դեպքում կունենանք դետերմինացված Թյուրինգի մեքենա: Ոչ դետերմինացված Թյուրինգի մեքենայի աշխատանքը կատարվում է հետևյալ ձևով. մեքենան առաջին քայլում աշխատանքային վիճակից անցնում է , ⋯ , ընդսկզբնական հանուր վիճակներից որևէ մեկին, հաջորդ քայլում` հանուր վիճակներից որևէ մեկին և այլն:

ընդ-

Մեքենայի աշխատանքը համարվում է ավարտված, եթե այն որևէ ճյուղի որևէ քայլում ընդունում է եզրափակիչ աշխատանքային վիճակ: Բերենք մի օրինակ, որը հիմնավորում է ոչ-դետերմինացված Թյուրինգի մեքենաներ դիտարկելու նպատակահարմարությունը: Դիտարկենք, այսպես կոչված, «ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդիրը: Տրված է ո փոփոխականից կախված բուլյան ֆունկցիա` ( , , ⋯ , ): Հարկավոր է ստուգել, այն իրագործելի է, թե՝ ոչ, այ) հավաքածու, որ սինքն`գոյություն ունի արդյոք ( , , ⋯ , ( , , ⋯ , ) = 1: Դիտարկենք հետևյալ նշումներով բինար ծառը.

Հեշտ է համոզվել, որ սահմանելով ոչ-դետերմինացված Թյուրինգի մեքենան այնպես, որ նրա հրամանները համապատասխանեն այս ծառում նշված «ճյուղավորումներին», բանաձևի իրագործելիությունը դրական պատասխանի դեպքում կարելի է ստուգել -ի կարգի քայլեր կատարելով (շարժվելով ( , ⋯ , ) -ից դեպի ( , , ⋯ , ) = 1 գագաթը տանող ճյուղով): Մինչդեռ դետերմինացված Թյուրինգի մեքենա կիրառելով նույն իրավիճակում, հնարավոր է՝ ստիպված լինենք կատարել 2 կարգի քայլ:

89. ,

ԴԱՍԵՐԻ ՍԱՀՄԱՆՈՒՄԸ: ՀԱՆԳԵՑՈՒՄ

Հայտնի խնդիրների մի մեծ դաս վերաբերում է այնպիսի օբյեկտների որոշակի հատկությունների հայտնաբերմանը, ինչպիսիք են գրաֆները, կողմնորոշված գրաֆները, ամբողջ թվերը, ամբողջ թվերի մասիվները, վերջավոր բազմությունների վերջավոր ընտանիքները, բուլյան բանաձևերը և այլն: Որոշակի կոդավորման շնորհիվ կարելի է այդ օբյեկտները փոխարինել {0, 1} այբուբենի բառերով, և թվարկված տիպի խնդիրները վերածել լեզուների (բառերի բազմությունների) ճանաչման խնդիրների ու հետազոտել դրանց հաշվողական բարդությունը: Ցույց կտրվի, որ դասական դժվար լուծելի խնդիրների մեծ մասը իրար համարժեք են այն իմաստով, որ կամ դրանցից յուրաքանչյուրի համար գոյություն ունի բազմանդամային ժամանակում աշխատող դետերմինացված ալգորիթմ, կամ էլ դրանցից ոչ մեկի համար այդպիսի ալգորիթմ գոյություն չունի: Σ = {0, 1} այբուբենում բոլոր հնարավոր վերջավոր բառերի բազմությունը նշանակենք Σ ∗ -ով: Σ ∗ -ի կամայական ենթաբազմությունը անվանենք լեզու: Որոշակի հատկությամբ օժտված վերջավոր օբյեկտների յուրաքանչյուր բազմությանը Σ ∗ -ում համապատասխանում է որոշակի ենթաբազմություն, հետևաբար, այդ հատկության ճանաչման խնդրին համապատասխանում է որոշակի լեզվի ճանաչման խնդիր: Սահմանում 1. ⊆ Σ ∗ լեզուն ճանաչվում է դետերմինացված Թյուրինգի մեքենայի կողմից, եթե ∀ ∈ համար ( )-ը «այո»-ի կոդն է, և ∀ ∉ համար ( )-ը «ոչ»-ի կոդն է: Սահմանում 2. լեզուն ճանաչող դետերմինացված Թյուրինգի մեքենան ճանաչում է լեզուն բազմանդամային ժամանակում, եթե գոյություն ունի ( ) բազմանդամ այնպիսին, որ կամայական հա-

մար ( ) ≤ (| |) , որտեղ ( ) -ը ալգորիթմի ժամանակային բարդությունն է օբյեկտի նկատմամբ կիրառելիս: Սահմանում 3. -ով նշանակենք բոլոր այն լեզուների դասը, որոնք ճանաչվում են որևէ դետերմինացված Թյուրինգի մեքենայի կողմից բազմանդամային ժամանակում: դասը դատարկ չէ: Իրոք՝ 83-ում տրված արդյունքը վկայում է, որ Σ այբուբենի սիմետրիկ բառերի լեզուն -ից է: Բերենք ևս մի քանի խնդիրների օրինակներ, որոնց համապատասխանող լեզուները -ից են:

ԽՆԴԻՐ 1. «2-ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ»

Տրված է ո փոփոխականից կախված կոնյուկտիվ նորմալ տեսքով գրված բուլյան բանաձև` & & … & , k ≥1, ( , ,…, ) = , =1 = ∨ ∨ ⋯∨ ; = =0 ̅, ≠

, եթե

≠ ; 1≤ ,

≤

≤ 2:

Ուշադրություն դարձնենք, որ յուրաքանչյուր տարրական դիզյունկտի փոփոխականների քանակը 2-ից ավելին չէ: Խնդիրը հետևյալն է` պարզել արդյո՞ք բանաձևը իրագործելի է, թե ոչ (այսինքն` այն գոնե մեկ կետում 1 արժեք ընդունում է, թե` ոչ): ԽՆԴԻՐ 2. Տրված է գրաֆը և ք բնական թիվը: Հնարավոր է արդյոք -ից հատ կող հեռացնել այնպես, որ ստացված ՛ գրաֆը դառնա անտառ (ցիկլոմատիվ թիվը լինի 0): Այս երկու խնդիրները դասից են (դրանց լուծման բազմանդամային ընթացակարգերը առաջարկել ինքնուրույն): Սահմանում 4. Π-ով նշանակենք այն ֆունկցիաների դասը, որոնք արտապատկերում են Σ ∗ բազմությունը Σ ∗ -ի մեջ, և որոնց համար գոյություն

ունեն դետերմինացված Թյուրինգի մեքենաներ, որոնք հաշվում են այդ ֆունկցիաները բազմանդամային ժամանակում՝ Π = { / : Σ ∗ → Σ ∗ & ∃ − դետերմինացված Թյուրինգի մեքենա, որը հաշվում է -ը բազմանդամային ժամանակում}: Սահմանում 5. լեզուն հանգեցվում է լեզվին և կնշանակենք` ≺ , եթե գոյություն ունի ∈ Π ֆունկցիա այնպիսին, որ ∈ ⇔ ( ) ∈ : Պարզ է, որ ∀ ⊆ Σ ∗ համար` ≺ , այդ դեպքում` ( ) = : Լեմմա 1 Եթե ≺ և ∈ , ապա ∈ : Իրոք, ≺ նշանակում է` գոյություն ունի ∈ Π այնպիսին, որ ∈ ⇔ ( ) ∈ , իսկ ( ) ∈ պայմանը ստուգվում է բազմանդամային ժամանակում: Դիցուք, -ը հաշվվում է Թյուրինգի մեքենայի միջոցով, իսկ ( ) ∈ ստուգվում է Թյուրինգի մեքենայի միջոցով: Այդ դեպքում ∈ կստուգվի ( ) ալգորիթմի միջոցով, որը նորից բազմանդամային է: Սահմանում 6. Կասենք, որ ոչ-դետերմինացված Թյուրինգի մեքենան ճանաչում է ⊆ Σ ∗ լեզուն, եթե ∀ ∈ համար գոյություն ունի մեքենայի աշխատանքային վիճակների , , … , գոնե մեկ վերջավոր հաաշխատանքային վիճակին հաջորդականություն, այնպիսին, որ -ինը՝ «այո»-ի կոդն է, մապատասխանող ժապավենի բառը -ն է, իսկ ∀ ∉ համար աշխատանքային վիճակների ցանկացած , , … , հաջորդականության համար, եթե -ում վիճակը եզրափակիչ է, ապա ժապավենի բառը «ոչ»-ի կոդն է: Սահմանում 7. ոչ-դետերմինացված Թյուրինգի մեքենան ճանաչում է լեզուն բազմանդամային ժամանակում, եթե գոյություն ունի ( ) բազմանդամ այնպիսին, որ կամայական ∈ համար գոյություն ունի

, ,…, աշխատանքային պրոցես այնպիսին, որ -ին համա–ն «այո»-ի կոդն է և պատասխանող ժապավենի բառը -ն է, իսկ ̃ = ( ) ≤ (| |): Սահմանում 8. -ով նշանակենք բոլոր այն լեզուների դասը, որոնց համար գոյություն ունեն ոչ-դետերմինացված Թյուրինգի մեքենաներ, որոնք ճանաչում են այդ լեզուները բազմանդամային ժամանակում: Ակնհայտ է, որ ⊆ : Դիսկրետ մաթեմատիկայում վերջին տարիներին առաջ քաշված հիմնական պրոբլեմը հակառակ անհավասարության ստուգումն է. ⊇

, այսինքն`

=

∶

Այս պրոբլեմը մինչ այժմ լուծված չէ: Դիտարկենք դասի մի շարք խնդիրներ: 1. «ՔՐՈՄԱՏԻԿ ԹԻՎ» խնդիրը Տրված է ( , ) գրաֆ և ք բնական թիվ: Ստուգել, -ի քրոմատիկ թիվը հավասար է -ին, թե՞ ոչ: 2. «ՀԱՄԻԼՏՈՆՅԱՆ ՑԻԿԼ» խնդիրը Տրված է ( , ) գրաֆ: Ստուգել այնտեղ կա՞ համիլտոնյան ցիկլ, թե՞ ոչ: 3. «ՇՐՋԻԿ ԱՌԵՎՏՐԱԿԱՆ» խնդիրը Տրված են քաղաքներ, դրանց միջև հեռավորությունները հայտնի են. -ն և քաղաքների հեռավորությունն է ( , ∈ 1, ): Տրված է նաև > 0 թիվը: Պարզել, կարող է արդյոք շրջիկ առևտրականը լինել քաղաքներից յուրաքանչյուրում գոնե մեկ ան≤ (∑-ը վերցված է ըստ շրջիկ առևտրագամ, այնպես, որ ∑ կանի անցած ճանապարհի):

4. «ՆԵՐԿԱՅԱՑՈՒՑԻՉՆԵՐԻ ԲԱԶՄՈՒԹՅՈՒՆ» խնդիրը

Տրված են բազմության հատ ենթաբազմություններ և բնական թիվը: Կարելի՞ է ընտրել , , … , ∈ այնպես, որ հատ ենթաբազմություններից յուրաքանչյուրը ունենա այդտեղ ներկայացուցիչ: 5. «ՓԱԹԵԹԱՎՈՐՈՒՄ» խնդիրը Տրված է = { , , … , } առարկաների բազմությունը և ( ) դրանց 1 ≤ ≤ ծավալները: > 0 փաթեթի ծավալն է: Նաև տրված է ք բնական թիվը: Հնարավոր՞ է արդյոք բազմության առարկաները «փաթեթավորել» ք հատ փաթեթներում, այսինքն, տեղի ունե՞ն հետևյալ պայմանները. ( )≤ ∈

,

= 1, :

րդ փաթեթին

6. «ԲԱՌԵՐԻ ԽՄԲԱԳՐՈՒՄ » խնդիրը Տրված է այբուբենը և ∀ , ∈ ∗ : Ունենք խմբագրման երկու գործողություն` տառի ջնջում և երկու տառերի տեղափոխում: Տրված է նաև բնական թիվը: Հնարավո՞ր է արդյոք բառից ստանալ բառը հատ խմբագրման գործողություններով:

7. «ՈՒՍՈՒՄՆԱԿԱՆ ԴԱՍԱՑՈՒՑԱԿՆԵՐ » խնդիրը

Տրված է = { , , … , } առաջադրանքների բազմությունը, ( , ) կողմնորոշված գրաֆը, որը ցիկլ չի պարունակում (այսինքն, նախորդման մասնակի կարգավորվածություն), և ամբողջ թվերը: Հարկավոր է ստուգել, գոյություն ունի՞ այնպիսի : → { 1, 2, … , } ֆունկցիա (կարգացուցակ), որ տեղի ունենան հետևյալ պայմանները. 1) |{ ∶ ( ) = }| ≤ բոլոր ≤ համար: ∈ , ապա ( ) < ( ): 2) Եթե ,

8. «ՈՒՍԱՊԱՐԿ» խնդիրը Տրված է = { , , … , } առարկաների բազմությունը, ( ) թվերը (1 ≤ ≤ ), որոնք բազմության տարրերի կշիռներն են, և ( ) (1 ≤ ≤ ) թվերը, որոնք այդ առարկաների գներն են: Տրված են նաև (կշռի սահմանափակում) և (գների սահմանափակում) } թվերը: Հնարավո՞ր է ընտրել բազմության այնպիսի { , , … , ենթաբազմություն, որ (

)≤

,

(

)≥

∶

9. ԹՎԵՐԻ ՏԵՍՈՒԹՅԱՆ մի խնդիր՝ Տրված են , , բնական թվերը: Գոյություն ունի՞ > թիվ, ≡ (mod ) ( -ն համեմատելի է -ի հետ ըստ այնպիսին, որ մոդուլ -ի): 10. «ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ » խնդիրը Տրված է ( , , … , ) փոփոխականներից կախված բուլյան ֆունկցիան: Ստուգել, այն իրագործելի է, թե՞ ոչ (այսինքն, գոյություն ունի՞ փոփոխականների արժեքների այնպիսի ∈ {0, 1} ( , , … , ) հավաքածու, որ ( , , … , ) = 1 , ( = 1, ):

11. «ԱՎՏՈՄԱՏՆԵՐԻ ԻԶՈՄՈՐՖՈՒԹՅՈՒՆ» խնդիրը

և ավտոմատները: Ստուգել, դրանք իզոմորֆ Տրված են ե՞ն, թե՞ ոչ (երկու ավտոմատներ իզոմորֆ են, եթե նրանք ճանաչում են նույն բազմությունը): 12. «3-ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդիրը նախկինում նկարագրված «2-ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդրից տարբերվում է

միայն նրանով, որ այստեղ յուրաքանչյուր -ի (1 ≤ ≤ ) փոփոխականների քանակը 3-ից մեծ չէ: Դժվար չէ ցույց տալ, որ «ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդիրը հանգեցվում է «3-ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդրին: Սահմանում 9: լեզուն (խնդիրը) կոչվում է -լրիվ (ՀPՇօոքlօէօ), եթե 1) ∈ 2) -ի ցանկացած լեզու (խնդիր) հանգեցվում է -ին: Այժմ հայտնի են 500-ից ավելի -լրիվ խնդիրներ (մասնավորապես, հաջորդ պարագրաֆում ապացուցվում է «Իրագործելիու-լրիվությունը): թյուն» խնդրի Սահմանում 10: լեզուն (խնդիրը) կոչվում է -դժվար (ՀPhճrմ), եթե -ի ցանկացած լեզու (խնդիր) հանգեցվում է -ին: Հետևյալ սխեմաները ցուցադրում են բոլոր վերոհիշյալ դասերի հնարավոր հարաբերությունները՝

810. ԿՈՒԿԻ–ԿԱՐՊԻ–ԼԵՎԻՆԻ ԹԵՈՐԵՄԸ

Հետագայում այս կամ այն խնդրի լեզու ասելով հասկանալու ենք Σ ∗ -ի այն բառերի ենթաբազմությունը, որոնք հանդիսանում են տվյալ խնդրի պայմաններին բավարարող օբյեկտների կոդերը: Թեորեմ (ԿՈՒԿ–ԿԱՐՊ–ԼԵՎԻՆ)|2|: Եթե ∈ , ապա ≺«ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդրի լեզվին: Ապացույց ∈ նշանակում է, որ գոյություն ունի ոչ-դետերմինացված Թյուրինգի մեքենա, որը ճանաչում է լեզուն բազմանդամային ժամանակում, այսինքն` գոյություն ունի ( ) բազմանդամ, այնպիսին, որ ∀ ∈ համար գոյություն ունի բառին համապատասխանող սկզբնական ընդհանուր վիճակով սկսվող աշխատանքային վիճակների վերջավոր հաջորդականություն, որի երկարությունը բավարարում է ( ) ≤ (| |) պայմանին: Առանց ընդհանրությունը խախտելու կարելի է ենթադրել, որ Թյուրինգի մեքենան միակողմանի է դեպի աջ: Իրոք, քանի որ ցանկացած Թյուրինգի մեքենայի համար կարելի է կառուցել միակողմանի Թյուրինգի մեքենա, որը համարժեք է -ին և ունի ոչ ավելի, քան քայլերի բազմանդամային աճ -ի քայլերի համեմատությամբ: Մեր միակողմանի Թյուրինգի մեքենայի ժապավենի բջիջները համարակալենք հետևյալ կերպ. ∥

⋯

̃

որտեղ ̃ = (| |) (պարզ է, որ ̃ -ն կախված է 5-ից, սակայն այդ կախվածությունը մենք ամեն անգամ չենք նշի գրառումները չծանրաբեռնելու նպատակով):

Դիցուք Թյուրինգի մեքենայի մուտքի այբուբենը հետևյալն է. = Λ, =«այո»-ի կոդն է: = { , , … , }, որտեղ` , = }, որՎիճակների բազմությունն է` = { , , … , տեղ -ն սկզբնական վիճակն է, = -ն` եզրափակիչ վիճակը: մեքենան ոչ-դետերմինացված է, այսինքն, որոշակի բնական թվի համար մեքենայի հրամանները ունեն այսպիսի տեսք.

ղ 0≤ ≤

− 1

0≤ ≤ ⋮

Դիցուք,

∈

0≤

, ,…,

≤

0≤

, ,…,

≤

բառը ունի հետևյալ տեսքը. , ,…, =

այսինքն, Թյուրինգի մեքենայի սկզբնական ընդհանուր վիճակը այսպիսին է (նշանակենք այն -ով). ∥ … Քանի որ ∈ , ապա մեքենան ոչ ավելին, քան ̃ քայլերից հետո կդադարեցնի աշխատանքը և կպատասխանի «այո», այսինքն` կգա հետևյալ եզրափակիչ աշխատանքային վիճակին (նշանակենք ով). այն ∥

Յուրաքանչյուր ∈ ∑∗ բառի համար կառուցենք կոնյուկտիվ նորմալ տեսքով տրված այնպիսի բուլյան բանաձև. Ա( ) =

&

&

&

& & ,

որը լինի իրագործելի այն և միայն այն դեպքում, երբ ∈ : Նշենք, որ , , , , H, բանաձևերից յուրաքանչյուրը նույնպես կախված է -ից, սակայն այդ կախվածությունը մենք ամեն անգամ չենք նշի գրառումները չծանրաբեռնելու նպատակով: Ներմուծենք հետևյալ փոփոխականները. 1, եթե է-րդ պահին Տ-րդ բջջում գրված է aզ տառը = հակառակ դեպքում 0, = =

1, 0, 1, 0,

եթե է-րդ պահին գլխիկը գտնվում է qզ վիճակում հակառակ դեպքում եթե է-րդ պահին գլխիկը դիտարկում է Տ-րդ բջիջը հակառակ դեպքում

0 ≤ ≤ ̃ ,0 ≤ ≤ ̃ ,0 ≤ ≤ , 0 ≤ ≤ : , , , , H, բանաձևերը սահմանենք այնպես, որ , և «նկարագրեն» մեքենայի էությունը, սկզբնական աշխատանքային վիճակը, -ն` մեքենայի -ն`եզրափակիչ աշխատանքային վիճակը, իսկ H-ը` ընդհանուր քայլը (մեքենայի աշխատանքի ընթացքը): բանաձևը կառուցենք այնպես, որ բավարարվի հետևյալ պայմանը. =

1,

եթե ∀ -րդ պահին գլխիկը գտնվում է մեկ և միայն մեկ վիճակում

0,

հակառակ դեպքում

Այսինքն, կարելի է գրել. =&

, որտեղ

1,

=

եթե t-րդ պահին մեքենայի գլխիկը գտնվում է մեկ և միայն մեկ վիճակում հակառակ դեպքում

0,

Այս պայմանին բավարարում է հետևյալ բանաձևը =(

∨ &

Կատարելով

)&

∨ ⋯∨ =

&

&

∨

∶

ձևափոխությունը,

-ն կա-

րելի է բերել կոնյուկտիվ նորմալ տեսքի: Այժմ նկարագրենք բանաձևը. =

1, 0,

եթե ∀ -րդ պահին գլխիկը դիտարկում է մեկ և միայն մեկ բջիջ հակառակ դեպքում

=& =

1, 0,

, որտեղ

եթե -րդ պահին գլխիկը դիտարկում է մեկ և միայն մեկ բջիջ հակառակ դեպքում

Այսինքն` =

∨

∨ ⋯∨

&

(

&

&

)

բանաձևը նույնպիսի ձևափոխությունից հետո, ինչպես բերվում է կոնյուկտիվ նորմալ տեսքի: Սահմանենք բանաձևը` =

1, 0,

եթե ∀ պահին ∀ -րդ բջջում գրված է մեկ և միայն մեկ տառ հակառակ դեպքում

=& =

1, 0,

-ում,

=&

&

, որտեղ`

եթե -րդ պահին -րդ բջջում գրված է մեկ և միայն մեկ տառ հակառակ դեպքում

=(

∨

)&

&

∨

:

բանաձևը կառուցենք հետևյալ պայմանին բավարարող`

( )=

&

&

&&

, որտեղ

= | |,

այսինքն` ժապավենի վրա սկզբնական վիճակում գրված է 5, մնացած բջիջներում գրված է Λ: Մեքենայի աշխատանքի ընթացքը «նկարագրող» H բանաձևը կառուցենք որպես երկու՝ և 5t բանաձևերի կոնյունկցիա, որոնցից -ը յուրաքանչյուր քայլի համար «արտահայտում է» աշխատանքային վիճակի փոփոխությունները, իսկ 5t –ն « ֆիքսում է» քայլի կատարումից հետո աշխատանքային վիճակի անփոփոխ մնացած ինֆորմացիան: բանաձևը կառուցենք հետևյալ ձևով` =&

&

&

,,

( ̃ − րդ պահին ոչինչ չի կատարվում, հետևաբար, նայում ենք մինչև ̃ − 1պահը) ,,

1,

եթե -րդ պահին գլխիկի

0,

մեքենան կատարում է համապատասխան հրամաններից որևէ մեկը, հակառակ դեպքում

=

,,

,,

=&

վիճակում, դիտարկելով

,,

տառը

, որտեղ

1,

եթե -րդ պահին

0,

մեքենան կատարում է համապատասխան հրամաններից որևէ մեկը, հակառակ դեպքում

=

վիճակում, -րդ բջիջում դիտարկելով

Եթե որոշակիության համար ենթադրենք, որ = Տ, ապա կունենանք

= Ա,

տառը

=Ձև

,,

=

&

& ⊃

&

&

∨

&

&

∨

&

&

∨⋯

:

Այստեղ իմպլիկացիան փոխարինելով դիզյունկցիայով և ժխտումով, կարող ենք բանաձևը բերել կոնյունկտիվ նորմալ տեսքի: 5t բանաձևը «ֆիքսում է» այն փաստը, որ տվյալ քայլում չդիտարկվող բոլոր բջիջները պահպանում են իրենց պարունակությունը՝ 5t= &

&

&

(⏋

&

⊃

):

Այստեղ ևս իմպլիկացիան փոխարինելով դիզյունկցիայով և ժխտումով, կարող ենք բանաձևը, հետևաբար նաև H բանաձևը բերել կոնյունկտիվ նորմալ տեսքի: բանաձևը գրենք հետևյալ ձևով` =

&

& &

&

&

Կառուցված Ա( ) = & & & & & բանաձևը կլինի իրագործելի այն և միայն այն դեպքում, երբ պատասխանը «այո» է, այսինքն ∈ : 

ԳՐԱԿԱՆՈՒԹՅՈՒՆ

1. Барздинь Я. М., Сложность распознавания симметрии на машинах Тьюринга, Проблемы кибернетики, 15, 1965, 245-248. 2. Кибернетический сборник, Новая серия, Вып.12, И-во «Мир», 1975. 3. Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965. 4. Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосибирск, НГУ, 1967. 5. Цейтин Г. С., Оценка числа шагов при применении нормального алгоритма, Математика в СССР за 40 лет, т. 1, М., 1959, 44-45. 6. Bluո Խ., RօՇurՏiԾօ fuոՇէiօոՏ էhօօry ճոմ Տքօօմ օf ՇօոքuէճէiօոՏ, Շճոճմ. հճէh. Bull., 9, 1966, 6, 745-750. 7. Bluո Խ., Ճ ոճՏhiոօ iոմօքօոմօոէ էhօօry օf էhօ Շօոքlօ5iէy օf rօՇurՏiԾօ fuոՇէiօոՏ, J. ՃՏՏօՇ. Շօոք. հճէh., 14, 1967, 322-337. 8. Rոbin Խ. O., Տքօօմ օf Շօոքuէճէiօո օf fuոՇէiօոՏ ճոմ ՇlճՏՏifiՇճէiօո օf rօՇurՏiԾօ ՏօէՏ, Bull. RօՇ. ՇօuոՇ. օf 1Տrճօl, 8F, 1959, 69-70.

ԵՐԵՎԱՆԻ ՊԵՏԱԿԱՆ ՀԱՄԱԼՍԱՐԱՆ

Անահիտ Չուբարյան Հռիփսիմե Մովսեսյան Սերգեյ Սայադյան

ՀԱՇՎԱՐԿԵԼԻՈՒԹՅԱՆ ԲԱՐԴՈՒԹՅԱՆ

ՏԵՍՈՒԹՅԱՆ ՀԻՄՆԱԴՐՈՒՅԹՆԵՐԸ

Համակարգչային ձևավորող՝ Կ. Չալաբյան Շապիկի ձևավորող` Ա. Պատվականյան Հրատ. սրբագրող՝ Վ. Դերձյան

Տպագրված է ՀՀ ԿԱ ՊԵԿ «Ուսումնական կենտրոն» ՊՈԱԿ-ի Հրատարակչական մասի տպարանում: ք. Երևան, Ահարոնյան 12/3

Ստորագրված է տպագրության՝ 02.07.2017: Չափսը՝ 605841/16: Տպ. մամուլը՝ 3.875: Տպաքանակը՝ 100: ԵՊՀ հրատարակչություն ք. Երևան, 0025, Ալեք Մանուկյան 1 www.քubliՏhiոg.yՏu.ճո

Ա. Ա. Չուբարյան Հ. Գ. Մովսեսյան Ս. Մ. Սայադյան

ՀԱՇՎԱՐԿԵԼԻՈՒԹՅԱՆ

ԲԱՐԴՈՒԹՅԱՆ ՏԵՍՈՒԹՅԱՆ

ՀԻՄՆԱԴՐՈՒՅԹՆԵՐԸ