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

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

Склад машини Тюринга

У кожної машини Тюрінга є стрічка , потенційно нескінченна в обидві сторони. Стрічка складається із дискретних комірок .
Є скінченна множина символів стрічки $S_0$ , $S_1$ …, $S_n$ , що називається алфавітом машини . Кожна комірка стрічки може бути зайнята не більш ніж одним символом.
Машина має деяку скінченну множину нутрішніх встанів $q_0$ , $q_1$ , …, $q_n$ . У кожен момент часу машина знаходиться лише в одному із цих станів.
Нарешті, є голівка (каретка) , яка у кожен момент часу знаходиться на одній із комірок стрічки.

Принцип роботи

Машина працює не безперервно, а покроково у дискретні моменти часу.
Якщо у якийсь момент $t$ голівка знаходиться на комірці, що містить символ $S_i$ , і машина знаходиться у внутрішньому стані $q_j$ , то вона може виконати одну з чотирьох доступних дій:

• голівка затирає символ $S_i$ , і записує у тій же комірці новий символ $S_k$
• голівка пересувається в сусідню ліву комірку стрічки
• голівка пересувається в сусідню праву комірку
• машина зупиняє виконання своєї роботи

Створення машини Тюринга

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

Таблиця переходів визначає набір правил переходів машини. Правило переходу описує, з якого внутрішнього стану $q$ та з яким символом $S_i$ у комірці під головкою потрібно виконати перехід. Пара $q \times S_i$ називається конфігурацією або умовою переходу. При виконанні переходу машина може виконати дії, що описуються як $S_k \times M \times p$ , де $S_k$ задає символ, який потрібно записати замість символа під кареткою, $M$ задає напрямок одиничного зсуву каретки на стрічці, а $p$ - це новий внутрішній стан, у який переходить машина після завершення поточного кроку.

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