Машина Тьюринга, планета інформатики

У 1936 р Аланом Тьюрингом для уточнення поняття алгоритму був запропонований абстрактний універсальний виконавець. Його абстрактність полягає в тому, що він являє собою логічну обчислювальну конструкцію, а не реальну обчислювальну машину. Термін «універсальний виконавець» говорить про те, що даний виконавець може імітувати будь-який інший виконавець. Наприклад, операції, які виконують реальні обчислювальні машини можна імітувати на універсальному виконавця. В наслідок, придумана Тьюрингом обчислювальна конструкція була названа машиною Тьюринга.
Крім того, передбачається, що універсальний виконавець повинен вміти доводити існування або відсутність алгоритму для того чи іншого завдання.

Що собою являє машина Тьюринга?

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

Щоб задати конкретну машину Тьюринга, потрібно описати для неї такі складові:

Зовнішній алфавіт. Кінцеве безліч (наприклад, А), елементи якого називаються буквами (символами). Одна з букв цього алфавіту (наприклад, а 0) повинна являти собою порожній символ.
Внутрішній алфавіт. Кінцеве безліч станів головки (автомата). Одне з станів (наприклад, q1) має бути початковим (запускає програму). Ще один зі станів (q0) має бути кінцевим (завершальним програму) - стан зупинки.
Таблиця переходів. Опис поведінки автомата (головки) в залежності від стану і ліченого символу.

Автомат машини Тьюринга в процесі своєї роботи може виконувати наступні дії:

Записувати символ зовнішнього алфавіту в клітинку (в тому числі і порожній), замінюючи знаходився в ній (в тому числі і порожній).
Пересуватися на одну клітинку вліво або вправо.
Міняти свій внутрішній стан.

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

Приклад роботи машини Тьюринга

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

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

Тут відбувається зсув головки вліво до тих пір, поки вона не виявиться над порожнім символом. Після цього машина переходить в стан q2 (команди якого збігаються з командами q1 попередньої програми).

Зображення, використані в статті