Лабораторна робота № 3

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

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

Структура машини Т'юринга

Машина Т'юринга (МТ) складається з двох частин - стрічки і автомата (див ліворуч) :

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

Домовимося порожній вміст клітини називати символом "порожньо" і означати знаком Λ ("лямбда"). У зв'язку з цим зображення стрічки, показане на малюнку справа, таке ж, як і на малюнку ліворуч. Ця угода зручна тим, що операцію стирання символу в деякій клітині можна розглядати як запис в цю клітину символу Λ, тому замість довгої фрази "записати символ в клітину або стерти символ", що знаходиться там, можна говорити просто "записати символ в клітину".

Автомат - це активна частина МТ. У кожен момент він розміщується під однією з клітин стрічки і бачить її вміст; це видима клітина, а символ, що знаходиться в ній - видимий символ; вміст сусідніх і інших клітин автомат не бачить. Крім того, в кожен момент автомат знаходиться в одному із станів, які означатимемо буквою q з номерами: q1, q2 і тому подібне. Знаходячись в деякому стані, автомат виконує якусь певну операцію (наприклад, переміщається направо по стрічці, замінюючи усі символи b на а), знаходячись в іншому стані - іншу операцію.

Опишемо тепер машину Т'юринга Θ ретельніше. Машина Θ має в розпорядженні кінцеве число знаків (символів, букв), які створюють так званий зовнішній алфавіт А = {a₀, а₁, .., а_n}. У кожну комірку стрічки, що оглядається, в кожен дискретний момент часу може бути записаний тільки один символ з алфавіта А. Заради одноманітності зручно вважати, що серед букв зовнішнього алфавіту А є "порожня буква", і саме вона записана в порожню комірку стрічки. Умовимося, що "порожньою буквою" або символом порожньоїкомірки являється буква Λа₀. Стрічка передбачається необмеженою в обидві сторони, але в кожен момент часу на ній записано кінцеве число непорожніх букв.

Далі, в кожен момент часу машина Θ здатна знаходитися в одному стані з кінцевого числа внутрішніх станів, сукупність яких Q = {q₀, q₁, .., q_m}. Серед станів виділяються два - початковий q1 і завершальний (чи стан зупинки) q0. Знаходячись в стані q1 машина починає роботу. Потрапивши в стан q0, машина зупиняється.

Автомат може виконувати три елементарні дії: 1) записувати у видиму клітину новий символ (міняти вміст інших клітин автомат не може); 2) зрушуватися на одну клітину вліво або управо ("перестрибувати" відразу через декілька клітин автомат не може); 3) переходити в новий стан. Нічого іншого робити автомат не уміє, тому усе більш складні операції так чи інакше мають бути зведені до цих трьох елементарних дій.

Робота машини Θ визначається програмою (функціональною схемою). Програма складається з команд. Кожна команда T(i,j)(i = 1, 2, .., m; j = 0, 1, .., n) є вираженням одного з наступних видів:

де 0 ≤ k ≤ т; 0 ≤ λ ≤ п. У виразах першого виду символ С часто опускатимемо.

Як же працює машина Т'юринга? Знаходячись в який-небудь момент часу в незавершальному стані (тобто в змозі, відмінному від q₀), машина здійснює крок, який повністю визначається її поточним станом q_iі символом a_j, який сприймається нею в даний момент на стрічці. При цьому зміст кроку регламентований відповідною командою T(i,j):q_ia_j→q_ka_lX, де X ϵ {С, П, Л}. Крок полягає в тому, що: 1) вміст a_j, клітини, що оглядається на стрічці, стирається і на його місце записується символ a_l (який може співпадати з a_j); 2) машина переходить в новий стан q_k (воно також може співпадати з предыдущим станом q₁); 3) машина переходить до огляду следующей правого комірки від тієї, яка оглядалася тільки що, якщо Х= П, або до огляду наступного лівого осередку, якщо X = Л, або ж продовжує оглядати ту ж комірку стрічки, якщо Х = С.

У наступний момент часу (якщо q_k ≠ q₀) машина робить крок, регламентований командою Т(k, l):q_ka_l →q_ra_sXі так далі. Оскільки робота машини, по умові, повністю определяется її станом q_i в даний момент і вмістом a_j обозреваемой у цей момент осередки, то для кожних q_i і a_j(i = 1, 2, ...,m; j= 0, 1, ..., n) програма машини повинна містити одну і тільки одну команду, що починається символами q_ia_j. Тому програма машини Т'юринга із зовнішнім алфавітом А = {а₀, а₁ ,..., а_п} і алфавітом внутрішніх станів Q = {q₀, q₁ ,..., q_m} містить m(n + 1) команд.

Словом в алфавіті А або в алфавіті Q, або в алфавіті AUQ називається будь-яка послідовність букв відповідного алфавіта. Під k -ою конфігурацією розумітимемо зображення стрічки машини з інформацією, що склалася на ній на початок k -го кроку (чи слово в алфавіті А, записане на стрічку на початок k -го кроку), з вказівкою того, який осередок оглядається в цей крок і в якому стані знаходиться машина. Мають сенс лише кінцеві конфігурації, тобто такі, в яких усі комірки стрічки, за виключенням, можливо, кінцевого числа, порожні. Конфігурація називається завершальною, якщо стан, в якому при цьому знаходиться машина, завершальний.

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

Говоритимемо, що непорожнє слово α в алфавіті А\ А\ {a₀} = {а₁ ,..., а_п} сприймається машиною в стандартному положенні, якщо воно записане в послідовних комірках стрічки, усі інші комірки порожні, і машина оглядає крайню справа комірку з тих, в яких записано слово α. Стандартне положення називається початковим (завершальним), якщо машина, сприймаюча слово в стандартному положенні, знаходиться в початковому стані q₁ (відповідно в стані зупинки q₀). Нарешті, будемо говорить, що слово α переробляється машиною в слово β, якщо від слова α, що сприймається в початковому стандартному положенні, машина після виконання кінцевого числа команд приходить до слова β, що сприймається в положенні зупинки.

Сама по собі МТ нічого не робить. Для того, щоб змусити її працювати, потрібно написати для неї програму. Ця програма записується у вигляді наступної таблиці:

А\Q	q1	…	qj	…	qm
А1
А2
Аi				q'A' [С, П, Л]
Аn
Λ

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

В цілому таблиця визначає дії МТ при усіх можливих конфігураціях і тим самим повністю задає поведінку МТ. Описати алгоритм у вигляді МТ - означає пред'явити таку таблицю.

(Зауваження. Часто МТ визначають як таку що складається із стрічки, автомата і програми, тому при різних програмах виходять різні МТ. Ми ж вважатимо, у дусі сучасних комп'ютерів, що МТ одна, але вона може виконувати різні програми).