1937: Alan Turing-ի ունիվերսալ մեքենան: Հայեցակարգ մեքենայի համար, որն ունակ է լուծել ցանկացած հաշվարկ

Alan Turing-ը 19-րդ դարի համակարգչային գիտությունների նշանավոր կերպարներից է, որը հայտնի է իր հեղափոխական գաղափարներով և աշխատանքներով։ Նա թողել է զգալի ժառանգություն՝ հաշվողական և գաղտնագրման մեքենաների, ինչպես նաև արհեստական բանականության ոլորտներում:

Turing-ը մեծ ներդրում է ունեցել Երկրորդ համաշխարհային պատերազմում՝ մասնակցելով Bombe ապակոդավորող սարքի ստեղծմանը, որը շատ պատմաբանների կարծիքով, կրճատեց պատերազմի տևողությունը։ Նա նախորդ դարի կեսերին քննարկեց արհեստական բանականությանը վերաբերող այնպիսի խնդիրներ, որոնք հիմա, նույնիսկ, ավելի արդիական են։ Թևակոխելով ժամանակը՝ Turing-ն առաջարկեց մի ունիվերսալ մեքենայի հայեցակարգ, որն այսօր համարվում է ժամանակակից համակարգչի նախատիպը։ Այս հոդվածը նվիրված է Turing-ի թողած ժառանգության հենց այդ կտորին՝ Turing-ի մեքենային և Turing-ի ունիվերսալ մեքենային։

Նկար 1: Alan Turing-ն իր ստեղծած Ավտոմատ հաշվողական շարժիչի հետ (ACE)

ԿՅԱՆՔԸ

Alan Turing-ը ծնվել է 1912 թվականի հունիսի 23-ին Փադիգթոնում ( Լոնդոն, Անգլիա):

Նկար 2: Alan Turing

Turing-ը մանկուց հետաքրքրված է եղել գիտությամբ. նրան քիչ էին հետաքրքրում դասական կրթական նյութերը, նա ավելի շատ տարված էր սեփական գաղափարներով և մտքերով։ Նա խնդիրներ ուներ դպրոցական մաթեմատիկայի հետ, բայց միևնույն ժամանակ Շեբորնում սովորելու տարիներին (1926 թ.-ից) շահում էր գրեթե բոլոր մաթեմատիկայի բնագավառի մրցանակները։ Դպրոցի տնօրենը նրա ծնողներին գրել էր հետևյալը․ «Եթե ​​նա պետք է մնա hանրային դպրոցում, ապա պետք է կրթվելու նպատակ ունենա։ Եթե ​​նա պատրաստվում է լինել բացառապես գիտնական, ապա հանրային դպրոցում պարզապես իր ժամանակն է վատնում»։

1931–1934 թվականներին Turing-ը սովորեց Քեմբրիջի համալսարանում, իսկ 1935-ին ընտրվեց Թագավորական քոլեջի անդամ (fellow of King’s College)։ Դա եղավ նրա դեսերտացիայի շնորհիվ, որի մեջ Turing-ը քննարկել էր Գաուսյան սխալների ֆունկցիաները և ապացուցել էր կենտրոնական սահմանի թեորեմը։ Այդ թեորեմն արդեն ապացուցվել էր Անդրեյ Մարկովի կողմից, սակայն Turing-ը դա արել էր այդ ապացույցից անտեղյակ։

Նկար 3: Alan Turing-ի դասարանի լուսանկարը Քեմբրիջի Արքայական քոլեջում, 1931 թ. (Turing-ը վերևի շարքի աջից երրորդ ուսանողն է)

1935-ին Turing-ը սկսեց մասնակցել Մաքս Նյումանի մաթեմատիկայի հիմունքների վերաբերյալ խորացված դասընթացին, որտեղ ուսումնասիրվում էր Գյոդելի անավարտության թեոեմը (Gödel’s incompleteness theorem) և Հիլբերտի որոշելիության (լուծելիության) մասին հարցը (Hilbert’s question on decidability)։ Այդ պահից ի վեր նա սկսեց աշխատել որոշելիության հարցի շուրջ, ինչն էլ դարձավ Turing-ի ունիվերսալ մեքենայի հայեցակարգի ստեղծման հիմքը։

Turing-ի ՄԵՔԵՆԱՆ

Այսպիսով, Դավիդ Հիլբերտի լուծելիության խնդրի (Entscheidungsproblem) շուրջ ուսումնասիրությունների արդյունքում, 1936 թվականին Turing-ը հրատարակեց «On Computable Numbers, with an application to the Entscheidungsproblem» (Հաշվարկելի թվերի մասին՝ լուծելիության խնդրի վրա հղումով) հոդվածը։ Հենց այստեղ նա ներկայացրեց երկու հայեցակարգեր՝ Turing-ի մեքենա և Turing-ի Ունիվերսալ մեքենա։ Այս աշխատությունում Turing-ը վերաձևակերպեց Գյոդելի անավարտության թեորեմը՝ փոխարինելով Գյոդելի ունիվերսալ թվաբանական ֆորմալ լեզուն պարզ հիպոթետիկ սարքավորումներով, որոնք էլ հենց կոչվեցին Turing-ի մեքենաներ։ Turing-ի մեքենայի գաղափարի հիման վրա Turing-ն իր հոդվածի վերջում ապացուցում է, որ Հիլբերտի լուծելիության խնդիրը (Entscheidungsproblem) չի կարող ունենալ լուծում։

Իսկ ի՞նչ է Turing-ի մեքենան։ Ինչպես արդեն նշվեց, դա հայեցակարգային սարք է, որը չնայած պարզության, տեսականորեն կարող է լուծել ցանկացած ալգորիթմի տեսքով ներկայացված խնդիր, ինչքան էլ այն բարդ լինի:

Turing-ի մեքենան կազմված է դիսկրետ բջիջների բաժանված անսահման ժապավենից և գրելու/կարդալու հնարավորություն ունեցող գլխիկից։ Ժապավենի յուրաքանչյուր բջիջ կարող է պարունակել մեկ նիշ։ Օգտագործվող նիշերի հնարավոր տարբերակները սահմանափակ քանակությամբ են՝ ամբողջ նիշերի ցանկը կոչվում է մեքենայի այբուբեն։ Մեքենան ունի նաև կարգավորումների ցանկ, որն իրենից ներկայացնում է վերջավոր թվով դեպքերի և քայլերի աղյուսակ։ Այդ ցանկի մեջ մեքենայի ցանկացած փուլի և ցանկացած հանդիպած նիշի համար նշված է քայլերի համակցություն։

Մեքենայի գրել/կարդալու գլխիկն աշխատանքի ամեն քայլին տեղակայված է լինում բջիջներից որևէ մեկի վրա։ Կարդալով բջջում գրված նիշը՝ գլխիկը կատարում է կարգավորումների ցանկում նշված այդ նիշին և աշխատանքի տվյալ փուլին համապատասխանող անհրաժեշտ քայլերը՝ գրում կամ փոփոխում է բջջի պարունակությունը, տեղաշարժվում աջ կամ ձախ, փոխում փուլը կամ դադարեցնում աշխատանքը։

Turing-ի մեքենայի մոդելը հիմնված է իրական կյանքում մարդու կատարած հաշվարկի մեխանիզմի վրա։ Եթե պարզեցնենք մեխանիզմը, ապա կարող ենք ասել, որ մարդը հաշվարկ կատարելիս որևէ օրենքների և կանոնների հիման վրա՝ գրում, ջնջում կամ ավելացնում է սիմվոլներ թղթի վրա։ Այդ գործողություններն արվում են մինչև ցանկալի արդյունքին հասնելը։ Նույնը կատարում է Turing-ի մեքենան։

Turing-Ի ՄԵՔԵՆԱՅԻ ԱՇԽԱՏԱՆՔԻ ՍԿԶԲՈՒՆՔԸ

Եկեք դիտարկենք Turing-ի մեքենայի շատ պարզ օրինակ: Մեքենան բաղկացած է անվերջ երկար ժապավենից, որն աշխատում է սովորական համակարգչի հիշողության, կամ ցանկացած այլ տվյալների պահման համակարգի պես: Ժապավենի վրայի բջիջները սկզբում դատարկ են և հնարավորություն ունեն լրացվել սիմվոլներով: Մեր դեպքում, մեքենան կարող է մշակել 0, 1 և ” “ (բացատ) սիմվոլները։ Այսպիսով մենք քննարկում ենք երեք նիշանի Turing-ի մեքենա:

Մեքենան ունի գլխիկ, որը ժամանակի ամեն պահին տեղադրված է լինում ժապավենի որևէ բջջի վերևում: Այս գլխիկի միջոցով մեքենան կարող է կատարել երեք հիմնական գործողություն՝

1. կարդալ գլխիկի տակի բջջի պարունակությունը
2. փոխել բջջի սիմվոլը՝ գրելով նորը կամ ջնջելով այն
3. տեղափոխել ժապավենն աջ կամ ձախ, որպեսզի մեքենան կարողանա կարդալ հարևան բջիջը:

Մեքենայի աշխատանքի սկզբունքը պարզաբանելու համար ստորև ներկայացնենք մի քանի պարզագույն խնդիրներ.

ԽՆԴԻՐ 1: տպել “110” նիշերի հաջորդականությունը դատարկ ժապավենի վրա

Քայլ 1: գրում ենք “1” գլխիկի տակի բջջի մեջ

Քայլ 2: տեղափոխում ենք ժապավենը մեկ բջիջ ձախ

Քայլ 3: գրում ենք 1՝ գլխիկի տակի հայտնված բջջում

Քայլ 4: Էլի տեղափոխում ենք ժապավենը մեկ բջջով ձախ

Քայլ 5: վերջապես գրում ենք 0

ԽՆԴԻՐ 2: արդեն գրված “110” -ի մեջ՝ փոխենք 1-երը 0-ների և հակառակը (կատարենք բիտերի հակադարձում)

Խնդիրը լուծելու համար Turing-ի մեքենային փոխանցենք հետևյալ կարգավորումների աղյուսակը.

փուլ

Կարդացվող նիշ

Գրելու հրահանգ

Տեղափոխվելու հրահանգ

Հաջորդ փուլ

Փուլ 0

բացատ

֊֊֊

֊֊֊

Կանգնեցնել փուլը

0

Գրել 1

Տեղափոխվել աջ

Փուլ 0

1

Գրել 0

Տեղափոխվել աջ

Փուլ 0

Մեքենան սկզբում կկարդա գլխիկի տակի նիշը, կգտնի համապատասխան հրահանգն աղյուսակից՝ կգրի նոր նիշը, հետո կտեղափոխի ժապավենն աջ կամ ձախ, ինչպես որ հրահանգված է և հետո կկրկնի կարդալու-գրելու-շարժվելու քայլերը: Քանի որ խնդիրը պարզ է, մեր մեքենան ունի միայն մեկ աշխատանքային փուլ, որի ընթացքում այն հակադարձելու է բջիջների միջի գրված նիշերը, իսկ բացատ սիմվոլին հանդիպելուն պես՝ դուրս է գալու փուլ 0-ից և դադարեցնելու է իր աշխատանքը։

Ստորև պատկերված են բոլոր քայլերը.

ԽՆԴԻՐ 3: Իրականացնել երկու թվերի գումարում

Գոյություն ունեն թվերի ներկայացման տարբեր ձևաչափեր՝ տասական, ութական, երկուական և այլն։ Turing-ի մեքենայով գումարում իրականացնելիս հիմնականում օգտագործվում է թվերի ունար ներկայացում: Այստեղ թիվը ներկայացված է կամ լրիվ մեկերով կամ լրիվ զրոներով: Օրինակ՝ 5 = 00000:

Turing-ի մեքենայով գումարում կատարելու սկզբունքը հետևյալն է.

1. Երկու գումարելիները տեղադրվում են ժապավենի վրա՝ մեկ բացատով բաժանված։ Օրինակ՝ 2+3 կլինի 00 000
2. Turing-ի մեքենան սկսում է ամենաձախ բջջից և շարժվում աջ՝ ստուգելով յուրաքանչյուր սիմվոլ
3. Հանդիպելով բացատ՝ մեքենան այն փոխարինում է 0-ով
4. Գլխիկը շարունակում է շարժվել աջ, մինչև բացատ հանդիպելը։ Բացատին հանդիպելու դեպքում՝ ամենաաջ տեղում գրված 1-ը փոխարինվում է 0-ով։

Turing-Ի ՈՒՆԻՎԵՐՍԱԼ ՄԵՔԵՆԱՆ։ ՀԱՄԱԿԱՐԳՉԻ ՆԱԽԱՀԱՅՐԸ

1936 թ.-ի հոդվածում Turing-ը բացի Turing-ի մեքենայից խոսել է նաև Turing-ի ունիվերսալ մեքենայի հայեցակարգից. հենց այս գաղափարն է համարվում համակարգչային գիտության հիմքը:

Ինչպես տեսանք, Turing-ի մեկ մեքենան ընդունակ է լուծել իր դիմաց դրված մեկ կոնկրետ խնդիր, օրինակ՝ հաշվել թվի քառակուսին կամ սորտավորել թվերի հաջորդականությունը։

Turing-ը ներկայացրեց այն միտքը, որ հնարավոր է կառուցել մեկ Ունիվերսալ մեքենա՝ ընդունակ իմիտացնել ցանկացած Turing-ի մեքենա: Այդ մեքենան որպես մուտքային տվյալ ստանում է՝ այդ պահին պահանջվող Turing-ի մեքենայի նկարագիրը և իրեն պահում է վերջինիս պես։ Օրինակ՝ մեկ Turing-ի մեքենա կարող է գումարել, իսկ մյուսը հանել։ Կախված մեր տված կարգավորումներից՝ Ունիվերսալ Turing-ի մեքենան մի պահի կարող է գումարել տրված թվերը՝ մեկ այլ պահի հանել։

Նկար 4: Turing-ի ունիվերսալ մեքենայի աշխատանքի սկզբունքը

Այսպիսով, Turing-ի ունիվերսալ մեքենան որպես մուտքային տվյալներ ստանում էր ցանկալի գործողություն կատարող Turing-ի մեքենայի նկարագիրը (կարգավորումները) և տվյալները, որոնք պետք է մշակվեն։ Հեշտ է նկատել, որ սա մերօրյա կենտրոնական մշակիչ հանգույցի՝ նույն ինքը CPU-ի, ընդհանրացրած նկարագիրն է։ Ինչպես Turing-ի ունիվերսալ մեքենան, կախված մուտքային կարգավորումներից, իմիտացնում է Turing-ի որևէ մեքենա, CPU-ն կախված տվյալ պահին փոխանցված մեքենայական կոդի՝ իրականացնում է դրան համապատասխան գործողությունը։
Ստացվում է, որ դեռևս 1936 թվականին Turing-ը ներկայացրել է մերօրյա համակարգչի հայեցակարգը, դիտարկել այն՝ որպես առանձին փոքր խնդիրներ լուծող համակարգերի միասնություն, որոնցից յուրաքանչյուրն ունի համապատասխան նկարագիրը։

Հարկ է նաև նշել, որ և՛ Turing-ի մեքենան, և՛ Turing-ի ունիվերսալ մեքենան հայեցակարգային մաթեմատիկական մոդելներ են. դրանք իրականում գոյություն չունեն, իհարկե կան որոշ ֆիզիկական մոդելներ և համակարգչային սիմուլյացիաներ, որոնք կատարում են որոշ հաշվարկներ, բայց դրանք լիարժեք չեն համապատասխանում մեքենայի օրիգինալ կոնցեպտին։

Նկար 5: Turing-ի մեքենայի ֆիզիկական մոդելը

Alan Turing-ը լինելով ականավոր մաթեմատիկոս և գիտնական՝ համակարգչային գիտության մեջ թողել է իր անջնջելի հետքը։ Նրա բացառիկ միտքն ու նորարար գաղափարները հեղափոխեցին մաթեմատիկայի և համակարգչային գիտությունների ոլորտները:

Turing-ը, իր նեկայացրած հայեցակարգային մեքենաների միջոցով, կարողացավ տալ հաշվողականության մասին գաղափար։ Նա այդ մոդելի հիման վրա ցույց տվեց հաշվողականության թեորետիկ սահմանները, ապացուցեց, որ կան խնդիրներ, որոնք անլուծելի են նույնիսկ ֆիզիկական սահմանափակումներ չունեցող թեորետիկ մոդելների համար։

Turing-ի ներդրումը չի սահմանափակվել այս հոդվածում ներկայացված հայեցակարգերով. նա իր անգնահատելի ներդրումն է ունեցել կրիպտոգրաֆիայի ոլորտում, մոտ մեկ դար առաջ տվել է արհեստական բանականության սահմանումը և քննարկել դրա հնարավորությունները։ Իզուր չեն Alan Turing-ին կոչել համակարգչային գիտությունների հայրը։

Հոդվածի համահեղինակ: @lika.sargsyan.99