Машина Тьюринга. Машина Тьюринга (МТ) — математична абстракція, що являє собою вычислительную машину общего вида

Машина Тьюринга (МТ) — математична абстракція, що являє собою вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Алгоритм є точним математичним поняттям. У якості моделі алгоритма першою була модель машини Тьюринга, запропонована у 40-х роках 20-го сторіччя англійським математиком, логіком Аланом Тьюрингом, який вважається першим хакером і піонером інформатики.

Машина Тьюринга отримала найбільше розповсюдження у теоретичній математиці при вивченні властивостей алгоритмів. Вона дозволила розв’язувати багато важливих питань, пов’язаних з проблемою алгоритмічної розв’язуваності чи нерозв’язуваності задач.

Машина Тьюринга - це пристрій, що містить стрічку нескінченої з обох кінців довжини, яку розділено на комірки Я1, Я2, …, Яn,… та керуючий пристрій з кінцевою кількістю станів. Керуючий пристрій може переміщуватися ліворуч та праворуч по стрічці, читати та записувати у комірки символи деякого алфавіту (будемо розглядати алфавит, що складається всього з двох символів: 0 та 1). Існує також пустий символ (e), який заповнює всі комірки стрічки, окрім тих, де записані вхідні дані. У керуючому пристрої міститься таблиця переходів, що являє собою алгоритм, який реализується машиною Тьюринга. Кожне правило з таблиці наказує машині, в залежності від поточного стану і символа, що знаходиться у поточній комірці, перейти у новий стан і переміститься на одну комірку ліворуч чи праворуч. Деякі стани машины Тьюринга можуть бути відмічені як термінальні, і перехід у будь-який з них означає кінець роботи, зупинку алгоритма.

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

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

Візьмемо за приклад таблицю.

У цій таблиці стани машини Тьюринга позначені як Q₀, Q₁. Початковий стан позначається як Q₀, а стан Q₁ є кінцевим. У верхньому рядку записані символи вхідного алфавиту машини. Таких символів три: 0, 1, e.

Розглянемо рядок Q₀.

На перетині стовпчика “0” і рядка “Q₀” дія машини ULQ₀ означає:

- U – нічого у комірку не писати;

- L – зсунути стрічку на одну комірку ліворуч (вперед);

- Q₀ – машина залишається у старому стані, комірку не змінює і зсовує стрічку вперед.

На перетині стовпчика “1” і рядка “Q₀” дія машини така:

- 0 – у поточну комірку будет записано 0 замість 1;

- L – зсунути стрічку на одну комірку ліворуч (вперед);

- Q₀ – машина залишається у старому стані, комірку не змінює і зсовує стрічку вперед.

На перетині стовпчика “e” і рядка “Q₀” дія машини така:

- U (перше) – нічого у комірку не писати;

- U (друге) – стрічку не зсовувати;

- Q₁ – перейти у кінцевий стан.

Представлені вище дії обнуляють числа, тобто заміняють 1 на 0.

Це є дуже елементарна машина Тьюринга. Але, розв’язувати реальні задачі на машині Тьюринга ніхто не буде. Вона використовується для анализу алгоритмів. Тому питання ”Чи можна розв’язати цю задачу?” можна замінити на питання “Чи можна для цієї задачі побудувати машину Тьюринга?”