Анотація: Присвячена простий класичної обчислювальної моделі (опису) алгоритму (алгорітмізіруемого процесу) - машині А. Тьюрінг, проблеми зупинки такої машини (завершаемості такого процесу) і зв'язків цієї проблеми з класичної алгоритмічної проблемою рівності слів у вільних напівгрупах.
Навіщо потрібні прості обчислювальні моделі?
До сих пір нам було зручно посилатися на програмістський досвід. кажучи про алгоритми, програмах, інтерпретатора, покроковому виконанні і т.д. Це дозволяло нам ігнорувати деталі побудови тих чи інших алгоритмів під тим приводом, що читач їх легко відновить (або хоча б повірить все-таки не кожен читач у своєму житті писав інтерпретатор Паскаля на Паскалі).
Але в деяких випадках цього недостатньо. Нехай, наприклад, ми хочемо довести алгоритмічну нерозв'язність якогось завдання, у визначенні якої нічого не говориться про програми (в цьому розділі, наприклад, ми доведемо нерозв'язність проблеми рівності слів в напівгрупах. Заданих утворюють і співвідношеннями). Це зазвичай робиться так. Ми показуємо, що проблема зупинки зводиться до цього завдання. Для цього ми моделюємо роботу довільного алгоритму в термінах даної задачі (що це означає, буде видно з приводиться нижче прикладу). При цьому нам важливо, щоб визначення алгоритму було якомога простіше.
Таким чином, наш план такий. Ми опишемо досить просто визначається клас машин (його можна вибирати по-різному, ми будемо використовувати так звані машини Тьюринга), потім оголосимо, що будь-яка обчислювана функція може бути обчислена на такій машині, а потім покажемо, що питання про зупинку машини Тьюринга можна звести до питання про рівність слів в полугруппе.
Машини Тьюринга: визначення
Машина Тьюринга має нескінченну в обидві сторони стрічку. розділену на квадратики (осередки). У кожному осередку може бути записаний деякий символ з фіксованого (для даної машини) кінцевого безлічі. званого алфавітом даної машини. Один із символів алфавіту виділений і називається "пропуском" передбачається, що спочатку вся стрічка порожня, тобто заповнена пробілами.
Машина Тьюринга може змінювати вміст стрічки за допомогою спеціальної читаючої та пишучої головки. яка рухається уздовж стрічки. У кожен момент головка знаходиться в одній з комірок. Машина Тьюринга отримує від головки інформацію про те, який символ та бачить, і в залежності від цього (і від свого внутрішнього стану) вирішує, що робити, то є якийсь символ записати в поточному осередку і куди зрушити після цього (ліворуч, праворуч або залишитися на місці). При цьому також змінюється внутрішній стан машини (ми припускаємо, що машина не рахуючи стрічки має кінцеву пам'ять. Тобто кінцеве число внутрішніх станів). Ще треба домовитися, з чого ми починаємо і коли закінчуємо роботу.
Таким чином, щоб задати машину Тьюринга, треба вказати наступні об'єкти:
- довільне кінцеве безліч A (алфавіт); його елементи називаються символами;
- деякий виділений символ (пробіл. або порожній символ);
- кінцеве безліч S. зване безліччю станів;
- деякий виділене стан, зване початковим;
- таблицю переходів. яка визначає поведінку машини в залежності від стану і поточного символу (див. нижче);
- деяку підмножину, елементи якого називаються заключними станами (потрапивши в такий стан, машина зупиняється).
Таблиця переходів влаштована таким чином: для кожної пари вказана трійка. Тут зрушення одне з чисел -1 (вліво), 0 (на місці) і 1 (направо). Таким чином, таблиця переходів є функція типу S x A -> S x A x. певна на тих парах, в яких стан не є заключним.
Залишається описати поведінку машини Тьюринга. У кожен момент є деяка конфігурація. що складається з вмісту стрічки (формально кажучи, вміст стрічки є довільне відображення Z -> A), поточної позиції головки (деяке ціле число) і поточного стану машини (елемент S). Перетворення конфігурації в наступну відбувається з природничих правилами: ми дивимося в таблиці, що треба робити для даного стану і для даного символу, тобто з'ясовуємо новий стан машини, міняємо символ на вказаний і після цього зрушуємо головку вліво, вправо або залишаємо на місці. При цьому, якщо новий стан є одним із заключних, робота машини закінчується. Залишається домовитися, як ми подаємо інформацію на вхід машини і що вважається результатом її роботи. Будемо вважати, що алфавіт машини, крім пробілу, містить символи 0 і 1 (а також, можливо, ще якісь символи). Входом і виходом машини будуть кінцеві послідовності нулів і одиниць (виконавчі слова). Вхідний слово записується на порожній стрічці, головка машини ставиться в його першу клітку, машина приводиться в початковий стан і запускається. Якщо машина зупиняється, результатом вважається двоичное слово. яке можна прочитати, починаючи з позиції головки і рухаючись направо (поки не з'явиться символ, відмінний від 0 і 1).
Таким чином, будь-яка машина Тьюринга задає деяку часткову функцію на довічних словах. Всі такі функції природно назвати обчислюваних на машинах Тьюринга.
Машини Тьюринга: обговорення
Зрозуміло, наше визначення містить багато конкретних деталей, які можна було б змінити. Наприклад, стрічка може бути нескінченною тільки в одну сторону. Можна додати машині дві стрічки. Можна вважати, що машина може або написати новий символ, або зрушити, але не те й інше разом. Можна обмежити алфавіт. вважаючи, скажімо, що в ньому має бути рівно 10 символів. Можна вимагати, щоб в кінці на стрічці нічого не було, крім результату роботи (інші клітини повинні бути порожні). Всі перераховані і багато інших змін не змінюють класу обчислюваних на машинах Тьюринга функцій. Звичайно, є і образливі зміни. Наприклад, якщо заборонити машині рухатися наліво, то це радикально змінить справу по суті стрічка стане марною, так як до старих записів уже не можна буде повернутися.
Як зрозуміти, які зміни нешкідливі, а які ні? Мабуть, тут необхідний деякий досвід практичного програмування на машинах Тьюрінга, хоча б невеликий. Після цього вже можна уявляти собі можливості машини, не виписуючи програми повністю, а керуючись лише приблизними описом. Як приклад опишемо машину, яка подвоює вхідний слово (виготовляє слово XX. Якщо на вході було слово X).
Якщо машина бачить пробіл (вхідний слово порожньо), вона завершує роботу. Якщо немає, вона запам'ятовує поточний символ і ставить позначку (в алфавіті крім символів 0 і 1 будуть ще їх "помічені варіанти" і). Потім вона рухається направо до порожньої клітки, після чого пише там копію запомненного символу. Потім вона рухається наліво до позначки; уткнувшись в позначку, відходить назад і запам'ятовує наступний символ і так далі, поки не скопіює все слово.
Маючи деякий досвід. можна за всіма цими фразами бачити конкретні шматки програми для машини Тьюринга. Наприклад, слова "запам'ятовує символ і рухається направо" означають, що є дві групи станів, одна для ситуації, коли запомнен нуль, інша коли запам'ятати одиниця. і всередині кожної групи запрограмовано рух направо до першої порожній клітини.
Маючи ще трохи більше досвіду, можна зрозуміти, що в цьому описі є помилка не передбачено механізму зупинки, коли все слово буде скопійовано, оскільки копії символів нічим не відрізняються від символів вихідного слова. Зрозуміло й те, як помилку виправити треба як копій писати спеціальні символи і, а на останньому етапі все позначки видалити.
77. Покажіть, що функція "звернення", що перевертає слово задом наперед, обчислюваних на машині Тьюринга.
Інший приклад неформального міркування: пояснимо, чому можна не використовувати додаткових символів, крім 0. 1 і порожнього символу. Нехай є машина з великим алфавітом з N символів. Побудуємо нову машину, яка буде моделювати роботу старої, але кожній клітині старої буде відповідати блок з k клітин нової. Розмір блоку (число k) буде фіксований так, щоб усередині блоку можна було б закодувати нулями і одиницями все символи великого алфавіту. Вихідні символи 0. 1 і порожній будемо кодувати як 0. за яким йдуть (k-1) порожніх символів, 1. за яким йдуть (k-1) порожніх символів, і групу з k порожніх символів. Для початку треба розсунути букви вхідного слова на відстань k. що можна зробити без додаткових символів (дійшовши до крайньої літери, відсуваємо її, потім дійшовши до наступної, відсуваємо її і крайню і так далі); треба тільки розуміти, що можна ідентифікувати кінець слова як позицію, за якою слідує більш k порожніх символів. Ясно, що в цьому процесі ми повинні зберігати в пам'яті деякий кінцевий об'єм інформації, так що це можливо. Після цього вже можна моделювати роботу вихідної машини по кроках, і для цього теж достатньо кінцевої пам'яті (е кінцевого числа станів), так як нам важлива лише невелика околиця головки моделюється машини. Нарешті, треба стиснути результат назад.
Твердження про те, що будь-яка обчислювана функція обчислюваних на машині Тьюринга, називають тезою Тьюринга. Звичайно, його сенс залежить від того, що розуміти під словами "обчислювана функція". Якщо розуміти їх в розпливчасто-інтуїтивному сенсі ( "функція обчислюється алгоритмічно, тобто за чіткими, недвозначним, однозначним правилами" або щось в такому роді), звичайно, ні про яке доведенні тези Тьюрінга не може бути мови. Можна лише говорити, що багатовікова практика людства від Евкліда до Кнута не зустрілася з прикладом алгоритму, який не можна було б записати як програму машини Тьюринга і т.п. Втім, ще один (не надто переконливий) аргумент наведений нижче.
На закінчення обговорення наведемо обіцяний вище аргумент на користь того, що будь-яка обчислювана функція обчислюваних на машині Тьюринга. Нехай є функція. яку людина вміє обчислювати. При цьому, він, природно, повинен використовувати олівець і папір, так як кількість інформації. яке він може зберігати "в умі", обмежена. Будемо вважати, що він пише на окремих аркушах паперу. Крім поточного листа, є стопка паперів справа і стопка зліва; в будь-яку з них можна покласти поточний лист. завершивши з ним роботу, а з іншого стопки взяти наступний. У людини є олівець і ластик. Оскільки дуже дрібні літери не видно, число чітко помітних станів листа звичайно, і можна вважати, що в кожен момент на аркуші записана одна буква з певного кінцевого (хоча і вельми великого) алфавіту. Людина теж має кінцеву пам'ять. так що його стан є елемент деякого кінцевого безлічі. При цьому можна скласти деяку таблицю, в якій записано, чим скінчиться його робота над листом з використанням вмісту, розпочата в даному стані (що буде на аркуші, в якому стані буде людина і з якої пачки буде взято наступний лист). Тепер уже видно, що дії людини як раз відповідають роботі машини Тьюринга з великим (але кінцевим) алфавітом і великим (але кінцевим) числом внутрішніх станів.