бку вихідного слова і, нарешті, в якому становищі отримувати значення функції. Це можна робити, наприклад, наступним чином. Значення,, ..., аргументів будемо розташовувати на стрічці у вигляді наступного слова:
0 0 ... 0 0.
Тут корисно ввести такі позначення. Для натурального x позначаємо:
==.
Додатково вважаємо==?- Пусте слово. Так що на слова =?,=1,=11,=111, ... будемо дивитися як на «зображення» натуральних чисел 0, 1, 2, 3, ... відповідно. Таким чином, попереднє слово можна представити таким чином: 0 ... 0. Далі, починати переробку даного слова будемо зі стандартного початкового положення, тобто з положення, при якому в стані обозревается крайня права одиниця записаного слова. Якщо функція f (,, ...,) визначена на даному наборі значень аргументів, то в результаті на стрічці повинно бути записано поспіль f (,, ...,) одиниць; в іншому випадку машина повинна працювати нескінченно. При виконанні всіх перерахованих умов будемо говорити, що машина Тьюринга обчислює цю функцію. Таким чином, сформульоване визначення ставати абсолютно строгим.
Приклад 4.1. Побудуємо машину Тьюринга, яка обчислює функцію f (x)=x/2. Ця функція не всюди визначена: областю її визначення є лише безліч всіх парних чисел. Тому, враховуючи визначення 4.1, потрібно сконструювати таку машину Тьюринга, яка при подачі на її вхід парного числа давала б на вході половину цього числа, а при подачі непарного - працювала б необмежено довго.
Сконструювати машину Тьюринга - значить написати (скласти) її програму. У цьому процесі два етапи: спочатку створюється алгоритм обчислення значень функції, а потім він записується на мові машини Тьюринга (програмується).
В якості зовнішнього алфавіту візьмемо Двоелементною безліч A={0,1}. У цьому алфавіті натуральне число x зображується словом 11 ... 1, що складається з x одиниць, яку на стрічці машини Тьюринга записується у вигляді х одиниць, що складаються в осередках поспіль. Робота машини починається зі стандартного початкового положення: 01, ... 1 10 (число одиниць одно х).
Зробимо початок обчислювального процесу таким: машина оглядає осередки, рухаючись справа наліво, і кожну другу одиницю перетворює на 0. Такий початок забезпечується наступними командами:
(1): 1? 1Л;
(2): 1? 0л;
(3): 0? 0л.
Якщо число х одиниць нечетно, то машина продовжить рух по стрічці вліво необмежено, тобто буде працювати нескінченно. Якщо ж число х одиниць парне, то в результаті виконання команд створюється конфігурація 0010101 ... 01010, в якій число одиниць одно х/2. Залишається зрушити одиниці так, щоб між ними не стояли нулі. Для здійснення цієї процедури пропонується наступний алгоритм. Будемо рухатися по стрічці вправо, нічого на ній не змінюючи, до першої одиниці і перейдемо за одиницю. Пересування здійснюється за допомогою наступних команд:
(4): 0? 0П;
(5): 0? 0П;
(6): 1? 1П.
У результаті їхнього виконання отримаємо конфігурацію
010101 ... 010100. (*)
Зауважимо 0, перед яким зупинилися, на 1 і просунемося вправо до найближчого 0:
(7): 0? 1П;
(8): 1? 1П.
Отримаємо конфігурацію 00111 0101 ... 010100, в якій правіше оглядається осередку записані «пари» 01, ..., 01. Крім того, на стрічці одна одиниця записана зайва. Просунемося по стрічці вправо до останньої «пари» 01. Це можна зробити за допомогою своєрідного циклу:
(9): 0? 0П;
(10): 1? 1П.
Отримаємо конфігурацію 001110101 ... 01010 00. Рухатися далі вправо безглуздо. Повернемося на два осередки назад і замінимо одиницю з останньої «пари» 01 на нуль:
(11): 0? 0л;
(12): 0? 0л;
(13): 1? 0л.
Отримаємо конфігурацію 001110101 ... 01 00. Число одиниць на стрічці знову одно х/2. Просунемося вліво на одну клітинку за допомогою команди
(14): 0? 0л.
В результаті чого отримаємо конфігурацію 001110101 ... 010 100. Тепер знищимо саму праву одиницю і просунемося по стрічці вліво до наступної одиниці:
(15): 1? 0л;
(16): 0? 0л.
Отримаємо конфігурацію
... 0100, (**)
...
