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

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

Функция [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]

Свойства вычислимой функции

Утверждение:

[math]f[/math] — вычислимая функция. Тогда [math]D(f)[/math] — перечислимое множество, где [math]D(f)[/math] — область определения функции [math]f[/math].

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу. p(x) f(x) return 1 Если функция [math]f[/math] определена на входе [math]x[/math], следовательно, [math]x \in D(f)[/math]. Тогда необходимо вернуть 1. Иначе программа зависнет при вызове [math]f(x)[/math].

[math]\triangleleft[/math]

Утверждение:

[math]f[/math] — вычислимая функция. Тогда [math]E(f)[/math] — перечислимое множество, где [math]E(f)[/math] — область изменения функции [math]f[/math];

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу. p(x) for [math]y \in D(f)[/math] if x == f(y) then return 1 Так как [math]D(f)[/math] перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.

[math]\triangleleft[/math]

Утверждение:

[math]f[/math] — вычислимая функция. [math]f(X)[/math] — перечислимое множество, где [math]X[/math] — перечислимое множество.

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу. p(x) for [math]y \in D(f) \cap X[/math] if x == f(y) then return 1 Из замкнутости перечислимых языков относительно операции пересечения следует, что элементы множества [math]X \cap D(f)[/math] можно перебрать. Если программа находит слов, то она возвращает 1.

[math]\triangleleft[/math]

Утверждение:

[math]f[/math] — вычислимая функция. [math]f^{-1}(X)[/math] — перечислимое множество, где [math]X[/math] — разрешимое множество.

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу.

[math]\triangleleft[/math]

Утверждение:

[math]f[/math] — вычислимая функция. [math]f^{-1}(X)[/math] — перечислимое множество, где [math]X[/math] — перечислимое множество.

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу.

[math]\triangleleft[/math]

Литература

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