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

Определение:

Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется вычислимой, если существует программа, вычисляющая функцию [math]f[/math]. То есть существует такая программа, что: если [math]f(n)[/math] определено для натурального числа [math]n[/math], то программа заканчивается на входе [math]n[/math] и выводит [math]f(n)[/math]; если [math]f(n)[/math] не определено, то программа зависает на входе [math]n[/math].

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

Примеры вычислимых функций

• Нигде не определённая функция вычислима.

p(x)
  return [math]\bot[/math]

• [math]f(x) = x^2[/math], где [math]x[/math] — рациональное число.

p(x)
  return [math]x^2[/math]

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции -- М.: МЦНМО, 1999 - С. 176