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

Թյուրինգի մեքենա
Թյուրինգի մեքենայի գեղարվեստական տեսքը
Տեսակ	մոդել
Դաս	մոդել
Հայտնաբերող	Ալան Թյուրինգ
Անվանված է	Ալան Թյուրինգ

Թյուրինգի մեքենա, վերացական մեքենա է, որը յուրաքանչյուր քայլի ժամանակ վերցնում է սլաքի ցույց տված նշանը, այնուհետև կարող է ցուցումներին համապատասխան դրանք փոխել՝ մեկ քայլ աջ կամ ձախ գնալով։ Ավելի ճշգրիտ՝ այն հաշվարկման մաթեմատիկական մեթոդ է։ Բացի մոդելի պարզությունից, Թյուրինգի մեքենան ստանալով ցանկացած համակարգչային ալգորիթմ, կարող է մոդելավորել այդ ալգորիթմի տրամաբանությունը։ Մեքենան գործում է անվերջ հիշողության ժապավենի վրա, որը բաժանված է բջիջների։ Այն տեղադրում է իր գլխավոր մասը բջջի վերևում և «կարդում է» (սքանավորում է) նշանն այնտեղ։ Այնուհետեև յուրաքանչյուր նշանն ու այդ նշանի ներկայիս վերջավոր աղյուսակում գտնվող տեղը օգտագործողի նշած ցուցումներով աշխատող (i) մեքենան կարդում է նշանը բջիջում, հետո (ii)-ն տեղափոխվում է ժապավենը մի բջիջ ձախ կամ աջ։ Այնուհետև (iii)-ին փոխանցվում է հաջորդ ցուցումը կամ հաշվարկը դադարեցվում է։

Պատմություն

Թյուրինգի մեքենան ստեղծվել է 1936 թվականին Ալան Թյուրինգի կողմից, ով կոչեց այն ա-մեքենա (ավտոմատ մեքենա)։ Այս մեքենայով Թյուրինգը ցույց տվեց, որ հետևյալ երկու հարցերն ունեն բացասական պատասխան.

1. Գոյություն ունի՞ որևէ մեքենա, որը կարող է որոշել կամայական մեքենան իր ժապավենի վրա «շրջանաձև է» գործում, թե ոչ։
2. Գոյություն ունի՞ որևէ մեքենա, որը կարող է որոշել կամայական մեքենան իր ժապավենի վրա երբևէ տպու՞մ է տրված նշանը, թե ոչ

Այսպիսով, կատարելով կամայական հաշվարկներ կատարող պարզ սարքերի մաթեմատիկական ուսումնասիրություն, նա հանգեց հաշվարկների մասին հետևյալ եզրակացությանը. մասնավորապես, թույլտվության (որոշման) խնդրի անհաշվելիությանը։ Հետազոտությունների հիման վրա Թյուրինգը ձևակերպեց ալգորիթմների հիմնական հիպոթեզը։ Որևէ ֆունկցիայի արժեքներ գտնելու համար նախատեսված ալգորիթմ գոյություն ունի այն դեպքում, երբ կարելի է հաշվարկել Թյուրինգի մեթոդով՝ Թյուրինգի մեքենայի վրա։ Այս թեզը համարվում է աքսիոմ, և չի կարող խիստ ապացուցվել մաթեմատիկորեն, քանի որ ալգորիթմը հստակ մաթեմատիկական հասկացություն չէ։ Ժամանակակից համակարգիչը, որը մինչև ավելի արագ հիշողության սարքերի հնարումը օգտագործում էր տարբերության շարժիչներ, պատկանում է հաշվիչ մեքենաների թվային դասին, հետևաբար Թյուրինգի մեքենայի կատարելագործված տարբերակն է։

Արտաքին հղումներ

• Машина Тьюринга// Лекция Александра Шеня в проекте ПостНаука (06.04.2013)
• Определения и примеры машин Тьюринга
• Пример аппаратной реализации машины Тьюринга
• Программы для машины Тьюринга. Сложение. Умножение чисел и др..
• Java-апплет, моделирующий машину Тьюринга.
• Программная реализация на C#
• Web Turing Machine Веб-приложение для создания и выполнения машины Тьюринга (Javascript)
• Javascript версия машины Тьюринга (работает on-line)
• Javascript версия многоленточной машины Тьюринга (работает on-line)