Вычислимость по Тьюрингу частично рекурсивных функций.

Теорема. Если функция f(x,y) правильно вычислима на машине Тьюринга, то и функция φ(x)=μy[f(x,y)=0], получающаяся с помощью оператора минимизации из функции f(x,y), также правильно вычислима на машине Тьюринга.

Доказательство: Обозначим F – машину Тьюринга, правильно вычисляющую функцию f(x,y). Используя ее, сконструируем такую машину Тьюринга, которая для заданного значения x вычисляет последовательно значения f(x,0), f(x,1), f(x,2), … до тех пор, пока в первый раз получится f(x,i)=0. После этого машина должна выдать на ленту число i, представляющее собой значение функции φ(x)=i. Если же для всех i будет иметь место f(x,i)>0,то машина должна будет работать вечно, и это будет означать, что функция φ не определена в точке x. начальная конфигурация на конструируемой машине такова: q₁01^x0. Будем мыслить ее следующим образом q₁01^x01⁰ и начнем с применения к ней машины “копирование” К₂. Получим конфигурацию 01^x01⁰q₁01^x01⁰. Теперь вычислим значение f(x,0), применив машину

F: 01^x01⁰q_α01^f(x,o).

Далее подбираем команды, которые при условии f(x,i)>0 преобразовывают конфигурацию 01^x01ⁱq01^f(x,i) в конфигурацию 01^x01ⁱ⁺¹q01^f(x,i+1):

q_α0→ q_α+10П: 01^x01⁰0 q_α+1 1^f(x,o);

q_α+11→ q_α+20: 01^x01⁰0 q_α+2 1^f(x,o)-1;

q_α+20→ q_α+30Л: 01^x01⁰q_α+3 001^f(x,o)-1;

q_α+30→ q_α+41: 01^x01⁰q_α+4 101^f(x,o)-1;

q_α+41→ q_α+51П: 01^x01¹0 q_α+5 01^f(x,o)-1;

О: 01^x01¹q0;

(Б^-)²: 01^x01¹q 01^x01¹;

F: 01^x01¹ q_β 01^f(x,1);

q_β0→ q_α0: 01^x01¹ q_α 01^f(x,1);

Последняя команда зацикливает программу, и машина от конфигурации 01^x01¹ q_α 01^f(x,1) переходит к конфигурации 01^x01² q_α 01^f(x,2) , затем к конфигурации 01^x01³ q_α 01^f(x,3) и т.д. Допустим, что на некотором шаге машина домтагла конфигурации 01^x01ⁱ q_α 01^f(x,i), при которой f(x,i)=0. Это значит, что φ(x)=i и машина должна выдать этот результат. Число i yнакоплено в «счетчике» 01ⁱ. Поэтому поступаем следующим образом. Уже имеющаяся команда q_α0→ q_α+10П приведет машину к конфигурации 01^x01ⁱ 0q_α+10. Следующие команды выдают на ленту необходимую конфигурацию q₀01ⁱ, т.е. q₀01^φ(x):

q_α+10→ q_γ0: 01^x01ⁱ 0q_γ0;

(Б^-)²: 01^x q_γ 01ⁱ 0;

ВО Б^-: q_δ 01ⁱ ;

q _δ 0→ q₀0: q₀01^φ(x)

Теорема доказана.

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

Теорема 3. Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна.