Машина на Тюринг

Художествено представяне на машината на Тюринг

Машина на Тюринг е абстрактно изчислително устройство, описано от английския математик Алън Тюринг през 1936 г.

Тюринг използва тази абстракция, за да даде първото точно определение на понятието алгоритъм (наричано още механична, формална или ефективна процедура). Машината се използва при доказването на основни резултати в компютърните науки, най-вече в областите изчислимост и сложност на алгоритмите, както и в математическата логика.

Описание

Моделът на машината на Тюринг се основава на телетипа, като обхватът му е разширен и позволява движение на хартиената лента и в двете посоки, а главата може да чете, изтрива и печата нови символи, вместо само да прочита и пробива постоянна перфорация.

Машината на Тюринг се състои от четири компонента:

1. Памет – безкрайна лента, състояща се от клетки, във всяка от които е записан символ от някаква крайна азбука. Азбуката съдържа специален празен символ (обикновено обозначаван с '0') и един или повече други символи. Във всеки момент от работата на машината лентата е крайна, но при нужда може да ѝ залепяме отляво или отдясно нови клетки, съдържащи празния символ.
2. Глава, която във всеки момент от изчислението се намира над определена клетка от лентата. При всеки такт главата прочита символа от клетката, над която се намира, записва нов символ и се премества наляво или надясно по лентата в зависимост от изпълняваната инструкция и прочетения символ.
3. Програма – краен списък от инструкции, който за разлика от съвременните компютри е отделен от паметта. Всяка инструкция е поредица от указания какво да се направи, ако главата е прочела i-тата буква от азбуката. Всяко указание съдържа информация какъв символ да се запише обратно върху лентата, коя инструкция ще се изпълнява на следващата стъпка и накъде (наляво или надясно) да се премести главата.
4. Регистър, съдържащ номера на активната инструкция (програмен брояч). Една от инструкциите се приема за начална, т.е. изчислението започва със зареждането на номера ѝ в програмния брояч. Има и крайна инструкция – при достигането ѝ изчислението спира.

Пример

Ще разгледаме машина, работеща с двубуквена азбука – буквите са 0 и 1. Ще наречем нашата машина Double. Ето списъка от инструкциите ѝ:

A 0:(0,s,R) 1:(0,B,R)
B 0:(1,C,L) 1:(1,B,R)
C 0:(1,A,L) 1:(1,C,L)

Имената на инструкциите са големите латински букви A, B и C. С малка буква s сме означили специалната инструкция за спиране на изчислението.

Всяка инструкция съдържа 2 указания – какво да прави при прочетена 0 или 1. Например инструкцията B при прочетена 0 трябва да изпълни указанието (1,C,L), чието тълкувание е: запиши върху лентата 1, следващата активна инструкция ще е C, премести главата наляво.

Предназначението на тази проста машина е да удвоява поредица от единици, при следните условия: в началото лентата съдържа поредица от няколко единици, а всички останали клетки са празни (т.е. заети от символа 0) и главата се намира над най-дясната единица и началната активна инструкция е A. Започвайки изчислението, машината в крайна сметка ще спре, като броят на единиците в поредицата ще е два пъти по-голям от началния им брой.

Нека в началото на изчислението лентата съдържа 3 поредни единици. Ето цялото изчисление, стъпка по стъпка (с курсив е отбелязан символа, над който се намира главата):

ст. инс. лента
-- – ----------------
 1 A 01110000
 2 B 01100000
 3 C 01101000
 4 A 01111000
 5 B 01011000
 6 B 01011000
 7 B 01011000
 8 C 01011100
 9 C 01011100
10 C 01011100
11 A 01111100
12 B 00111100
13 B 00111100
14 B 00111100
15 B 00111100
16 B 00111100
17 C 00111110
18 C 00111110
19 C 00111110
20 C 00111110
21 C 00111110
22 A 01111110
23 s 01111110

Изобщо, ако началната поредица съдържа k единици, машината Double ще спре след изпълнението на 2k²+k+1 стъпки (без да броим инструкцията за спиране), на лентата ще има 2k единици и главата ще е над най-лявата единица. Тези свойства на Double могат да бъдат доказани с използване на математическа индукция.

Изчислимост и алгоритми

През 30-те години на XX век били предложени няколко математически определения на понятието ефективен метод (алгоритъм, формална процедура, изчисляващо устройство, компютър). Било също доказано, че всички такива определения са еквивалентни, т.е. класа задачи, които можем да решим с някоя от предложените схеми (примерно с машини на Тюринг) точно съвпада с класа задачи, решими с всяка друга разумна схема за правене на изчисления (примерно най-мощните съвременни компютри, с допълнителна възможност да им добавяме памет по време на изчислението). Тази еквивалентност, приемана като природен закон за всички възможни схеми за изчисляване се нарича тезис на Чърч по името на американския логик Алонсо Чърч, който я забелязва най-рано.

Тезисът на Чърч позволява да се дефинира (определи) понятието алгоритъм така:

Алгоритъм е всяко правило за изчисляване, което може да бъде представено чрез конкретна машина на Тюринг.

Машината Double, която описахме по-горе представя универсален алгоритъм за удвояване на число, независимо колко голямо е то. За решаването на една задача може да има различни алгоритми. Числото в нашия примерен алгоритъм беше представено в линейно кодиране и удвояването му е доста бавно. Можем да направим друга, по-ефективна машина на Тюринг за удвояване, която да ползва азбука от 3 букви (празен символ ' ', '0' и '1'), числото на лентата да е записано в двоичен код, при което удвояването ще се сведе до изписването на '0' в първата празна клетка отдясно на числото.

Пак от тезиса на Чърч следва, че когато създаваме нов алгоритъм не е необходимо да се мъчим да го опишем като машина на Тюринг. Достатъчно е да опишем алгоритъма на кой да е от стандартните езици за програмиране. Тезисът гарантира, че получената програма може да се трансформира в еквивалентна машина на Тюринг.

Нерешими задачи

През 30-те години на XX век бил разрешен и следният важен въпрос: Съществуват ли задачи, които могат да се формулират като задачи за изчисляване, но да няма алгоритъм, който ги решава?

Оказва се, че има много такива задачи. Ето една нерешима задача:

Има ли алгоритъм, който да определя дали подадена на входа му компютърна програма решава задачата за удвояване на число, представено като поредица от единици?

Друга формулировка: Има ли машина на Тюринг, която да решава дали описана върху лентата ѝ последователност от символи е дефиниция на алгоритъм, еквивалентен на машината Double?

Горната задача е нерешима и в по-обща формулировка, известна като теорема на Райс, т.е. няма алгоритъм, който да установява еквивалентност на компютърни програми. Такъв тип нерешимост има важно практическо значение – не можем да създадем автоматизирани средства за проверка на коректността на компютърните програми.

Още през 1936 г. Тюринг доказва, че няма алгоритъм, който да определя дали дадена програма ще завърши изчислението си или ще зацикли.

Нерешимите задачи имат пряка връзка с основите на математиката и математическата логика. Известната теорема на Гьодел за непълнота, изключително важен резултат за математиката, но и за цялата наука и философията, доказана още през 1932 г. конструира специално неразрешимо твърдение за всяка достатъчно богата формална математическа теория. Това Гьоделево твърдение, което нито може да се докаже, нито да се опровергае с формални математически методи, по същество е еквивалентно на алгоритмично нерешима задача.

Вижте също

• Алгоритъм