Вычислимые функции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры вычислимых функций)
м («утверждение» → «лемма»)
Строка 40: Строка 40:
  
 
== Свойства вычислимой функции ==
 
== Свойства вычислимой функции ==
{{Утверждение
+
{{Лемма
|id = D(f)
+
|id = lemma-
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>D(f)</tex> {{---}} область определения функции <tex>f</tex>. Тогда <tex>D(f)</tex> является перечислимым множеством.
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>D(f)</tex> {{---}} область определения функции <tex>f</tex>. Тогда <tex>D(f)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
Строка 50: Строка 50:
 
Если функция <tex>f</tex> определена на входе <tex>x</tex>, то <tex>x \in D(f)</tex>. Тогда необходимо вернуть 1. Иначе программа зависнет при вызове <tex>f(x)</tex>.
 
Если функция <tex>f</tex> определена на входе <tex>x</tex>, то <tex>x \in D(f)</tex>. Тогда необходимо вернуть 1. Иначе программа зависнет при вызове <tex>f(x)</tex>.
 
}}
 
}}
{{Утверждение
+
{{Лемма
 +
|id = lemma-
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>E(f)</tex> {{---}} область значений <tex>f</tex>. Тогда <tex>E(f)</tex> является перечислимым множеством.
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>E(f)</tex> {{---}} область значений <tex>f</tex>. Тогда <tex>E(f)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
Строка 60: Строка 61:
 
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
 
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
 
}}
 
}}
{{Утверждение
+
{{Лемма
 +
|id = lemma-
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f(X)</tex> является перечислимым множеством.
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f(X)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
Строка 70: Строка 72:
 
Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1.
 
Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1.
 
}}
 
}}
{{Утверждение
+
{{Лемма
 +
|id = lemma-
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f^{-1}(X)</tex> является перечислимым множеством.
 
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f^{-1}(X)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  

Версия 22:20, 23 января 2012

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

Определение:
Функция [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].


Определение:
Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется вычислимой, если её график [math]F = \lbrace \langle x, y\rangle | 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]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 - С. 176