Тьюрінга

Нагадаємо, що числовою називають функцію f(x₁,..., x_n), значеннями якої та значеннями її аргументів є невід'ємні цілі числа. Розглядатимемо частковічислові функції, тобто числові функції, визначені, загалом, не для всіх значень аргументів.

Для обчислення числових функцій на машинах Тьюрінга часто використовують спеціальне кодування чисел. Наприклад, невід'єм­не ціле число т можна задати набором з (m +1) одиниць, який позначють І ^{m+ 1}. Отже, 0 задають як 1, 1 —як 11, 2-як 111 тощо.

Числову функцію f(x₁, …, х_n) називають обчислюваною за Тьюрінгам, якщо існує машина Тьюрінга T така, що для довільних цілих невід'ємних m₁, m₂,..., m_n, якщо f (m₁, m₂,..., m_n)=m, то машина Т∈ застосовною до слова і в заключній конфігура­ції на деякому відрізку стрічки буде записано слово , а решта комірок (якщо такі будуть) виявляться порожніми. Якщо ж f (m₁, m₂,..., m_n) невизначене, то машина Т є незастосовною до слова

Приклад 10.3. Побудуємо машину Тьюрінга, яка обчислює чис­лову функцію s (x)= x +l. Зовнішній алфавіт A ={Λ, 1}, множина станів Q={q₀, q₁}, а команди можна визначити так: q₁1→ 1Пq₁.

Робота цієї машини у разі обчислення s (1) складається з конфі­гурацій, зображених на рис. 10.4. ▲