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

Машина Тьюринга, що була описана А.Тьюрингом у 1936 р., являє собою теоретичну модель обчислювальної машини. Машину Тьюринга (МТ) слід розглядати як одну з можливих формалізацій поняття алгоритму. Її робота може бути описана таким чином.Розглянемо стрічку, розділену на окремі комірки; ця стрічка є потенційно нескінченною в обидва боки. В кожній комірці може бути записаний певний символ з деякого заданого алфавіту A. Машина Тьюринга в будь-який момент часу може перебувати в певному стані (множина станів S є скінченною) і вказувати на певну комірку.

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

Програма машини Тьюринга являє собою послідовність інструкцій, кожна з яких має вигляд
aisj → akslI,
де ai, akє A; sl, smS, I є {R, L, H}.
Цей запис читається так: якщо машина перебуває в стані sl і зчитує символ ai, вона повинна записати в поточну позицію символ ak, перейти до стану sm і зсунутися вправо (відповідає літері R), вліво (відповідає літері L) або зупинитися (відповідає літері H).
Вважається, що на початку роботи машина перебуває на лівому кінці стрічки в початковому стані s0. Вона виконує операції, що визначаються її програмою. Якщо вона в деякий момент зупиняється, результатом роботи алгоритму вважається послідовність символів, яка записана на стрічці в момент зупинки.
Приклад.
Наведемо програму для машини Тьюринга, яка обчислює функцію x+y, де x,y - натуральні числа. Необхідно домовитися про представлення цих чисел. Стандартним для машини Тьюринга є представлення натурального числа n послідовністю з n+1 одиниць.

Ідея вирішення могла б полягати у тому, щоб замінити крайній зліва та крайній справа символи "1" на "0", а роздільник "0" - на "1". Якби були доступні відповідні команди, це можна було б зробити просто і швидко, але ми обмежені жорсткими рамками машини Тьюринга. За таких умов схема алгоритму полягає в такому: рухатися вправо до виявлення першої одиниці (початок першого числа); як тільки вона буде виявлена, замінити її на нуль і перейти в інший стан s1. Потім рухатися вправо, поки 0, який розділяє два числа, не буде замінений на 1; при цьому знову змінити стан. Далі рухатися вправо до появи першого нуля (кінця другого доданку). Після цього зсунутися вліво, замінити останню 1 на 0 та зупинитися.
Програма може мати вигляд:
0s0 → 0 s0R
1s0 → 0 s1R
1s1 → 1 s1R
0s1 → 1 s2R
1s2 → 1 s2R
0s2 → 0 s3L
1s3 → 0 s4H.
Наведений приклад показує, що машина Тьюринга є дуже незручною для програмування. Ці незручності пов'язані з тим, що:

* немає довільного доступу до пам'яті; якщо, наприклад, машина вказує на першу комірку, а потрібно перейти до десятої, машина повинна послідовно переглянути другу, третю і т.д. комірку;
* неструктурованість записів на стрічці; заздалегідь невідомо, де закінчується одне число і починається інше;
* дуже обмежений набір команд; відсутні, наприклад, основні арифметичні операції.

Універсальну машину Тьюринга можна неформально визначити як машину, яка може сприймати програму для обчислення будь-якої функції, яку в принципі можна обчислити за допомогою спеціалізованої машини M1 і надалі працювати як машина M1. Можна довести, що таку машину можна побудувати.
На початок

Клас функцій, обчислюваних за Тьюрингом

Можна довести, що машини Тьюринга здатні обчислювати лише функції з певного класу, а саме - функції, які дістали назву рекурсивних функцій. Функція, яка не є рекурсивною, не може бути обчислена за допомогою машини Тьюринга.
У класичній теорії розглядаються функції з цілими невід'ємними аргументами та цілими невід'ємними значеннями. Інші типи функцій конструюються на їх основі.

Визначення.
Рекурсивною функцією називається функція, яка може бути отримана з базових функцій за допомогою скінченної кількості застосувань підстановок, рекурсій та μ-операторів.

До базових функцій відносяться три функції:

* нуль-функція Z(x)=0 при будь-якому x;
* додавання одиниці: N(x) = x+1;
* проектуючі функції: Ui(x1,…, xn)= xi для всіх x1,…, xn.

Функція f(x1,…, xn) отримана з функцій g, h1,…, hm, за допомогою підстановки, якщо f(x1,…, xn) = g (h1(x1,…, xn ), …, h1(x1,…, xn ) ).
Функція f(x1,…, xn ,y) отримана за допомогою рекурсії, якщо:
f(x1,…, xn, y+1) =h (x1,…, xn , y, f(x1,…, xn, y));
f(x1,…, xn, 0) = g (x1,…, xn ) при n ≠ 0;
f(y+1) =h (y, f(y)); f(0) = k , k - ціле невід'ємне число при n= 0.
Функція f(x1,…, xn) отримана за допомогою μ-оператора, якщо її значення дорівнює мінімальному значенню y, при якому g(x1,…, xn, y)=0.

Частково рекурсивною називається функція, яка конструюється за допомогою скінченного числа підстановок, рекурсій та μ-операторів, але визначена не при всіх значеннях аргументів.
Якщо деяка функція може бути сконструйована з базових функцій за допомогою скінченного числа тільки підстановок та рекурсій, вона називається примітивно рекурсивною.
На початок

Теза Чорча. Алгоритмічно нерозв'язні проблеми
Теза Чорча.
Клас частково рекурсивних функцій співпадає з класом частково обчислюваних функцій.
Теза Чорча часто формулюється в еквівалентній формі, а саме: будь-який алгоритм в інтуїтивному розумінні цього слова може бути реалізований за допомогою деякої машини Тьюринга. Іншими словами, за допомогою машини Тьюринга можна вирішити будь-яку задачу, для якої існує алгоритм вирішення в інтуїтивному розумінні.

Довести тезу Чорча неможливо. Її можна було б спростувати, якби були б запропоновані формалізації поняття алгоритму, здатні обчислювати нерекурсивні функції. Але таких формалізмів досі запропоновано не було.
Якщо ми визнаємо тезу Чорча, ми можемо прийняти машину Тьюринга як основу для загального визначення алгоритму: алгоритм є послідовність інструкцій, яка може бути виконана за допомогою машини Тьюринга або еквівалентної їй обчислювальної моделі.

Тепер ми можемо дати більш чітке визначення універсального комп'ютера: універсальним називається комп'ютер, за допомогою якого можна промоделювати роботу машини Тьюринга.

Якщо теза Чорча є справедливою, ми повинні визнати наступне. Якщо вдається довести, що не існує машини Тьюринга, яка могла б вирішити певну проблему, то ця проблема є алгоритмічно нерозв'язною, тобто для неї не існує загального алгоритму вирішення. Такі проблеми насправді існують.
Наприклад, це знаменита проблема зупинки, яка формулюється так: потрібно для будь-яких початкових даних визначити, чи зупиниться машина Тьюринга, чи ні. Оскільки будь-яка програма, яка працює на будь-якому комп'ютері, може бути реалізована і на машині Тьюринга, це твердження можна переформулювати так: не існує загального алгоритму, який для будь-якої програми заздалегідь визначав би, зупиниться вона чи ні.
Але можна навести формалізми, які полегшують програмування і дозволяють здійснювати обчислення більш швидко, ніж машини Тьюринга.