2. Функции, вычислимые на машинах Тьюринга.

Для любого натурального числа обозначим через слово, со­стоящее из n + 1 числа единиц: 11... 1.

Функция , где ,, называется вычислимой на машине Тьюринга T_f = <A, Q, П, q₀, q₁>, если выполняются следующие условия:

1. из следует ;

2. из следует

т.е. начиная со слова машина T_f работает не­ограниченно долго, не приходя в заключительное состояние q₀.

Таким образом, вычислимость функции f на машине Тью­ринга T_f означает, что по любому набору из обла­сти определения (закодированному в виде наборов единиц длин n + 1, разделенных нулями) машина T_f выдает значе­ние (закодированное в виде набора единиц длины ), а для любого набора ма­шина T_f не завершает работу за конечное время.

Функция f называется правильно вычислимой на машине Тьюринга T_f = <A, Q, П, q₀, q₁>, если выполняются следующие условия:

1. из следует ;

2. из следует

т.е. начиная со слова машина T_f работает не­ограниченно долго, не приходя в заключительное состояние q₀. и при этом не достраиваются ячейки слева.

Функция f называется правильно вычислимой (сокращенно ПВФ), если f правильно вычислима на некоторой машине Тью­ринга.

Преимущество правильной вычислимости по сравнению с обычной вычислимостью на машинах Тьюринга состоит в том· что левее ячейки, напротив которой стоит головка в начальном состоянии, можно записывать информацию, которая не изменя­ется в процессе "правильного вычисления".

Пример 1. Нуль-функция 0-Функция о : N —> N, для которой о(х) =0, , правильно вычислима на машине ЛS.

2. Функция следования s : Ν —> Ν, для которой s(x) = х + 1, , правильно вычислима на машине S.

3. n-Местная функция проекции на т-ую координату , для которой правильно вычислима на композиции машин Тьюринга.

4. Функции + : Ν² —> Ν, +(х, у) = х +y, и · : Ν² —> Ν, , правильно вычислимы на машинах Сложение и Умножение соответственно.

Теорема 1. Если функции ,... и правильно вычислимы, то функция

правильно вычислима.

3. Рекурсивные функции и отношения

1. Примитивно рекурсивные функции.

Рассмотрим сна­чала всюду определенные числовые функции , т.е не нуль-местные операции на множестве Ν, и опре­делим понятие примитивно рекурсивной функции (сокращенно ПРФ).

Функции о(х), s(x), , называются простейши­ми примитивно рекурсивными функциями.

Пусть f— m-местная операция, g₁,...,g_m - n-местные опе­рации на множестве N. Оператор S, ставящий в соответствие операциям f и g₁,...,g_m n-местную операцию h, удовлетворяю­щую тождеству

называется оператором суперпозиции (подстановки). При этом всюду определенная функция

h = S(f, g₁,...,g_m)

является, очевидно, суперпозицией функций f и g₁,...,g_m.

Оператор примитивной рекурсии R каждой (п + 2)-местной операции f и n-местной операции g на множестве N ставит в соответствие (п + 1)-местную операцию

h=R(f,g)

удовлетворяющую следующей схеме примитивной рекурсии:

Для n = 0 схема примитивной рекурсии имеет следующий вид:

,

где a — постоянная одноместная функция, равная числу а.

Схема примитивной рекурсии образует некоторый индукци­онный процесс построения функции h, при котором на нулевом шаге используется функция g, а на каждом последующем шаге значение функции f от аргументов x₁,... ,х_m,, номера у предыду­щего шага и значения функции h, вычисленного на предыдущем шаге.

Функция f называется примитивно рекурсивной, если суще­ствует последовательность функций f₀, · · ·, f_n ,в которой f_n = f и всякая функция f_i является простейшей ПРФ или получается из предыдущих функций с помощью оператора суперпозиции S или оператора примитивной рекурсии R.

Пример 1. Функция сложения χ + у примитивно рекурсивна в силу схемы примитивной рекурсии

2. Схема примитивной рекурсии

обосновывает примитивную рекурсивность функции умножения .

Доказательство примитивной рекурсивности следующих функ­ций оставляется в качестве упражнения.

3. х^у, где 0⁰ = 1, — функция возведения в степень.

4. х!, где 0! = 1, — Х-факториал.

5.

знак числа х

6.

дополнение знака числа х

7. \х — у\ — модуль разности.

8. max(x, у) — максимум чисел x и у. \

9 min(x,y) — минимум чисел x и у.

10 [х/у], где [х/0] = x — частное от деления x на у.

11. rest(:r, у), где rest(x, 0) = x, — остаток от деления x на у.

Пусть f(x₁,... ,x_n,i) — (n + 1)-местная операция на мно­жестве N. Определим операторы суммирования и произведения:

Предложение 1. Если f — примитивно рекурсивная функция, то функции g₁,g₂, примитивно рекурсивны