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

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

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

(1) если определено, то ;

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