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

Основные определения

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

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

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

Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется вычислимой, если её график [math]F = \lbrace \langle x, y\rangle \mid f(x)[/math] определено и равно [math]y \rbrace[/math] является перечислимым множеством пар натуральных чисел.

Теорема:

Приведенные определения эквивалентны.

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow [/math] Напишем полуразрешающую программу для множества [math]F[/math]. [math]p(\langle x, y\rangle):[/math] for [math]a \in D(f)[/math] if [math]a == x \land f(a) == y[/math] return 1 Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1. [math]\Leftarrow[/math] Напишем программу, вычисляющую функцию [math]f[/math]. [math]f(n):[/math] for [math]\langle x, y \rangle \in F[/math] if [math]x == n[/math] return [math]y[/math] Так как [math]F[/math] — перечислимое множество, то можно перебрать элементы этого множества.

[math]\triangleleft[/math]

Замечание

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

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

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

[math]p(x):[/math]
  while True

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

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

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

Лемма:

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

Доказательство:

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу. [math]p(x):[/math] [math]f(x)[/math] 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]f[/math]. Тогда [math]E(f)[/math] является перечислимым множеством.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

Доказательство:

[math]\triangleright[/math]

Для доказательства достаточно написать полуразрешающую программу. [math]p(x):[/math] if [math]f(x) \in X[/math] return 1 На проверке условия [math]f(x) \in X[/math] программа может зависнут, если [math]f(x)[/math] не определено или [math]f(x) \notin X[/math]. Если [math]f(x)[/math] не определено, то [math]x \notin f^{-1}(X)[/math]. Условие [math]f(x) \notin X[/math] можно проверить, так как [math]X[/math] перечислимо.

[math]\triangleleft[/math]

Характеристика перечислимых множеств через вычислимые функции

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

Множество [math]X[/math] называется перечислимым (англ. computably enumerable set), если выполняется хотя бы одно из условий: существует программа, перечисляющая все элементы [math]X[/math] в произвольном порядке; [math]X[/math] является областью определения вычиcлимой функции [math]f[/math]; [math]X[/math] является областью значений вычиcлимой функции [math]f[/math]; функция [math]f_X(x) = \begin{cases} 1, & x \in X \\ \bot, & x \notin X \end{cases}[/math] — вычислима.

Теорема:

Определения 1, 2, 3, 4 эквивалентны.

Доказательство:

[math]\triangleright[/math]

[math]1 \Rightarrow 4[/math] Пусть [math]p[/math] — программа, перечисляющая [math]X[/math]. Приведём программу [math]q[/math], вычисляющую функцию [math]f_X(x)[/math]: [math]q(x):[/math] for [math]k = 1 \ .. \ \infty[/math] if [math] p(k) == x [/math] return 1 [math]2 \Rightarrow 1[/math] Пусть [math]X[/math] — область определения вычислимой функции [math]f[/math], вычисляемой программой [math]p[/math]. Тогда [math]X[/math] перечисляется такой программой: [math]q():[/math] for [math] TL = 1 \ .. \ \infty [/math] for [math] k = 1 \ ..\ TL[/math] if [math]p(k)|_{TL} \neq \bot [/math] print [math]k[/math] [math]3 \Rightarrow 1[/math] Пусть [math]X[/math] — область значений вычислимой функции [math]f[/math], вычисляемой программой [math]p[/math]. Тогда [math]X[/math] перечисляется такой программой: [math]q():[/math] for [math] TL = 1 \ .. \ \infty [/math] for [math] k = 1 \ ..\ TL[/math] if [math]p(k)|_{TL} \neq \bot [/math] print [math]p(k)|_{TL}[/math] [math]4 \Rightarrow 2[/math], [math]4 \Rightarrow 3[/math] Пусть дана [math]f_X(x)[/math]. Введём новую функцию [math]g(x) = x[/math], если [math]f_X(x) \neq \bot[/math]. Очевидно, что она вычислима и что её область определения и область значений совпадают с [math]X[/math].

[math]\triangleleft[/math]

Теорема об униформизации

Теорема:

Пусть [math]F[/math] — перечислимое множество пар натуральных чисел. Тогда существует вычислимая функция [math]f[/math], определённая на тех и только тех [math]x[/math], для которых найдется [math]y[/math], при котором [math]\langle x, y \rangle \in F[/math], причём значение [math]f(x)[/math] является одним из таких [math]y[/math].

Доказательство:

[math]\triangleright[/math]

Напишем программу, вычисляющую функцию [math]f[/math]. [math]f(x):[/math] for [math]\langle a, b \rangle \in F[/math] if [math]x == a[/math] return [math]b[/math] Так как множество [math]F[/math] перечислимо, то его элементы можно перебрать.

[math]\triangleleft[/math]

Теорема о псевдообратной функции

Теорема:

Для любой вычислимой функции [math]f[/math] существует вычислимая функция [math]g[/math], являющаяся псевдообратной в следующем смысле: [math]E(f) = D(g)[/math], и при этом [math]f(g(f(x))) = f(x)[/math] для всех [math]x[/math], при которых [math]f(x)[/math] определена.

Доказательство:

[math]\triangleright[/math]

Напишем программу, вычисляющую функцию [math]g[/math]. [math]g(n):[/math] for [math]x \in D(f)[/math] if [math]f(x) == n[/math] return [math]x[/math] Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения.

[math]\triangleleft[/math]

Источники информации

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 134, с. 176. ISBN 5-900916-36-7
• Wikipedia — Computable function
• Wikipedia — Computably enumerable set
• Википедия — Вычислимая функция
• Википедия — Перечислимое множество