Обчислювані по Т'юрингу функції

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

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

Тут корисно ввести наступні позначення. Для натурального х позначаємо:

Додатково вважаємо 0° = 1° = Λ - порожнє слово. Отже на слова 1° = Λ, 1¹ = 1, 1² = 11, 1³ = 111,.. дивитимемося як на "зображення" натуральних чисел 0, 1, 2, 3,..відповідно.

Таким чином, попереднє слово можна представити наступним чином: . Далі, починати переробку даного слова будемо із стандартного початкового положення, тобто з положення, при якому в стані q₁ оглядається крайня права одиниця записаного слова. Якщо функція f (х₁, х₂,..., х_п) визначена на цьому наборі значень аргументів, то в результаті на стрічці повинно бути записано підряд f (х₁, х₂,..., х_п) одиниць; інакше машина повинна працювати нескінченно. При виконанні усіх перерахованих умов говоритимемо, що машина Т'юринга обчислює цю функцію. Таким чином, сформульоване визначення стає абсолютно строгим.

Приведемо програми машин Т'юринга, які правильно обчислюють функції

Приклад 1. S(x) = х + 1. Функція здійснює переведення: q₁01^x0 => q₀01^x+1. Початковий і кінцевий стани повинні знаходитися на нулі зліва. Її програма: q₁0→q₂П, q₂1→q₂1П, q₂0→q₃1, q₃1→q₃1Л, q₃0→q₀0.

Перевірити роботу на словах.

Приклад 2. О(х) = 0. Функція О(x) = 0 здійснює переведення: q₁01^x0 => q₀00^x+1. Її програма: q₁0→q₂0П, q₂1→q₂1П, q₂0→q₃0Л, q₃1→q₄0, q₄0→q₃0Л, q₃0→q₀0. Відповідну машину Т'юринга позначили О (онулення).

Перевірити роботу на словах.

Приклад 3. Побудувати машину "ліве зрушення" Б^-, з початкового стандартного положення оброблюється слово 01^x q ₁0 в те ж саме слово і зупиняється, оглядаючи найлівішу комірку з нулем q ₀01^x0.

Програма машини Б^-: q₁0→ q₂0Л, q₂l → q₂lЛ, q₂0 → q₀0.

Перевірити роботу на словах.

Приклад 4. Побудувати машину "праве зрушення" Б⁺ Друга машина з початкового стану, в якому оглядається ліва комірка з нулем, слово q ₁01^x0 переробляє в те ж саме слово і зупиняється, оглядаючи найправішу комірку з нулем 01^x q ₀0.