Определение вычислимой функции

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

Функция называется вычислимой, если существует машина Тьюринга такая, что:

1) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для ;

2) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, либо не останавливается, либо останавливается, но при этом запись на ленте отлична от кода для .

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

Машина Тьюринга реализует (вычисляет) функцию правильным образом, если:

1) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для ; при этом останов происходит над левой единицей кода для ;

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

Лемма. Если – вычислимая функция, то существует машина Тьюринга, которая вычисляет ее правильным образом.