Вычислимые функции

Пусть = (₁,₂,…_n), n 1, - произвольный набор целых неотрицательных чисел. Слово называется основным машинным кодом набора в алфавите {0,1} и обозначается через K( ), т.е. K( ) = , где = (₁,₂,…_n), n 1.

В частности, слово является основным машинным кодом числа 

В дальнейшем будем рассматривать частичные числовые функции.

Определение. Функция f(x₁, x₂,…, x_n), n 1, называется частичной числовой функцией, если переменные x_i ( ) принимают значения из расширенного натурального ряда N={0,1,...} и в том случае, когда на наборе = (₁,₂,…_n) функция f определена, f( )N.

Определение. Частичная числовая функция f называется вычислимой, если существует машина Тьюринга M_f, обладающая следующими свойствами:

1. Если f( ) определена, то M_f (K( ))=K(f( )) (т.е. машина M_f, будучи применима к основному коду для и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для f( )).

2. Если f( ) не определена, то либо M _f(K( )) не является кодом никакого числа из N, либо M_f не применима к слову K( ) (т.е. машина M_f, будучи применима к основному коду для и находясь в начальном состоянии над его левой единицей, либо останавливается, но при этом запись на ленте отлична от кода любого числа из N, либо не останавливается).

Определение. Если функция f вычислима с помощью машины M_f, то будем говорить, что машина M_f вычисляет функцию f.

Определение. Машина M_f вычисляет функцию f(x₁, x₂,…, x_n) правильным образом:

а) если f( ) определено, то M_f (K( ))=K(f( )), при этом останов происходит над левой единицей кода для f( );

б) если f( ) не определено, то M_f, будучи применима к K( ) и находясь в начальном состоянии над его левой единицей, не останавливается.

П ример.

1. S(x) = x + 1;

2. O(x₁, x₂,…, x_n)=0, n 1; простейшие частичные

3. ( x₁, x₂,…, x_n) = x_m, . числовые функции

Покажем, что данные функции вычислимы.

1) Вычислимость функции S(x) следует из того, что она реализуема следующей машиной:

S
0	1S
1	1L

2) Вычислимость функции O(x₁, x₂,…, x_n)=0, n 1, следует из того, что она реализуема следующей машиной:

O
0	1S
1	0R

3) Вычислимость функции ( x₁, x₂,…, x_n) = x_m, , следует из того, что она реализуема следующей машиной:

	q1	…	qm-1	qm		…	qn
0	0R	…	0R	0R	0R	…	0L	0L	0R
1	0R	…	0R	1R	0R	…	0R	1L	1L

Машина для идет направо (в начальный момент обозревается, как всегда, левая единица основного кода) и стирает все массивы основного кода для (₁,₂,…_n), кроме m-го, затем возвращается влево и встает над левой единицей оставшегося массива.

Замечание. Машина M_f вычисляет данные функции правильным образом.

Лемма. Если f(x₁, x₂,…, x_n) - вычислимая функция, то существует машина Тьюринга, которая вычисляет ее правильным образом.

Замечание. В дальнейшем для вычислимых функций будем использовать исключительно машины, вычисляющие их правильным образом.

Через P_выч. обозначим класс всех вычислимых функций.