Թյուրինգի մեքենա
| Թյուրինգի մեքենա | |
|---|---|
 Թյուրինգի մեքենայի գեղարվեստական տեսքը | |
| Տեսակ | մոդել |
| Հայտնաբերող | Ալան Թյուրինգ |
| Անվանված է | Ալան Թյուրինգ |
Թյուրինգի մեքենա, վերացական մեքենա է, որը յուրաքանչյուր քայլի ժամանակ վերցնում է սլաքի ցույց տված նշանը, այնուհետև կարող է ցուցումներին համապատասխան դրանք փոխել՝ մեկ քայլ աջ կամ ձախ գնալով։ Ավելի ճշգրիտ՝ այն հաշվարկման մաթեմատիկական մեթոդ է։ Բացի մոդելի պարզությունից, Թյուրինգի մեքենան ստանալով ցանկացած համակարգչային ալգորիթմ, կարող է մոդելավորել այդ ալգորիթմի տրամաբանությունը։ Մեքենան գործում է անվերջ հիշողության ժապավենի վրա, որը բաժանված է բջիջների։ Այն տեղադրում է իր գլխավոր մասը բջջի վերևում և «կարդում է» (սքանավորում է) նշանն այնտեղ։ Այնուհետեև յուրաքանչյուր նշանն ու այդ նշանի ներկայիս վերջավոր աղյուսակում գտնվող տեղը օգտագործողի նշած ցուցումներով աշխատող (i) մեքենան կարդում է նշանը բջիջում, հետո (ii)-ն տեղափոխվում է ժապավենը մի բջիջ ձախ կամ աջ։ Այնուհետև (iii)-ին փոխանցվում է հաջորդ ցուցումը կամ հաշվարկը դադարեցվում է։
Պատմություն[խմբագրել | խմբագրել կոդը]
Թյուրինգի մեքենան ստեղծվել է 1936 թվականին Ալան Թյուրինգի կողմից, ով կոչեց այն ա-մեքենա (ավտոմատ մեքենա)։ Այս մեքենայով Թյուրինգը ցույց տվեց, որ հետևյալ երկու հարցերն ունեն բացասական պատասխան.
- Գոյություն ունի՞ որևէ մեքենա, որը կարող է որոշել կամայական մեքենան իր ժապավենի վրա «շրջանաձև է» գործում, թե ոչ։
- Գոյություն ունի՞ որևէ մեքենա, որը կարող է որոշել կամայական մեքենան իր ժապավենի վրա երբևէ տպու՞մ է տրված նշանը, թե ոչ
Այսպիսով, կատարելով կամայական հաշվարկներ կատարող պարզ սարքերի մաթեմատիկական ուսումնասիրություն, նա հանգեց հաշվարկների մասին հետևյալ եզրակացությանը. մասնավորապես, թույլտվության (որոշման) խնդրի անհաշվելիությանը[1]։ Հետազոտությունների հիման վրա Թյուրինգը ձևակերպեց ալգորիթմների հիմնական հիպոթեզը։ Որևէ ֆունկցիայի արժեքներ գտնելու համար նախատեսված ալգորիթմ գոյություն ունի այն դեպքում, երբ կարելի է հաշվարկել Թյուրինգի մեթոդով՝ Թյուրինգի մեքենայի վրա։ Այս թեզը համարվում է աքսիոմ, և չի կարող խիստ ապացուցվել մաթեմատիկորեն, քանի որ ալգորիթմը հստակ մաթեմատիկական հասկացություն չէ։ Ժամանակակից համակարգիչը, որը մինչև ավելի արագ հիշողության սարքերի հնարումը օգտագործում էր տարբերության շարժիչներ, պատկանում է հաշվիչ մեքենաների թվային դասին, հետևաբար Թյուրինգի մեքենայի կատարելագործված տարբերակն է։
Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]
Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]
- Машина Тьюринга// Лекция Александра Шеня в проекте ПостНаука (06.04.2013)
- Определения и примеры машин Тьюринга
- Пример аппаратной реализации машины Тьюринга
- Программы для машины Тьюринга. Сложение. Умножение чисел и др..
- Java-апплет, моделирующий машину Тьюринга.
- Программная реализация на C#
- Web Turing Machine Веб-приложение для создания и выполнения машины Тьюринга (Javascript)
- Javascript версия машины Тьюринга (работает on-line)
- Javascript версия многоленточной машины Тьюринга (работает on-line)
| ||||||
