в якій лівіше оглядається осередку записана серія пар 10, 10, ..., 10 (якщо читати справа наліво). Тепер на стрічці бракує однієї одиниці, тобто число одиниць одно (х/2) - 1. просунемося по стрічці вліво до останньої «пари» 10. Це можна зробити за допомогою циклу
(17): 1? 1Л;
(18): 0? 0л,
виконавши який, прийдемо до наступної конфігурації: 001 110101 ... 0100. Повернемося вправо до найближчого нулю і перетворимо його на одиницю:
(19): 1? 1П;
(20): 1? 1П;
(21): 0? 1П.
Отримаємо конфігурацію 001111 101 ... 0100, в якій число одиниць знову одно х/2.
Якщо тепер переступимо вправо по стрічці через оглядається одиницю і переведемо машину в стан за допомогою команди
(22): 1? 1П,
то прийдемо до наступної конфігурації: 0011111 01 ... +0100, яка по суті аналогічна конфігурації (*). У результаті програма зациклюється (стає циклічною): знову найближчий 0 перетворюється на 1, а сама права 1 - в 0, потім машина повертається до самого лівому нулю, опиняючись на початку наступного циклу, і т.д.
Як же завершується робота програми? У деякий момент конфігурація буде мати вигляд 00111 ... 1110 100. Виконавши команди (17), (18), прийдемо до конфігурації 00111 ... 1 110100. Далі виконуються команди (19), (20), (21), що призводить до конфігурації: 00111 ... 111111 00. Залишається зупинити машину. Це робиться за допомогою команди
(23): 0? 0л.
Заключна конфігурація має вигляд: 00111 ... 1 111 100.
1.5 Правильна вичіслімость функцій на машині Тьюринга
У попередньому параграфі ми розглянули, яким чином «дана машина Тьюринга обчислює функцію f (,, ...,)». Для цього потрібно, щоб кожне з чисел,, ..., було записано на стрічку машини безперервним масивом з відповідного числа одиниць, а самі масиви були розділені символом 0. Якщо функція f (,, ..., визначена на даному наборі значень аргументів, то в результаті на стрічці повинно бути записано поспіль f (,, ...,) одиниць. При цьому ми не дуже строго ставилися до того, в якому початковому положенні машина починає працювати (часто це було стандартне початкове положення), в якому завершує роботу і як ця робота протікає.
Надалі нам знадобиться більш сильне поняття вичислімості функції на машині Тьюринга - поняття правильної вичислімості.
Визначення 5.1: Будемо говорити, що машина Тьюринга правильно обчислює функцію f (,, ...,), якщо початкове слово 0 ... 0 вона переводить в слово 0 ... 0 і при цьому в процесі роботи не прилаштовує до початкового слову нових осередків на стрічці ні ліворуч, ні праворуч. Якщо ж функція f не визначена на даному наборі значень аргументів, то, почавши працювати з зазначеного положення, вона ніколи в процесі роботи не буде надбудовувати стрічку зліва.
Приклад 5.1. Наведемо програми машин Тьюринга, правильно обчислює функції S (x)=x + 1 і O (x)=0. Функція S (x)=x + 1 здійснює переказ: 0= gt;. Її програма: 0? П, 1? 1П, 0? 1, 1? 1Л, 0? 0. Функція O (x)=0 здійснює переказ: 0= gt;. Її програма: 0? 0П, 1? 1П, 0? 0л, 1? 0, 0? 0л, 0? 0. Відповідну машину Тьюринга позначили О.
Приклад 5.2. Побудувати дві машини «лівий зрушення» і «праве зрушення». Перша з початкового стандартного положення переробляє слово 0 в той же самий слово і зупиняється, оглядаючи найлівішу клітинку з нулем. Друга машина з початкового стану, в якому оглядається ліва комірка з нулем, слово 0 переробляє в той же самий слово і зупиняється, оглядаючи найправішу клітинку з нулем.
Програма машини: 0? 0л, 1? 1Л, 0? 0. Ясно, що програма машини виходить з програми попередньої машини заміною символу «Л» символом «П».
1.6 Композиція машин Тьюринга
Визначення 6.1: Нехай задані машини Тьюринга і, що мають загальний зовнішній алфавіт {,, ...,} і алфавіти внутрішніх станів {,, ...,} і {,, ..., } відповідно. Композицією (або твором) машини на машину називається нова машина з тим же зовнішнім алфавітом {,, ...,}, внутрішнім алфавітом {,, ...,,, ...,} і програмою, получающейся наступним чином. У всіх командах з, що містять символ зупинки, замінюємо останній на. Всі інші символи в командах з залишаються незмінними. У командах з символ залишається незмінним, а всі інші стани (i=1, ..., t) замінюємо відповідно на. Сукупність усіх так отриманих команд утворює програму машини-композиції.
Введене поняття є зручним інструментом дл...
