Թյուրինգի մեքենաների օրինակներ. Թյուրինգ մեքենայի վրա ֆունկցիաների ճիշտ հաշվարկելիությունը
Թյուրինգի մեքենան (MT) վերացական կատարող է (աբստրակտ հաշվողական մեքենա):
Ալգորիթմների համակցությունները այն անվանումն է, որը հաստատվել է մի քանի տրվածներից նոր ալգորիթմներ կառուցելու մի շարք հատուկ մեթոդների համար:
Ալգորիթմների համակցությունների թեորեմները կազմում են ալգորիթմների ընդհանուր տեսության կարևոր բաժինը։ Ապացուցվելուց հետո դրանք հնարավորություն են տալիս հետագայում ստուգել բարդ և ծանր ալգորիթմների իրագործելիությունը՝ առանց իրականում դուրս գրելու դրանք սահմանող սխեմաները:
Թյուրինգ մեքենայի ալգորիթմների համակցությունները նկարագրվում են Թյուրինգի մեքենաների վրա կատարված գործողություններով:
1. Կոմպոզիցիայի գործողություն.
Թող M 1 և M 2 լինեն Թյուրինգի մեքենաներ, որոնք ունեն նույն արտաքին այբուբենը A« (a 0,a 1,...,a p ): Նրանց վիճակների բազմությունները նշանակենք համապատասխանաբար Q1 " (q 0 ,q 1 ,...,q n ) և Q2 " (q 0" ,q 1" ,...,q m" ):
Սահմանում.
M 1 և M 2 մեքենաների կազմը M=M 1 ×M 2 նշանակված մեքենա է, որի ծրագիրն ունի A այբուբեն, Q« վիճակների բազմություն (q 0,q 1,...,q n,q. n+1,... ,q n+m) և ստացվում է M 1 և M 2 մեքենաների ծրագրերից հետևյալ կերպ՝ M 1 մեքենայի ծրագրում ամենուր, որտեղ առկա են q 1 նշանով «եռապատկերներ». M 1 մեքենայի վերջնական վիճակը), այն փոխարինվում է q 0" նշանով (Մ 2 մեքենայի սկզբնական վիճակ); M 1 և M 2 մեքենաների ծրագրերի բոլոր այլ նշանները մնում են անփոփոխ (ի վերջո, այդ ամենը. մնում է վերահամարակալել M մեքենայի բոլոր վիճակները՝ (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )):
Կազմը սկսում է «աշխատել» որպես M 1 մեքենա, բայց այն դեպքերում, երբ M 1 մեքենան պետք է կանգնի, այն անցնում է M 2 մեքենայի ծրագրին, q 1-ը q 0-ով փոխարինելու պատճառով»: Ակնհայտ է. կոմպոզիցիայի գործողությունը ասոցիատիվ է, բայց ոչ կոմուտատիվ:
Դրա աշխատանքը համարժեք է T1 և T2 մեքենաների հաջորդական աշխատանքին:
Նկարը ցույց է տալիս Թյուրինգի մեքենաների կազմը, որն իրականացնում է սուպերպոզիցիոն օպերատորը n=1 և m=1 համար:
Նկար 1.
Սահմանում.
Թյուրինգ մեքենայի M-ի կրկնությունը կկոչվի մեքենա
2. Ճյուղավորման շահագործում.
Թող M 1, M 2 և M 3 լինեն Թյուրինգի մեքենաներ, որոնք ունեն նույն արտաքին այբուբենը A« (a 0, a 1,...,a i,...,a j,...,a p) և, համապատասխանաբար, բազմություններ. վիճակներ՝ Q1" (q 0,q 1,...,q n), Q2" (q 0" ,q 1" ,...,q m"), Q3" (q 0", q 1" ,.. ., ք լ»):
Սահմանում.
M 1, M 2 և M3 Թյուրինգ մեքենաների վրա ճյուղավորվող գործողության արդյունքը կոչվում է Turing մեքենա M, որի ծրագիրը ստացվում է M 1, M 2 և M 3 մեքենաների ծրագրերից հետևյալ կերպ. գրվում է M1 մեքենան, ապա նշանակվում են M 2 և M 3 մեքենաների ծրագրերը։ Եթե M1 մեքենայի q 1 վերջնական վիճակում դիտվում է a i նշանը, ապա կառավարումը փոխանցվում է M 2 մեքենային, այսինքն. խորհրդանիշ q 1 փոխարինվում է խորհրդանիշով q 0" և սկսում է աշխատել M 2 մեքենան: Եթե M 1 մեքենայի q 1 վերջնական վիճակում դիտվում է a j նշանը, ապա կառավարումը փոխանցվում է M 3 մեքենային, այսինքն՝ խորհրդանիշը q 1 փոխարինվում է: q 0" նշանով և M 3 մեքենան սկսում է աշխատել: M 1 և M 2 մեքենաների ծրագրերում մնացած բոլոր նշանները մնում են անփոփոխ: Մ մեքենան ավարտում է իր աշխատանքը q 1 վերջնական վիճակում (ամփոփելով՝ մնում է իրականացնել M մեքենայի վիճակների վերջից մինչև վերջ վերահամարակալումը):
Թյուրինգի M 1, M 2 և M3 մեքենաների վրա ճյուղավորվող աշխատանքի արդյունքը նշվում է հետևյալ կերպ.
Երկու տառանոց Turing մեքենաների համար (Turing մեքենաներ երկու տառանոց այբուբենով) կամայական Turing մեքենաների M1, M2 և M3 ճյուղավորման գործողությունը նշվում է հետևյալ կերպ.
դրանք. եթե M1 մեքենան աշխատում է q 1 վիճակում, ապա դիտվում է a 0 նշանը, ապա կառավարումը փոխանցվում է M2 մեքենային, հակառակ դեպքում՝ M3 մեքենային:
3. Looping գործողություն.
Թող M լինի Թյուրինգի մեքենա՝ A« (a 0 ,a 1 ,...,a p ) այբուբենով և Q« (q 0 ,q 1 ,...,q n ) վիճակների բազմությամբ։
Սահմանում.
Looping գործողության արդյունքը կկոչվի Turing մեքենա, որը կնշանակվի (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)
որի ծրագիրը ստացվում է M մեքենայի ծրագրից՝ q i a j ®q 1 a t r, rՕ(L,R,L), t=0,1,2,.. հրամանի արդյունքում q 1 նշանը փոխարինելով: .p, q s նշանով:
2.4 Թյուրինգ մեքենայի տարբերակները
Turing մեքենայի մոդելը կարող է երկարաձգվել: Կարելի է դիտարկել Թյուրինգի մեքենաները կամայական թվով ժապավեններով և բազմաչափ ժապավեններով՝ տարբեր սահմանափակումներով։ Այնուամենայնիվ, այս բոլոր մեքենաները Turing ամբողջական են և մոդելավորվում են սովորական Turing մեքենայի կողմից:
Որպես նման համարժեքության օրինակ, դիտարկենք ցանկացած ՄՏ-ի կրճատումը կիսաանսահման ժապավենի վրա գործող ՄՏ-ի:
Թեորեմ.Ցանկացած Թյուրինգ մեքենայի համար կա կիսաանսահման ժապավենի վրա աշխատող Թյուրինգի համարժեք մեքենա:
Ապացույց:
Դիտարկենք Յու.Գ.Կարպովի ապացույցը. Այս թեորեմի ապացույցը կառուցողական է, այսինքն՝ կտանք ալգորիթմ, որով ցանկացած Թյուրինգ մեքենայի համար կարող է կառուցվել հայտարարված հատկությամբ համարժեք Թյուրինգի մեքենա։ Նախ, մենք պատահականորեն համարակալում ենք MT աշխատանքային ժապավենի բջիջները, այսինքն, մենք որոշում ենք ժապավենի վրա տեղեկատվության նոր տեղադրությունը.
Նկար 1.
Այնուհետև մենք վերահամարակալում ենք բջիջները և կենթադրենք, որ «*» նշանը չի պարունակվում MT բառարանում.
Նկար 1.
2.5 Թյուրինգի հաշվարկելիություն և որոշելիություն
Վերևում ապացուցվեց, որ ռեկուրսիվ ֆունկցիաների, Թյուրինգի մեքենաների կամ Մարկովի նորմալ ալգորիթմների միջոցով հաշվարկվող ֆունկցիաների դասերը համընկնում են։ Սա թույլ է տալիս մեզ համարել «հաշվարկային ալգորիթմ» հասկացությունը նկարագրության մեթոդի անփոփոխ: Տարբերությունները նկատվում են միայն ալգորիթմական օբյեկտների օգտագործման մեջ։ Եթե ռեկուրսիվ ֆունկցիաների համար օբյեկտները թվեր և թվային ֆունկցիաներ են, և հաշվարկման գործընթացը սահմանվում է սուպերպոզիցիայի, ռեկուրսիայի, նվազագույնի և կրկնության օպերատորների կողմից, ապա Թյուրինգի մեքենաների համար այդպիսի օբյեկտները արտաքին և ներքին հիշողության այբուբենների և հաշվարկի խորհրդանիշներն են: գործընթացը նշված է արձանագրությամբ՝ օգտագործելով ելքը, անցումը և գլուխը շարժելը: Նորմալ Մարկովի ալգորիթմի համար նման առարկաները բառեր կամ նշանների հաջորդականություններ են, և հաշվարկման գործընթացը սահմանվում է փոխարինման կանոններով կամ ապրանքներով, որոնք փոխում են սկզբնական նշանների հաջորդականության կազմը և կառուցվածքը ցանկալի արդյունքի:
Թվաբանական (թվային) ֆունկցիան այն ֆունկցիան է, որի արժեքների միջակայքը N բազմության ենթաբազմությունն է, իսկ սահմանման տիրույթը N բազմության տարրն է:
Ալգորիթմական խնդիրների համար բնորոշ իրավիճակ է, երբ անհրաժեշտ է գտնել f(x 1, x 2, ..., x n) թվային ֆունկցիայի հաշվարկման ալգորիթմ՝ կախված x 1, x 2 արգումենտների ամբողջական արժեքներից: , ..., x n.
Մենք անվանում ենք f:N n →N ֆունկցիան հաշվարկելի, եթե կա ալգորիթմ, որը թույլ է տալիս իր արգումենտների արժեքների ցանկացած հավաքածու հաշվարկել ֆունկցիայի արժեքը (կամ ցույց տալ, որ ֆունկցիան սահմանված չէ տվյալ բազմության վրա): Քանի որ հաշվարկելի ֆունկցիայի սահմանման մեջ օգտագործվում է ալգորիթմի ինտուիտիվ հայեցակարգը, «հաշվարկվող ֆունկցիա» տերմինի փոխարեն հաճախ օգտագործվում է «ինտուիտիվ հաշվարկելի ֆունկցիա» տերմինը: Այսպիսով, զանգվածային խնդիրը լուծում ունի, եթե խնդրին համապատասխան թվաբանական ֆունկցիան ինտուիտիվորեն հաշվարկելի է։
F(x 1, x 2, …, x n) ֆունկցիան կոչվում է արդյունավետորեն հաշվարկելի, եթե տրված արժեքների համար k 1 , k 2 , …, k n արգումենտների համար կարելի է գտնել f(k 1, k 2 , ֆունկցիայի արժեքը, …, k n) օգտագործելով գոյություն ունեցող մեխանիկական ընթացակարգեր (ալգորիթմ):
Ալգորիթմի հայեցակարգը պարզաբանելու փոխարեն մենք կարող ենք դիտարկել «հաշվարկվող ֆունկցիայի» հասկացության պարզաբանումը։ Սովորաբար նրանք ընթանում են հետևյալ սխեմայով.
1. Ներկայացվում է ֆունկցիաների հստակ սահմանված դաս։
2. Համոզվեք, որ այս դասի բոլոր գործառույթները հաշվարկելի են:
3. Ընդունեք այն վարկածը (թեզը), որ հաշվարկելի ֆունկցիաների դասը համընկնում է ներդրված ֆունկցիաների դասի հետ։
Ֆունկցիան կոչվում է հաշվարկելի, եթե կա այն հաշվարկող ալգորիթմ: «Հաշվարկելիությունը» ալգորիթմների տեսության հիմնական հասկացություններից է, որն անփոփոխ է հաշվարկվող ֆունկցիայի և ալգորիթմի նկատմամբ: Հաշվարկվող ֆունկցիայի և ալգորիթմի միջև տարբերությունը ֆունկցիայի նկարագրության և դրա արժեքները հաշվարկելու ձևի տարբերությունն է՝ հաշվի առնելով անկախ փաստարկների արժեքները:
Թյուրինգի թեզը. Ցանկացած ինտուիտիվ ալգորիթմ կարող է իրականացվել Turing մեքենայի միջոցով:
Թյուրինգի թեզից հետևում է, որ եթե առաջանում են ալգորիթմական խնդիրներ, ապա դրանք պետք է լուծվեն Թյուրինգի մեքենաների կառուցման հիման վրա, այսինքն՝ ալգորիթմի բավականաչափ ձևավորված հայեցակարգի հիման վրա։ Ավելին, ալգորիթմական խնդիրներում մենք հաճախ խոսում ենք ոչ թե ալգորիթմի կառուցման, այլ որոշ հատուկ կառուցված ֆունկցիաների հաշվելիության մասին։
Հարկ է նշել, որ այս դեպքերում բավական է օգտագործել այբուբենը (0,|), որտեղ 0-ը դատարկ գրանշանն է։ Օրինակ, բնական թվերը, ներառյալ 0-ը, այս այբուբենում կոդավորված են հետևյալ կերպ. 0 - |; 1 - ||; 2 -
N - ||…| (n + 1 անգամ): Մասնակի թվային n-տեղական f(x1, x2, ..., xn) ֆունկցիան կոչվում է Թյուրինգ հաշվարկելի, եթե կա M մեքենա, որը հաշվարկում է այն հետևյալ իմաստով. 1. Եթե արգումենտների արժեքների բազմությունը.
ԻՆՔՆԱԽՆԴԻՐԸ
Ըստ Թյուրինգի մեքենայի սահմանման՝ սա եռակի է T=
P: q iա ա ժա ® q rա ա սա Ս տա , a = 1, 2, …, k , Որտեղ Ս 1- Ռ, Ս 2-Լ, Ս 3- Գ . (*)
Այս դեպքում կարելի է ենթադրել, որ կան որոշ ընդհանուր այբուբեններ A 0Եվ Q 0, որում գրված են նիշեր ա Եվ ք բոլոր Turing մեքենաների համար: Այնուհետեւ խորհրդանիշները q iա, ա ժա, q rա, ա սա, Ս տաայբուբենների խորհրդանիշներ են A 0Եվ Q 0.
Այս մոտեցումը թույլ է տալիս բոլոր Թյուրինգ մեքենաներին համարակալել, այսինքն՝ յուրաքանչյուր մեքենային հատկացվում է այս մեքենային հատուկ որոշակի թիվ (կոդ), որով այն կարելի է տարբերել այլ մեքենաներից։ Այստեղ մենք կքննարկենք համարակալման մեթոդներից մեկը:
Թյուրինգի մեքենաների գոդելյան համարակալում. Թող p 1, p 2, p 3 , ... - աճման կարգով դասավորված պարզ թվերի հաջորդականություն, օրինակ՝ 2, 3, 5, 7, 11, 13, ...
Թյուրինգ մեքենայի համարը ծրագրով (*)զանգահարած համարը
n(T) = .
Օրինակ
Մեքենա, որն իրականացնում է ֆունկցիա Ս(x)= x + 1 , այբուբենով ծրագիր ունի {0, } . Այս ծրագրի թիվը՝ հաշվի առնելով այն հանգամանքը, որ ա 0 = 0 , ա 1= | կլինի մի թիվ.
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3:
Ակնհայտ է, որ ոչ բոլոր բնական թվերն են Թյուրինգի մեքենայի թվեր։ Մյուս կողմից, եթե n – որոշակի մեքենայի թիվը, ընդհանուր այբուբեններով, ապա դրա ծրագիրը կարող է եզակի կերպով վերականգնվել այս թվից:
Ավտոմեքենա Տ, կիրառելի բառին n(T)(այսինքն՝ ձեր սեփական համարի կոդը), կոչվում է ինքնուրույն կիրառելի .
Հնարավոր է կառուցել և՛ ինքնուրույն կիրառելի մեքենաներ, և՛ ոչ ինքնակիրառական մեքենաներ: Օրինակ՝ տրված օրինակի մեքենան ինքնակիրառելի է։ Ավտոմեքենա Տ, որը ծրագրի աջ հատվածներում (աղյուսակի մարմնում) չունի կանգառի նշան, կիրառելի չէ որևէ բառի և, հետևաբար, բառի վրա. n(T).
Ինքնակիրառման խնդիրցույց տալ ալգորիթմ, որը, հաշվի առնելով Թյուրինգի ցանկացած մեքենա, կորոշի արդյոք այն ինքնուրույն կիրառելի է, թե ոչ:
Ըստ Թյուրինգի թեզի՝ նման ալգորիթմը պետք է փնտրել Թյուրինգի մեքենայի տեսքով։ Այս մեքենան պետք է կիրառելի լինի բոլոր Թյուրինգ մեքենաների համարների կոդերի համար և կախված փորձարկվող մեքենաների կոդերի մշակման արդյունքից, կունենա տարբեր վերջնական կոնֆիգուրացիաներ։
Եկեք, օրինակ, այս մեքենան Տկիրառվում է կոդի վրա n(Տ * ) . Եթե մեքենան Տ * ինքնուրույն կիրառելի, ապա վերջնական մեքենայի կոնֆիգուրացիան Տնման է ա" q 0 | Բ», իսկ եթե մեքենան Տ * ինքնուրույն կիրառելի չէ, ապա մեքենայի վերջնական կոնֆիգուրացիան Տնման է ա" q 0 0 Բ ". Այստեղ ա», Բ», ա», Բ»- բառեր.
ԹեորեմԻնքնակիրառելիության խնդիրը ալգորիթմորեն անորոշ է, այսինքն՝ չկա Թյուրինգի մեքենա, որը լուծի այս խնդիրը վերը նշված իմաստով։
Թեորեմից հետևում է, որ չկա ընդհանուր ալգորիթմ, որը լուծում է ինքնակիրառության խնդիրը։ Հատուկ հատուկ դեպքերում նման ալգորիթմներ կարող են լինել:
Եկեք օգտագործենք այս թեորեմի արդյունքները՝ սկզբնական բառի նկատմամբ կիրառելիության խնդրի անորոշությունն ապացուցելու համար։
Նախնական բառի նկատմամբ կիրառելիության խնդիրը հետևյալն է՝ ստեղծել ալգորիթմ, որը, ըստ մեքենայի Տև խոսքը X կտեղադրեր, կիրառելի մեքենա Տիմիջայլոց X թե ոչ (հակառակ դեպքում կա կանգառի խնդիր):
Թյուրինգի մեքենաների առումով, ինչպես ինքնակիրառման խնդրի ձևակերպումը, այս խնդիրը ձևակերպված է հետևյալ կերպ. հնարավո՞ր է արդյոք կառուցել այնպիսի մեքենա, որը կիրառելի կլինի ձևի բոլոր բառերի համար. n(T) 0 X , Որտեղ Տկամայական մեքենա, X – կամայական բառ, իսկ եթե մեքենան Տկիրառելի բառի համար X ա" q 0 |Բ» , իսկ եթե մեքենան Տբառի համար կիրառելի չէ X , կհանգեցնի վերջնական կոնֆիգուրացիայի ա" q 0 0 B" . Այստեղ ա", Բ"Եվ ա», Բ»- կամայական խոսքեր.
ԹեորեմՍկզբնական բառի նկատմամբ կիրառելիության խնդիրը ալգորիթմորեն անորոշ է, այսինքն՝ չկա Թյուրինգի մեքենա, որը լուծի այս խնդիրը վերը նշված իմաստով։
Ինչպես նշվեց վերևում, ինքնուրույն կիրառելիության խնդրի համար, առաջին նախնական քայլը համարակալումն է: Հետևաբար, ստորև այս խնդիրը հետևողականորեն դիտարկվում և լուծվում է ալգորիթմների և նրա երեք հիմնական տեսակի ալգորիթմական մոդելների համար:
Ալգորիթմների համարակալում
Ալգորիթմների համարակալումը կարևոր դեր է խաղում դրանց հետազոտության և վերլուծության մեջ: Քանի որ ցանկացած ալգորիթմ կարող է սահմանվել որպես վերջավոր բառ (ներկայացվում է որպես որոշ այբուբենի խորհրդանիշների վերջավոր հաջորդականություն), իսկ վերջավոր այբուբենի բոլոր վերջավոր բառերի բազմությունը հաշվելի է, ապա բոլոր ալգորիթմների բազմությունը նույնպես հաշվելի է։ Սա նշանակում է բնական թվերի բազմության և ալգորիթմների բազմության միջև մեկ առ մեկ քարտեզագրման առկայություն, այսինքն՝ յուրաքանչյուր ալգորիթմին թիվ վերագրելու կարողություն։
Ալգորիթմների համարակալումը նաև բոլոր ալգորիթմորեն հաշվարկվող ֆունկցիաների համարակալումն է, և ցանկացած ֆունկցիա կարող է ունենալ անսահման թվով թվեր։
Համարակալման առկայությունը թույլ է տալիս ալգորիթմների հետ աշխատել այնպես, ինչպես թվերի հետ։ Համարակալումը հատկապես օգտակար է այլ ալգորիթմների հետ աշխատող ալգորիթմների ուսումնասիրության մեջ։
Թող լինի որոշակի զանգվածային խնդիր X սկզբնական օբյեկտների բազմության և Y ցանկալի առարկաների բազմության հետ: Զանգվածի խնդրի լուծման համար անհրաժեշտ է, որ X և Y բազմությունների տարրերը լինեն կառուցողական առարկաներ: Հետևաբար, այս բազմությունների տարրերը կարելի է համարակալել բնական թվերով։ Թող x∈ X լինի ինչ-որ սկզբնական օբյեկտ, նրա թիվը նշանակենք n(x-ով): Եթե սկզբնական x-ի զանգվածի խնդիրում պահանջվում է ստանալ n(y) թվով y∈ Y ցանկալի օբյեկտը, ապա մենք սահմանում ենք թվաբանական ֆունկցիա f. Nn →N այնպես, որ f(n(x))=n. (y):
Որպես զանգվածային խնդիրների համար թվաբանական ֆունկցիաներ կառուցելու օրինակ՝ դիտարկենք զանգվածային խնդիրները։
1. Եթե տրված է բնական թվերի ] զանգված, ապա նրան կարելի է վերագրել 2x1, 3x2,... p(n)xn բնական թիվը, որտեղ p(n)-ը n-րդ պարզ թիվն է։ Բերենք 5 երկարությամբ զանգվածի օրինակ.
] 2x13x25x37x411x5.
Այս համարակալումը սահմանում է f թվաբանական ֆունկցիան (օրինակ՝ f(73500) = f(22315372110) = 20315272113 = 4891425):
2. Ցանկացած ռացիոնալ թիվ ունի որոշակի բնական թիվ: Խնդրի պահանջվող օբյեկտների հավաքածուի համարակալումը չնչին է.
(«այո», «ոչ») ա (1, 0): Տրված զանգվածի խնդրի համար դուք կարող եք կառուցել մեկ արգումենտի թվաբանական ֆունկցիա՝ օգտագործելով նախորդ օրինակի տեխնիկան, կամ կարող եք դիտարկել երեք արգումենտների ֆունկցիա (բնօրինակ եռակի տարրերի երեք թվեր):
3. Ծրագրի տեքստերի համարակալումը կարող է իրականացվել հետևյալ կերպ. ցանկացած ծրագիր կարող է ընկալվել որպես թիվ գրել 256-արի թվային համակարգում (եթե ծրագիրը գրանցելու համար օգտագործվել են ASCII աղյուսակի նիշերը):
Զանգվածային խնդրից թվաբանական ֆունկցիայի անցումը թույլ է տալիս նվազեցնել զանգվածային խնդրի լուծման առկայության հարցը իր փաստարկից թվաբանական ֆունկցիայի արժեքները հաշվարկելու արդյունավետ միջոցի առկայության հարցին ( փաստարկներ):
Թվերի հավաքածուների համարակալում
Ալգորիթմների տեսության մեջ լայն տարածում է գտել մի տեխնիկա, որը թույլ է տալիս մի քանի փոփոխականների ֆունկցիաների ուսումնասիրությունը նվազեցնել մեկ փոփոխականի ֆունկցիաների ուսումնասիրության։ Այն հիմնված է թվերի բազմությունների համարակալման վրա, որպեսզի թվերի բազմությունների և դրանց թվերի միջև գոյություն ունենա երկակի համապատասխանություն, և այն ֆունկցիաները, որոնք որոշում են թվերի բազմությունից նրա թիվը և թվերից բուն թվերի բազմությունը, սովորաբար ռեկուրսիվ են: Օրինակ՝ երկու անկախ փոփոխականներ (x, y) պարունակող ֆունկցիայի համար h(x, y) այս քարտեզագրումը կարող է այսպիսին լինել.
Նկար 1.
Թող զույգերը (x, y) կազմեն մասնակի դասավորված բազմություն N(2): Եթե տրված է h(x, y) = n, ապա կա հակադարձ քարտեզագրում՝ x = h -1 1 (n) և y= h -1 2 (n), այսինքն՝ h(h -1 1 (n), h -1 2 (n)) = n. Սա թույլ է տալիս հաշվարկել n թիվը ցանկացած զույգի համար (x, y) և, ընդհակառակը, օգտագործելով n թիվը՝ x-ի և y-ի արժեքները հաշվարկելու համար.
Օգտագործելով այս կանոնները, դուք կարող եք հաշվարկել եռակի համարակալումը h 2 (x, y, z) = h(h(x, y), z) = n և, ընդհակառակը, եռակի թվով - արժեքները: x, y, z. Օրինակ, եթե h 2 (x, y, z) = n, ապա z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h (h (h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ) , h -1 2 (n)). Եռյակները (x, y, z) կազմում են մասնակի դասավորված բազմություն N(3): Նմանապես, կամայական թվերի համար մենք ունենք.
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn): Եթե h n-1 (x1, x2,…, xn)=m, ապա xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (մ)), ... ................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (մ)...)), x1 = h -1 2 (...ժ (մ)...)):
Ունենալով N (1) , N (2) ,..., N (i) ,..., N(n) բազմությունների բազմությունների համարակալումը, որտեղ N (i) թվերի (i) բազմությունների բազմությունն է, հնարավոր է սահմանել կամայական բազմությունների համակցված համարակալում M = N (1) N (2) ... N (i) .. N(n) , որտեղ M N: Ցանկացած n N-ի համար մենք ունենք h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1):
Եթե h(x ,1x ,2..., x)n = m, ապա h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (մ)+1. Օգտագործելով վերը նշված բանաձևերը, կարող եք վերականգնել x1, x2,…, xn արժեքները:
Առնչվող տեղեկություններ.
Թյուրինգի մեքենայի սահմանումը, գործողությունը և մեթոդները
Թյուրինգի մեքենան հասկացվում է որպես որոշակի հիպոթետիկ (վերացական) մեքենա, որը բաղկացած է հետևյալ մասերից (նկ. 3.1.)
1) երկու ուղղություններով անսահման ժապավեն՝ բաժանված բջիջների, որոնցից յուրաքանչյուրում կարելի է գրել այբուբենի միայն մեկ նիշ, ինչպես նաև դատարկ l նիշը.
2) կառավարող սարք (աշխատանքային գլուխ), որը ցանկացած պահի կարող է լինել լրակազմի վիճակներից մեկում. Յուրաքանչյուր նահանգում գլուխը դրվում է բջջի դիմաց և կարող է կարդալ (վերանայել) կամ գրել այբուբենից տառ դրան: Ա.
Բրինձ. 3.1. Թյուրինգ մեքենա
ՄՏ-ի աշխատանքը բաղկացած է տարրական քայլերի (ցիկլերի) հաջորդականությունից: Յուրաքանչյուր քայլ կատարում է հետևյալ գործողությունները.
1. աշխատանքային գլուխը կարդում է (վերանայում) խորհրդանիշը.
2. կախված իր վիճակից և մոնիտորինգվող խորհրդանիշից, գլուխը արտադրում է սիմվոլ և գրում այն վերահսկվող բջիջում (հնարավոր է =) ;
3. գլուխը մեկ բջիջ է տեղափոխում աջ (R), ձախ (L)կամ մնում է տեղում (E);
4. Գլուխը գնում է մեկ այլ ներքին վիճակի. (հնարավոր է =).
Վիճակը կոչվում է նախնական և վերջնական: Վերջնական վիճակի մեջ մտնելիս մեքենան կանգ է առնում։
ՄՏ-ի ամբողջական վիճակը կոչվում է կոնֆիգուրացիա . Սա տառերի բաշխումն է ժապավենի բջիջների միջև, աշխատանքային գլխի վիճակը և վերահսկվող բջիջը: Կազմաձևումը տակտի մեջ տգրված է ձևով՝ , որտեղ է գտնվում դիտարկվող բջիջի ձախ կողմում գտնվող ենթաբառը, արդյո՞ք մոնիտորինգի ենթարկվող բջջի տառը, աջ կողմում գտնվող ենթաբառն է:
Սկզբնական կոնֆիգուրացիան և վերջնական կոնֆիգուրացիան կոչվում են ստանդարտ:
MT-ի աշխատանքը նկարագրելու 3 եղանակ կա.
Ձևի հրամանատարական համակարգ
Ֆունկցիոնալ սեղան;
Անցումների գրաֆիկ (դիագրամ):
Դիտարկենք դրանք օրինակներով։
Օրինակ 1.Կառուցեք MT, որն իրականացնում է այբուբենի երկու բառերի շաղկապումը: Ժապավենի վրա բառերն առանձնացված են *-ով: Սկզբնական կոնֆիգուրացիան ստանդարտ է:
MT հրամանի համակարգը նման է.
Պետության մեջ գլուխը շարժվում է դեպի աջ, մինչև դատարկ նշանը:
Ամենաաջ կերպարը ջնջվում է:
Աստղանիշը ջնջվում է, եթե առաջին բառը դատարկ է:
Ճիշտ բառը մեկ դիրքով նիշ առ նիշ տեղափոխվում է ձախ:
Անցում ստանդարտ վերջնական կազմաձևին:
Ֆունկցիոնալ աղյուսակ
| ա | բ | * | լ | |
| - | ||||
| - | ||||
| - | ||||
| - |
Աղյուսակում գծիկները նշանակում են, որ l նշանը հնարավոր չէ գտնել վիճակներում:
|
|
|||
Ստանդարտ վերջնական կոնֆիգուրացիա:
ՄՏ-ի վրա բառարանի ֆունկցիայի հաշվարկը մենք կհասկանանք հետևյալ կերպ. Թող սկզբնական կոնֆիգուրացիայով ժապավենի վրա գրվի a բառը: Եթե արժեքը որոշված է, ապա վերջավոր թվով քայլեր (ցիկլեր) մեքենան պետք է գնա վերջնական կոնֆիգուրացիայի, որում բառը գրված է ժապավենի վրա: Հակառակ դեպքում ՏՏ-ն պետք է անժամկետ աշխատի։
Օգտագործելով MT, դուք կարող եք նկարագրել թվաբանական գործողությունների կատարումը թվերի վրա: Այս դեպքում թվերը ներկայացվում են ժապավենի վրա որպես բառեր այբուբենի, որը բաղկացած է որոշ թվային համակարգի թվերից և առանձնացված հատուկ նշանով, որը ներառված չէ այս այբուբենի մեջ, օրինակ՝ *: Ամենատարածված օգտագործվող համակարգը միանվագ է, որը բաղկացած է մեկ խորհրդանիշից –1: Ժապավենի վրա X թիվը գրված է այբուբենի բառով (կամ կրճատված): A=(1).
Թվային ֆունկցիան պատշաճ կերպով հաշվարկելի է (կամ պարզապես Թյուրինգի հաշվարկելի), եթե կա MT, որը կարգավորում է կոնֆիգուրացիան, երբ = y, կամ աշխատում է անորոշ ժամանակով, երբ սահմանված չէ:
Օրինակ 2.Ունի կոդում երկու թվերի գումարման գործողություն:
Սկզբնական կոնֆիգուրացիա.
Վերջնական կոնֆիգուրացիա, այսինքն. գումարումն իրականում հանգում է թվի նշանակմանը բհամարին ա. Դա անելու համար առաջին 1-ը ջնջվում է, իսկ *-ը փոխարինվում է 1-ով:
Մենք տալիս ենք MT-ի նկարագրությունը ֆունկցիոնալ աղյուսակի տեսքով.
| * | լ | ||
| - | |||
| - | |||
| - |
ՄՏ-ի նկարագրության վերը նշված մեթոդները գործնականում կարող են օգտագործվել միայն պարզ ալգորիթմների համար, քանի որ բարդերի համար նկարագրությունը դառնում է չափազանց ծանր: Նմանապես, ռեկուրսիվ ֆունկցիաների նկարագրությունը՝ օգտագործելով միայն սուպերպոզիցիայի, պարզունակ ռեկուրսիայի և մինիմիզացիայի ամենապարզ գործառույթներն ու օպերատորները, չափազանց դժվար կլիներ: Հետևաբար, ֆունկցիայի պարզունակ կամ մասնակի ռեկուրսիվությունն ապացուցվում է այլ ֆունկցիաների միջոցով, որոնց պարզունակ կամ մասնակի ռեկուրսիվությունն արդեն ապացուցված է։
Նմանապես, բարդ ալգորիթմների համար Turing մեքենաները կարող են կառուցվել գոյություն ունեցող ՄՏ-ների միջոցով: Այս կոնստրուկցիան կոչվում է MT կազմ:
Եկեք նկարագրենք MT կազմի 4 հիմնական մեթոդներ.
Հաջորդական կազմը (գերդիրքավորում);
Զուգահեռ կազմը;
Ճյուղավորում
Հաջորդական կազմը մեքենաներ և հաշվողական բառարանի գործառույթներ և այբուբենով Ա, կոչվում է մեքենա Տ, որը հաշվարկում է ֆունկցիան։ Հերթական կազմը պատկերված է հետևյալ կերպ.
և նշանակված է.
Հերթական կազմը սովորաբար օգտագործվում է ալգորիթմների գծային հատվածները նկարագրելու համար։
Մեքենա կառուցելու հնարավորության մասին թեորեմի ապացույց Տ, որը երկու կամայական մեքենաների հաջորդական կազմն է և իրականացվում է վերջնական վիճակը սկզբնական վիճակի հետ նույնացնելով։
Օրինակ 3.Կառուցեք 2*X բազմապատկման ալգորիթմ միատարր կոդով` օգտագործելով պատճենահանող սարք, որը a բառը թարգմանում է a*a բառի և գումարման մեքենայի: Պահանջվող MT-ն ունի հետևյալ տեսքը.
| | | |
|||||||||||||
| | |
||||||||||||||
Զուգահեռ կազմը մեքենաներ և հաշվողական բառարանի գործառույթներ և այբուբեններ ԱԵվ INհամապատասխանաբար, մեքենան կոչվում է Տ, որը գնահատում է բառարանի ֆունկցիան։ Այստեղ նշանն օգտագործվում է ՄՏ-ի զուգահեռ կազմով բառեր առանձնացնելու համար։
| |
և նշանակված է՝ .
Փաստորեն, երկու ՄՏ-ների զուգահեռ շարադրությունը որպես մուտք է ստանում տարբեր այբուբեններով 2 բառից բաղկացած բառ և դուրս է բերում 2 բառից բաղկացած բառ, այսինքն. ներկայացնում է երկու միաժամանակ և ինքնուրույն աշխատող մեքենաներ:
Զուգահեռ կոմպոզիցիա իրականացնելու համար օգտագործվում է երկհարկանի գոտի ունեցող մեքենա։ Սրա անհրաժեշտությունը պայմանավորված է նրանով, որ հաշվարկը և ժամանակը հաջորդաբար տեղի են ունենում, և, հաշվելով, օրինակ, նախ, կարող է ավելի շատ տարածք պահանջել, քան a-ն և փչացնել b բառը: Երկհարկանի ժապավենի մեքենան աշխատում է այսպես. b բառը գրվում է երկրորդ հարկում և ջնջվում առաջին հարկում, հաշվարկվում է առաջին հարկում, հաշվարկվում է երկրորդ հարկում և այնուհետև վերագրվում է առաջին հարկ, հնարավոր է, հերթափոխով: .
Իրականացնել զուգահեռ կազմը nօգտագործված մեքենաներ n–հատակի ժապավեն:
Երկհարկանի ժապավենով MT հրամանը գրված է հետևյալ կերպ՝ որտեղ են տառերը գրված համապատասխանաբար առաջին և երկրորդ հարկերում։
Օրինակ 4. Իրականացնել մեքենաների և հաշվողական ֆունկցիաների զուգահեռ կազմը երկուական թվային համակարգում և ա+բունարային համակարգում։
Մուտքային բառն ունի ձև՝ .
Եկեք նկարագրենք MT-ի աշխատանքը հրամանների համակարգով.
Անցնել աջ բառի բ
Բ բառը վերաշարադրելով երկրորդ հարկ
Տեղափոխել ձախ բառը a
X թվին ավելացնելով 1.
Անցնել աջ բառի բ.
մարդահամար բ 1-ին հարկ՝ թվերի միաժամանակյա գումարումով աԵվ բ.T համապատասխանաբար. Հրամանների համակարգին ավելացված գանգուր փակագծերի հրամաններ
Ամբողջ MT-ի վերջնական վիճակը.
Հարկ է նշել, որ բոլոր դեպքերում, ալգորիթմի սկզբում, անհրաժեշտ է մուտքագրել աղբյուրի տվյալների ստուգում հատուկ արժեքների համար (առավել հաճախ՝ 0); այս պահանջին չհամապատասխանելը կարող է հանգեցնել հանգույցի:
MT կազմը կարող է օգտագործվել բարդ ալգորիթմներ կառուցելու համար: Հարց է առաջանում՝ կարո՞ղ է որևէ ալգորիթմ ներդրվել որպես MT կոմպոզիցիա։ Այս հարցի պատասխանը տալիս է Թյուրինգի թեզը Չերչի թեզի անալոգը. յուրաքանչյուր ալգորիթմ կարող է իրականացվել Թյուրինգի մեքենաների միջոցով և հակառակը, Թյուրինգ մեքենայի կողմից իրականացվող յուրաքանչյուր գործընթաց ալգորիթմ է:
Թյուրինգի թեզը թեորեմ չէ, դա անհնար է ապացուցել, քանի որ այն պարունակում է ոչ պաշտոնական հայեցակարգ» ալգորիթմ« Այնուամենայնիվ, երկար տարիների մաթեմատիկական պրակտիկան այս թեզի հավաստի հաստատումն է. 50 տարի շարունակ ինտուիտիվ իմաստով ոչ մի ալգորիթմ չի գտնվել, որը հնարավոր չէր իրականացնել Turing մեքենաների միջոցով:
Աշխատանքի նպատակը.ձեռք բերել գործնական հմտություններ ալգորիթմներ գրելու մեջ՝ օգտագործելով Թյուրինգի մեքենաների կազմը:
Տեսական տեղեկատվություն
ՄՏ-ի նկարագրության վերը նշված մեթոդները գործնականում կարող են օգտագործվել միայն պարզ ալգորիթմների համար, հակառակ դեպքում նկարագրությունը դառնում է չափազանց ծանր: Բարդ ալգորիթմների համար Turing մեքենաները կարող են կառուցվել արդեն գոյություն ունեցող տարրական ՄՏ-ների միջոցով, և այս կառուցումը կոչվում է. կազմը MT.
Եկեք նկարագրենք MT կազմի 4 հիմնական մեթոդներ.
Հաջորդական կազմը (գերդիրքավորում);
Զուգահեռ կազմը;
Ճյուղավորում
1. Թյուրինգի մեքենաների հաջորդական կազմը
Հաջորդական կազմըկամ սուպերպոզիցիաԹյուրինգ մեքենաներ և 
Եվ 
այբուբենով Ա,դա կոչվում է մեքենա Մ, ֆունկցիայի հաշվում 
.
Հերթական կազմը պատկերված է հետևյալ կերպ.
և նշանակված է 
կամ 
.
2. Թյուրինգի մեքենաների զուգահեռ կազմը
Զուգահեռ կազմը
մեքենաներ 
Եվ 
, բառարանի ֆունկցիաների հաշվում 
Եվ 
այբուբեններով ԱԵվ IN,համապատասխանաբար, մեքենան կոչվում է Մ, որը գնահատում է բառարանի ֆունկցիան։ Ահա նշանը 
օգտագործվում է ՄՏ-ի զուգահեռ կազմով բառեր առանձնացնելու համար:
Զուգահեռ կազմը ՄՏ 
Եվ 
պատկերված է հետևյալ կերպ.
և նշանակված է. 
.
Փաստորեն, երկու ՄՏ-ների զուգահեռ կազմը որպես մուտք է ստանում 2 բառից բաղկացած տարբեր այբուբեններով բառ, և դուրս է բերում նաև 2 բառից բաղկացած բառ, այսինքն. ներկայացնում է երկու միաժամանակ և ինքնուրույն աշխատող մեքենաներ: Զուգահեռ կոմպոզիցիա իրականացնելու համար օգտագործվում է երկհարկանի գոտի ունեցող մեքենա։
Երկհարկանի գոտի մեքենան աշխատում է հետևյալ կերպ.
1) բառ 
վերաշարադրված ժապավենի երկրորդ հարկում և ջնջված առաջինում,
2) հաշվարկված 
առաջին հարկում,
3) հաշվարկված 
Երկրորդ հարկում
4)
վերագրված է առաջին հարկ, հնարավոր է հերթափոխով։
Երկհարկանի ժապավենով MT հրամանը գրված է հետևյալ կերպ.
,
Որտեղ 
– համապատասխանաբար առաջին և երկրորդ հարկերում գրված նամակներ. Նշենք բառերի երկարությունը 
, համապատասխանաբար, 
.
Եկեք ցույց տանք Թյուրինգի մեքենայի աշխատանքը երկհարկանի ժապավենով: Ընդհանուր առմամբ, բառերի երկարությունը 
Եվ 
չեն համընկնում միմյանց հետ, սակայն պատկերի պարզության համար ենթադրում ենք, որ դրանք հավասար են: Այնուհետև 1)-4) կետերի կատարումը ՄՏ-ի վրա երկհարկանի ժապավենով կատարվում է հետևյալ կերպ.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Իրականացնել զուգահեռ կազմը n Օգտագործվում են Turing մեքենաներ n– հատակի ժապավեն:
3. Ճյուղավորում կամ պայմանական անցում Թյուրինգի մեքենաների կոմպոզիցիաներում
Եթե տրվեն Թյուրինգի մեքենաներ 
Եվ 
, բառարանի ֆունկցիաների հաշվում 
Եվ 
, և մեքենան 
, որը գնահատում է որոշ նախադրյալ Պ(
)
վերականգնմամբ (այսինքն՝ առանց բառը ջնջելու
),
ապա Թյուրինգի մեքենա կարող է կառուցվել ճյուղավորում իրականացնելու համար 
, ֆունկցիայի հաշվարկում.
Թյուրինգի մեքենաների ճյուղավորումը կոմպոզիցիայի դիագրամներում պատկերված է հետևյալ կերպ.
և նշանակված է 
, Այստեղ 
- մեքենայի աշխատանքի արդյունքը 
, վերցնելով «1» արժեքները, եթե պրեդիկատը Պ(
)=
”ճիշտ”
և «0», եթե պրեդիկատը Պ(
)=
“կեղծ”
,
– Turing մեքենա, որն իրականացնում է մուտքագրված բառի պատճենումը 
.
4 . Ցիկլը Թյուրինգի մեքենաների բաղադրության մեջ
ՑիկլԿազմում MT-ն իրականացվում է նույն սկզբունքներով, ինչ ճյուղավորումը:
«Ցտեսություն P(
)=
”ճիշտ”
, կատարել 
»,
Որտեղ
- բառը ժապավենի վրա առաջին կատարումից առաջ 
և հաջորդ մահապատժից հետո .
Ցիկլը պատկերելու համար մենք ներկայացնում ենք որոշակի նշում, թող.
– Թյուրինգի մեքենա, որն իրականացնում է պրեդիկատի հաշվարկը P(
)
;
–MT, որն իրականացնում է մուտքագրված բառի պատճենումը 
;
–MT, իրականացվում է օղակով և իրականացվում 
;
–MT, կատարվում է հանգույցից դուրս գալու և իրականացնելիս 
.
Այնուհետև Թյուրինգի մեքենաների ցիկլային կազմը կամ ցիկլը կարելի է պատկերել հետևյալ կերպ.
Ծրագրավորում Turing Machine կոմպոզիցիաներով.
1) բարդ ալգորիթմների բլոկ-սխեմաների կառուցում այնպիսի մանրամասնության մակարդակի, որ դրանց բլոկները համապատասխանեն տարրական ՄՏ-ներին.
2) տարրական ՄՏ-ների կառուցում, որոնք իրականացնում են պարզ բլոկներ.
3) տարրական ՄՏ-ների միավորումը ՄՏ կազմի մեջ.
Օրինակ.Կառուցեք MT կոմպոզիցիա, որն իրականացնում է 
.
– Թյուրինգ մեքենա, որն իրականացնում է մուտքագրված բառի պատճենումը.
–MT, որն իրականացնում է հաստատուն զրո սահմանելու գործառույթը.
–MT, հաշվողական պրեդիկատ՝ վերականգնմամբ 
;
– MT, որն իրականացնում է ընտրության գործառույթը 
- այդ փաստարկը 
փաստարկներ;
–MT՝ իրականացնելով արգումենտի կրճատման ֆունկցիան 
1-ով unary կոդը (ջնջում է ձախ նիշը);
– MT, որն իրականացնում է երկու թվերի գումարում ունարային կոդով:
Հարկ է նշել, որ ամեն դեպքում ալգորիթմի կատարման սկզբում անհրաժեշտ է ստուգել մուտքային տվյալները ճշտության համար (օրինակ՝ արգումենտի հավասարությունը 0-ին բաժանման ժամանակ)։
Նկար 1.6
Նկար 1.6-ում օգտագործվում են հետևյալ նշումները.
T 1, T 2 - Turing մեքենաներ;
ST 1, ST 2 - համապատասխանաբար T 1 և T 2 մեքենաների հրամանատարական համակարգեր;
x - նախնական տեղեկատվություն T 1 մեքենայի համար;
T 1 (x) - մեքենայի շահագործման արդյունքը T 1;
T 2 (T 1 (x)) - T 2 մեքենայի աշխատանքի արդյունքը:
Որպես օրինակ, դիտարկենք երկու մեքենաների կազմը, որոնցից առաջինը կատարում է պատճենման գործողություն, իսկ երկրորդը կատարում է ունարային կոդով թվեր ավելացնելու գործողությունը։ Մեքենաների համակցության դիագրամը և ստացված արդյունքներով ժապավենի օրինակը ներկայացված են Նկար 1.7-ում:
Նկար 1.7
Նկար 1.7-ում ներկայացված կոմպոզիցիան թույլ է տալիս կատարել թվի կրկնապատկման գործողություն՝ օգտագործելով արդեն հայտնի պատճենող և ավելացման մեքենաներ: Այսպիսով, Թյուրինգի մեքենաների համար ալգորիթմներ կազմելով՝ որոշակի գործողություններ լուծելու համար (օրինակ՝ թվաբանական գործողություններ), այնուհետև Թյուրինգի մեքենաների կոմպոզիցիաները կարող են կազմվել ավելի բարդ խնդիրներ լուծելու համար։ Այս դեպքում ընդհանուր ալգորիթմի մշակումը հանգում է նրան, որ այն կազմվում է այն գործողություններից, որոնց համար արդեն հայտնի են Թյուրինգ մեքենայի վրա կատարման ալգորիթմները: Այս մոտեցումը նման է ծրագրավորման գործընթացների և գործառույթների օգտագործմանը:
Սակայն մեքենայի կոմպոզիցիայի օգտագործումը ենթադրում է, որ հայտնի են տարրական գործողություններ կատարելու ալգորիթմները, որոնցից կազմված է ընդհանուր ալգորիթմը։ Հետևաբար, կամայական խնդիրներ լուծելիս այս մոտեցումը չի բացառում նոր ալգորիթմներ կազմելու և, համապատասխանաբար, տարբեր կառավարման միավորներով Turing մեքենաների մշակման անհրաժեշտությունը: Հնարավոր է իրականացնել ցանկացած ալգորիթմ՝ առանց կառավարման միավորի կառուցվածքը փոխելու՝ օգտագործելով ունիվերսալ Turing մեքենա:
1.2.2.Ունիվերսալ Թյուրինգ մեքենա
Եթե տրված է որոշ Turing մեքենա (այսինքն՝ մուտքային, ելքային ազդանշանների և վիճակների այբուբենները, գլխի սկզբնական դիրքը և մեքենայի սկզբնական վիճակը հայտնի են, ինչպես նաև մեքենայի աշխատանքի աղյուսակը և ժապավենը նախնական տեղեկություններով. ), ապա բոլոր տեղեկատվական փոխակերպումները կարելի է ձեռքով կատարել քայլ առ քայլ, ինչի համար նախատեսված է այս մեքենան։ Փաստորեն, այս դեպքում կատարվում է Թյուրինգ մեքենայի մոդելավորում։
Թյուրինգի մեքենայի մոդելավորման ժամանակ կատարվող գործողությունները վերլուծելիս կարելի է պարզել, որ մոդելավորումը հանգում է յուրաքանչյուր քայլին հետևյալ գործողությունների կրկնմանը.
Ä Կարդալ նիշ ժապավենի բջիջից, որի վրա գտնվում է գլուխը:
Ä Փնտրեք հրաման մեքենայի շահագործման աղյուսակում: Որոնումն իրականացվում է մեքենայի ընթացիկ վիճակի և ընթերցված նշանի արժեքի հիման վրա:
Ä Ընտրել նշանը հրամանից, որը պետք է գրվի ժապավենի վրա և ձայնագրել այն:
Ä Հրամանից ընտրեք գլխի շարժման նշանը և տեղափոխեք այն:
Ä Հրամանից մեքենայի նոր վիճակ ընտրելը և ներկայիս վիճակը նորի փոխելը: Դրան հաջորդում է անցնել հաջորդ քայլին և կրկնել այս քայլերը:
|
|
 |
|||||
 |
|||||
Նկար 1.8
Այս տարրական գործողությունների բնույթն այնպիսին է, որ բոլորը կարող են իրականացվել Թյուրինգի այլ մեքենայի միջոցով, որը նմանակում է սկզբնական մեքենայի աշխատանքը: Մոդելավորման էությունը բացատրված է Նկար 1.8-ում:
Եթե T մեքենան ունի ST հրամանային համակարգ և մշակում է ժապավեն X տեղեկատվությամբ, ապա դրա աշխատանքը կարող է մոդելավորվել մեկ այլ U մեքենայի կողմից, որն ունի իր SU հրամանատարական համակարգը։ Մեքենայի U-ի մուտքագրումը մոդելավորելու համար անհրաժեշտ է ներկայացնել ոչ միայն ժապավեն X տեղեկատվությամբ , այլեւ հրամանատարական համակարգը (աշխատանքային սեղան) ST. Այս հրամանի համակարգը կարող է ձայնագրվել նույն ժապավենի վրա, ինչ սկզբնական տեղեկատվությունը:
 |
Նկար 1.9
Մոդելավորող մեքենայի կարևոր առանձնահատկությունն այն է, որ նրա հրամանատարական համակարգը SU (և, համապատասխանաբար, կառավարման ստորաբաժանման կառուցվածքը) կախված չէ մոդելավորված մեքենայի գործող ալգորիթմից: Թյուրինգ մեքենա, որը կարող է նմանակել ցանկացած այլ Թյուրինգի աշխատանքը: մեքենան կոչվում է ունիվերսալ: Ունիվերսալ Turing մեքենայի (UMT) կառուցվածքի տարբերակը ներկայացված է Նկար 1.9-ում:
UMT ժապավենը բաժանված է երեք գոտիների՝ տվյալների գոտի, ռեժիմի գոտի և հրամանի գոտի:
Տվյալների գոտին պարունակում է նախնական տեղեկատվություն, որը պետք է մշակվի մոդելավորված Turing մեքենայի կողմից: Նույն գոտում գրանցվում են UMT գործողության արդյունքները։
Ռեժիմի գոտին գրանցում է ընթացիկ վիճակը Q t և ընթացիկ մուտքագրման նշանը X t, որը կարդացվում է տվյալների գոտու բջիջից տվյալ ցիկլում:
Հրամանի գոտին պարունակում է մոդելավորված մեքենայի հրամանատարական համակարգը: Հրամանները կազմակերպվում են խմբերի: Առաջին խումբը ներառում է Q 0 նշանով սկսվող հրամաններ, երկրորդը՝ Q 1 նշանով և այլն։ Յուրաքանչյուր խմբի ներսում հրամանները դասավորված են ըստ X t նշանի արժեքի: Այսպիսով, ժապավենի հրամանները տեղակայված են այնպես, ինչպես դրանք տեղակայված են մոդելավորված մեքենայի շահագործման աղյուսակում:
Ժապավենից տեղեկատվության ընթերցումը և ժապավենին գրելը կատարվում է երեք գլխի միջոցով՝ G d - տվյալների գլուխ, G r - ռեժիմի գլուխ, G k - հրամանի գլուխ: Յուրաքանչյուր գլուխ կարող է շարժվել գոտու իր գոտիով:
Մինչ UMT-ը կսկսի գործել, համապատասխան տեղեկատվությունը պետք է գրանցվի ժապավենի յուրաքանչյուր գոտում: Գլուխները պետք է տեղադրվեն յուրաքանչյուր գոտու ձախ նշանի վերևում:
UMT-ի աշխատանքը տեղի է ունենում ցիկլերով, յուրաքանչյուր ցիկլում մոդելավորվում է մոդելավորված մեքենայի մեկ հրամանի կատարումը: UMT-ի շահագործման գրաֆիկը ներկայացված է Նկար 1.10-ում:
 |
Նկար 1.10
Նկար 1.10-ում օգտագործվում են հետևյալ նշումները.
Q G-ից P (G-ից L, G r P, G r L, G d P, G d L) - շարժվում է գլուխներից մեկը
աջ կամ ձախ;
Q (G k), (G d), (G r) - տեղեկատվություն, որը կարդացել է ղեկավարներից մեկը;
Q (G k) à (G r) - հրամանի ղեկավարի կողմից տվյալների ընթերցում և այս տվյալները գրելը
փոխանցվում է ռեժիմի գլխի միջոցով ժապավենի ռեժիմի գոտի;
Q a-ն օժանդակ փոփոխական է, որն ընդունում է 1 արժեքը, e-
Համընկնում են արդյոք Գկ և Գր ղեկավարների կարդացած նիշերը.
Q in-ը օժանդակ փոփոխական է, որն ընդունում է 1 արժեքը, e-
արդյոք ընթացիկ (Q t) և վերջնական (Q z) նշանները
Q p - ազդանշան, որը վերցնում է 1 արժեքը, եթե հրամանի ղեկավարը, երբ
ձախ շարժվելը դուրս եկավ հրամանատարական գոտու սահմաններից.
UMT-ի շահագործման յուրաքանչյուր ցիկլում կատարվում են հետևյալ քայլերը.
u որոնել հրամանի գոտի;
u որոնել թիմ գոտում;
u սիմուլյացիա հրամանի կատարման.
Հրամանի գոտու որոնումը սկսվում է ռեժիմի գոտուց ներկա Q t վիճակի համեմատելով հրամանի գոտու առաջին հրամանի սկզբում գրանցված Q i վիճակի հետ։ Եթե այս վիճակները հավասար չեն, ապա հրամանի գլուխը տեղափոխվում է հաջորդ հրամանի սկիզբ, որի համար գլխի հինգ քայլերը կատարվում են դեպի աջ (վիճակներ U 0 - U 4): Եթե Q t և Q i նշանները համընկնում են, հրամանի գլուխը գտնվում է ցանկալի գոտու առաջին հրամանի սկզբում: Հաջորդը, որոնումը սկսվում է ռեժիմի գոտու Q t և X t խորհրդանիշներին համապատասխանող հրամանի համար: Դա անելու համար ռեժիմի գլուխը տեղադրվում է ռեժիմի գոտու X t նշանի վերևում, իսկ հրամանի գլուխը տեղադրված է ընթացիկ հրամանի X i նշանի վերևում:
Գոտում հրամանի որոնումը նման է հրամանի գոտու որոնմանը: Այս դեպքում հրամանի գլուխը շարժվում է դեպի աջ հինգ քայլ (U 5 - U 9 վիճակներ), մինչև X t և X i նիշերը համեմատվեն:
Հրամանի կատարումը (պետություններ U 10 - U 17) սկսվում է հրամանի գլուխը մեկ քայլ աջ տեղափոխելով, որից հետո հայտնաբերված հրամանից կարդացված Y նշանը գրվում է տվյալների գոտի՝ օգտագործելով տվյալների գլխի փոխարեն: նախկինում կարդացված խորհրդանիշ X t. Հրամանի գլխի հաջորդ քայլից հետո դեպի աջ, տվյալների գլխի շարժման նշանը (Y d) կարդացվում է գտնված հրամանից և տվյալների գլուխը տեղափոխվում է այս նշանի համաձայն (R, L): Նրա տակ գտնվում է հաջորդ մշակված նշանը (X t +1), որը, օգտագործելով ռեժիմի գլուխը, գրվում է ռեժիմի գոտում՝ հաջորդ ցիկլը պատրաստելու համար։ Հաջորդը, հրամանների և ռեժիմի գլուխները տեղադրվում են այնպես, որ հաջորդ վիճակը Q t +1 (վիճակներ
U 14, U 15): U 16 նահանգում ստուգվում է լուծույթն ավարտելու պայմանը։ Եթե հաջորդ վիճակի խորհրդանիշը չի համընկնում մոդելավորված մեքենայի վերջնական վիճակի խորհրդանիշի հետ (Q z), ապա խնդրի լուծումը ավարտված չէ, և U 17 վիճակում հրամանի գլուխը տեղափոխվում է իր սկզբնական դիրքը ( մինչև առաջին գոտու առաջին հրամանի սկիզբը): Այս դեպքում UMT-ը պատրաստ է կատարել հաջորդ ցիկլը, այսինքն. հաջորդ հրամանի կատարումը մոդելավորելու համար:
Երբ Q t և Q z նշանները համընկնում են, խնդրի լուծումն ավարտվում է, և UMT-ն անցնում է վերջնական վիճակի U z:
UMT-ի շահագործման գործընթացը վերլուծելիս կարելի է կարևոր եզրակացություն անել, որ UMT-ի շահագործման ալգորիթմը կախված չէ նրանից, թե ինչ կոնկրետ խնդիր է լուծում մոդելավորված Turing մեքենան: Հետևաբար, UMT կառավարման միավորի կառուցվածքը չի փոխվում տարբեր մեքենաների մոդելավորման ժամանակ, այսինքն. կախված չէ լուծվող խնդիրներից. Այդ իսկ պատճառով UMT-ն իսկապես ունիվերսալ մեքենա է, որի օգնությամբ դուք կարող եք կատարել ցանկացած ալգորիթմ՝ առանց դրա կառուցվածքը փոխելու։
Քանի որ հաջորդ UMT հրամանի ընտրության և դրա կատարման գործընթացը կապված է ժապավենի բջիջների հաջորդական թվարկման հետ, UMT-ում խնդիրների լուծումը չափազանց շատ ժամանակ է պահանջում: Հետևաբար, Թյուրինգի մեքենան, ներառյալ ունիվերսալը, երբեք չի կառուցվել, բայց դրանում դժվար չէ տեսնել ժամանակակից համակարգիչների անալոգը: Այսպիսով, UMT հրամանի գոտում հրամանի համակարգը նման է մեքենայական ծրագրին, որտեղ Q t և X t զույգ խորհրդանիշները խաղում են մեքենայի հրամանի հասցեի դերը:
Այնուամենայնիվ, Թյուրինգի մեքենան բավականին հարմար միջոց է ալգորիթմների նկարագրության համար և լայնորեն կիրառվում է ալգորիթմների տեսության մեջ։
Վերահսկիչ հարցեր
ü1.Ինչպիսի՞ն է Թյուրինգի մեքենաների բաղադրությունը:
ü2.Ինչի՞ համար են օգտագործվում Թյուրինգի մեքենաների կազմը:
ü3. Կարո՞ղ է Թյուրինգի մեկ մեքենան մոդելավորել մեկ այլ մեքենայի աշխատանքը:
Թյուրինգ.
ü4.Ի՞նչ գործողություններ են կատարվում այս դեպքում:
ü5.Բացատրե՛ք ունիվերսալ Թյուրինգ մեքենայի կառուցվածքը:
ü6.Ի՞նչ տեղեկատվություն է գրանցվում UMT ժապավենի տարածքներում:
ü7.Ի՞նչ է Թյուրինգ մեքենայի հրամանատարական համակարգը:
ü8.Ի՞նչ քայլեր է պարունակում UMT աշխատանքային ցիկլը:
ü9.Բացատրեք «հրամանատարության գոտու որոնում» քայլի բովանդակությունը:
ü10.Բացատրեք «հրամանի կատարում» քայլի բովանդակությունը:
ü11.Ի՞նչ հատկանիշներ է օգտագործում տեղեկատվության մշակման գործընթացը
Դիագրամը նման է գրաֆիկի.
Մեքենայի աղյուսակի արժեքը
Աղյուսակ 1
Որոշ գործողություններ Turing մեքենաների վրա
Թյուրինգի մեքենայի աշխատանքը լիովին որոշվում է մուտքային տվյալների և հրամանների համակարգով: Այնուամենայնիվ, հասկանալու համար, թե ինչպես է կոնկրետ մեքենան լուծում խնդիրը, որպես կանոն, անհրաժեշտ են բովանդակալից բացատրություններ, որոնք տրվել են մեքենայի համար: 
. Այս բացատրությունները հաճախ կարելի է ավելի ֆորմալ և ճշգրիտ դարձնել՝ օգտագործելով սխեմաները և Թյուրինգի մեքենայի որոշ գործողություններ: Հիշեցնենք, որ ֆունկցիաների կազմը 
Եվ 
կոչվում է ֆունկցիա 
, որը ստացվում է օգտագործելիս 
հաշվարկի արդյունքին 
. Որպեսզի 
որոշվել է սրանով 
, դրա համար անհրաժեշտ է և բավարար 
որոշվել է 
, Ա 
որոշվել է 
.
Թեորեմ 1. Եթե 
Եվ 
Թյուրինգի հաշվարկելի են, ապա դրանց կազմը 
Թյուրինգը նույնպես հաշվարկելի է:
Թող 
- մեքենա, որը հաշվարկում է 
, Ա 
- մեքենա, որը հաշվարկում է 
, և համապատասխանաբար նրանց պետությունների ամբողջությունը 
Եվ 
.
Եկեք կառուցենք մեքենայի անցման դիագրամ 
դիագրամներից 
Եվ 
մենք նույնացնում ենք սկզբնական գագաթը 
մեքենաների դիագրամներ 
տերմինալ գագաթով 
մեքենաների դիագրամներ 
(հրամանատար համակարգերի համար դա համարժեք է այն փաստին, որ հրամանատարական համակարգը 
հանձնարարված հրամանատարական համակարգին 
և դրա համար 
թիմերում 
փոխարինել 
) Մենք ստանում ենք դիագրամ ( 
) պետությունները: Սկզբնական վիճակ 
մենք կհայտարարենք 
և վերջնական 
. Նշման պարզության համար մենք ենթադրում ենք 
Եվ 
մեկ փոփոխականի թվային ֆունկցիաներ.
Թող 
որոշված. Հետո 
Եվ
. Ավտոմեքենա 
կանցնի կոնֆիգուրացիաների նույն հաջորդականությամբ այն տարբերությամբ, որ փոխարենը 
այն տեղի կունենա ք 
. Այս կոնֆիգուրացիան մեքենայի ստանդարտ նախնական կոնֆիգուրացիան է 
, Ահա թե ինչու 
. Բայց քանի որ բոլոր թիմերը 
մեջ պարունակվող 
, Դա
եւ, հետեւաբար 
. Եթե 
սահմանված չէ, ուրեմն 
կամ 
չի կանգնում և հետևաբար մեքենան 
կանգ չի առնելու. Այսպիսով, մեքենան 
հաշվարկում է 
.
Մեքենան այսպիսով կառուցված 
մենք այն կանվանենք մեքենաների կոմպոզիցիա 
Եվ 
և նշանակել 
(կամ 
(
)), և նաև պատկերված է բլոկային դիագրամում.
Թյուրինգի մեքենաների կազմը
Թող 
,
,
- երեք Turing մեքենա նույն արտաքին այբուբենով 
, ներքին վիճակների այբուբեններով 
,
,
և ծրագրեր 
,
,
համապատասխանաբար.
Կազմը
մեքենաներ 
Եվ 
կանչեց մեքենաՏ
, որի ծրագիրը բազմությունների միավորումն է 
Եվ
, Որտեղ 
նշանակում է մի շարք հրամաններ, որոնք ստացվել են 
փոխարինելով բոլորը 
վրա 
.
Թյուրինգի մեքենաներից դուրս գալը
Ճյուղավորող մեքենաներ
,
,
Ըստ 
, խորհրդանշականորեն
կանչեց մեքենաՏ
, որի ծրագիրը ստացվում է հետեւյալ կերպ.-ից 
թիմերը բացառված են 
Եվ 
Համար 
, ստացված հավաքածուն կկոչվի 
; Հետո.
Ունիվերսալ Turing մեքենա
Թյուրինգ մեքենայի հրամանատարական համակարգը կարող է մեկնաբանվել և՛ որպես կոնկրետ սարքի աշխատանքի նկարագրություն, և՛ որպես ծրագիր, այսինքն. մի շարք հրահանգներ, որոնք հստակորեն հանգեցնում են արդյունքի: Օրինակները վերլուծելիս ակամա ընդունվում է երկրորդ մեկնաբանությունը, այսինքն. մենք գործում ենք որպես մեխանիզմ, որը կարող է վերարտադրել ցանկացած Թյուրինգ մեքենայի աշխատանքը: Վստահությունը, որ բոլորը դա կանեն նույն ձևով (եթե նրանք սխալներ չգործեն, ինչը, ի դեպ, ենթադրվում է նաև, երբ գործում է Թյուրինգի մեքենան), ըստ էության վստահություն է Թյուրինգի գործողությունը վերարտադրող ալգորիթմի առկայության մեջ։ մեքենա ըստ տվյալ ծրագրի, այսինքն. հրամանատարական համակարգ. Իրոք, դժվար չէ նման ալգորիթմի բանավոր նկարագրություն տալ։ Դրա հիմնական գործողությունը կրկնվում է ցիկլային և բաղկացած է հետևյալից. «Ընթացիկ կոնֆիգուրացիայի համար 
գտեք հրամանը ձախ կողմով հրամանի համակարգում 
. Եթե այս հրամանի աջ կողմը ձևի է 
, ապա փոխարինեք ընթացիկ կազմաձևով 
վրա 
(պարզվում է, որ կոնֆիգուրացիան 
); եթե աջ կողմն ունի ձևը 
, ապա փոխարինեք 
վրա 
. Ալգորիթմի բանավոր նկարագրությունը կարող է սխալ լինել և պետք է ձևակերպվի: Քանի որ Թյուրինգի մեքենան ներկայումս քննարկվում է որպես ալգորիթմի հայեցակարգի պաշտոնականացում, բնական է, որ խնդիր դրվի նկարագրված վերարտադրման ալգորիթմը կիրառող Թյուրինգի մեքենայի կառուցման խնդրին: Թյուրինգի մեքենաների համար, որոնք հաշվարկում են մեկ փոփոխականի ֆունկցիաները, այս խնդրի ձևակերպումը հետևյալն է. 
, հաշվարկելով երկու փոփոխականի ֆունկցիա և այնպիսին, որ ցանկացած մեքենայի համար 
հրամանատարական համակարգով 
, Եթե 
սահմանված (այսինքն, եթե մեքենան 
կանգ է առնում նախնական տվյալների վրա 
) Եվ 
կանգ չի առնում, եթե 
կանգ չի առնում. Մենք կկանչենք ցանկացած մեքենա, որն ունի այս հատկությունը ունիվերսալ Turing մեքենա. Դժվար չէ այս ձևակերպումն ընդհանրացնել ցանկացած թվով փոփոխականների վրա:
Առաջին խնդիրը, որն առաջանում է ունիվերսալ մեքենա կառուցելիս 
, պայմանավորված է նրանով, որ 
ինչպես Թյուրինգի ցանկացած այլ մեքենա, այն պետք է ունենա ֆիքսված այբուբեն 
և ֆիքսված վիճակներ 
. Հետեւաբար, հրամանատարական համակարգը 
և կամայական մեքենայի նախնական տվյալները 
դուք չեք կարող այն պարզապես տեղափոխել մեքենայի գոտի 
(միշտ մեքենա կա 
, այբուբեններ 
Եվ 
որը գերազանցում է իշխանությունը 
Եվ 
կամ պարզապես չեն համընկնում դրա հետ):
Լուծումն այն է, որ հերոսները լինեն 
Եվ 
կոդավորված է այբուբենի նշաններով 
. Թող 
,
. Մենք միշտ դա ենթադրելու ենք 
Եվ 
(այս երկու նշանները միշտ գտնվում են թվերի հետ աշխատող ցանկացած մեքենայի այբուբենում): Նշենք ծածկագրերը 
Եվ 
միջոցով 
Եվ 
և սահմանել դրանք որպես 
; ուրիշի համար 
; վերջնական վիճակի համար 
, Եթե 
. Կոդ 
այս մեքենայի համար 
միշտ ունի երկարություն (ձևաչափ) 
և ծածկագիրը 
- ձևաչափ 
. Խորհրդանիշներ 
,
եկեք ներս մտնենք 
, այսինքն. 
,
,
. Նիշերի կոդը 
, որը կազմված է այս բառը կազմող նիշերի ծածկագրերով, նշում ենք 
. Այսպիսով, ունիվերսալ մեքենայի խնդրի ձևակերպման վերջնական ճշգրտումը 
եռում է նրանով, որ ցանկացած մեքենայի համար 
և բառեր 
Այբուբեն 
.
Ունիվերսալ Թյուրինգ մեքենայի առկայությունը նշանակում է, որ հրահանգների համակարգը 
ցանկացած մեքենա 
կարելի է մեկնաբանել երկու եղանակով՝ կամ որպես բնօրինակ սարքի աշխատանքի նկարագրություն 
, կամ որպես ծրագիր ունիվերսալ մեքենայի համար 
. Կառավարման համակարգ նախագծող ժամանակակից ինժեների համար այս հանգամանքը բնական է։ Նա լավ գիտի, որ ցանկացած կառավարման ալգորիթմ կարող է իրականացվել կա՛մ ապարատային՝ համապատասխան շղթա կառուցելու միջոցով, կա՛մ ծրագրային ապահովման մեջ՝ գրելով ունիվերսալ կառավարման համակարգչային ծրագիր։
Այնուամենայնիվ, կարևոր է գիտակցել, որ ունիվերսալ ալգորիթմական սարքի գաղափարը բացարձակապես կապ չունի դրա իրականացման ժամանակակից տեխնիկական միջոցների մշակման հետ (էլեկտրոնիկա, պինդ վիճակի ֆիզիկա և այլն) և ոչ թե տեխնիկական, այլ մաթեմատիկական փաստ է։ , նկարագրված վերացական մաթեմատիկական տերմիններով, որոնք անկախ են տեխնիկական միջոցներից և, ավելին, հիմնված են չափազանց փոքր թվով շատ տարրական սկզբնական հասկացությունների վրա։ Հատկանշական է, որ ալգորիթմների տեսության հիմնարար աշխատանքները (մասնավորապես՝ Թյուրինգի աշխատանքը) ի հայտ են եկել 30-ական թվականներին՝ մինչ ժամանակակից համակարգիչների ստեղծումը։
Այս կրկնակի մեկնաբանությունը վերացական մակարդակով պահպանում է ինժեներական իրականացման երկու տարբերակների հիմնական դրական և բացասական կողմերը: Հատուկ մեքենա 
աշխատում է շատ ավելի արագ; բացի այդ, մեքենայի կառավարման սարքը 
բավականին ծանր (այսինքն՝ վիճակների և հրամանների թիվը մեծ է): Այնուամենայնիվ, դրա արժեքը հաստատուն է և կառուցվելուց հետո այն հարմար է կամայականորեն մեծ ալգորիթմներ իրականացնելու համար: Ընդամենը անհրաժեշտ է ժապավենի մեծ ծավալ, որը, բնականաբար, համարվում է ավելի էժան և ավելի պարզ, քան կառավարման սարքը: Բացի այդ, ալգորիթմը փոխելիս ձեզ հարկավոր չի լինի նոր սարքեր կառուցել, պարզապես անհրաժեշտ է գրել նոր ծրագիր։