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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Свойства вычислимой функции)
м (rollbackEdits.php mass rollback)
 
(не показано 40 промежуточных версий 9 участников)
Строка 1: Строка 1:
 +
== Основные определения ==
 
{{Определение
 
{{Определение
|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если существует программа, вычисляющая функцию <tex>f</tex>. То есть существует такая программа, что:
+
|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''' (англ. ''computable function''), если существует программа, вычисляющая функцию <tex>f</tex>, такая, что:
# если <tex>f(n)</tex> определено для натурального числа <tex>n</tex>, то программа заканчивается на входе <tex>n</tex> и выводит <tex>f(n)</tex>;
+
* если <tex>f(n)</tex> определено для натурального числа <tex>n</tex>, то программа завершает свою работу на входе <tex>n</tex> и выводит <tex>f(n)</tex>;
# если <tex>f(n)</tex> не определено, то программа зависает на входе <tex>n</tex>.
+
* если <tex>f(n)</tex> не определено, то программа зависает на входе <tex>n</tex>.
 
}}
 
}}
''Замечание''<br/>
+
 
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и т.п. Поэтому аналогичным образом можно определить понятие вычислимой функции для рациональных чисел.
+
{{Определение
 +
|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если её график <tex>F = \lbrace \langle x, y\rangle \mid f(x)</tex> определено и равно <tex>y \rbrace</tex> является [[Перечислимые_языки|перечислимым]] множеством пар натуральных чисел.
 +
}}
 +
 
 +
{{Теорема
 +
|statement = Приведенные определения эквивалентны.
 +
|proof = <tex>\Rightarrow </tex><br/>
 +
Напишем полуразрешающую программу для множества <tex>F</tex>.
 +
<tex>p(\langle x, y\rangle):</tex>
 +
  '''for''' <tex>a \in D(f)</tex>
 +
    '''if''' <tex>a == x \land f(a) == y</tex>
 +
      '''return''' 1
 +
Так как [[Вычислимые функции#Свойства вычислимой функции|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/>
 +
<tex>\Leftarrow</tex><br/>
 +
Напишем программу, вычисляющую функцию <tex>f</tex>.
 +
<tex>f(n):</tex>
 +
  '''for''' <tex>\langle x, y \rangle \in F</tex>
 +
    '''if''' <tex>x == n</tex>
 +
      '''return''' <tex>y</tex>
 +
Так как <tex>F</tex> {{---}} перечислимое множество, то можно перебрать элементы этого множества.
 +
}}
 +
 
 +
=== Замечание ===
 +
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и многое другое. Поэтому аналогичным образом можно определить понятие вычислимой функции для счётных множеств.
  
 
=== Примеры вычислимых функций ===
 
=== Примеры вычислимых функций ===
 
* Нигде не определённая функция вычислима.
 
* Нигде не определённая функция вычислима.
  p(x)
+
  <tex>p(x):</tex>
   '''return''' <tex>\bot</tex>
+
   '''while True'''
 
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
 
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
  p(x)
+
  <tex>p(x):</tex>
 
   '''return''' <tex>x^2</tex>
 
   '''return''' <tex>x^2</tex>
  
 
== Свойства вычислимой функции ==
 
== Свойства вычислимой функции ==
{{Утверждение
+
{{Лемма
|statement = <tex>f</tex> вычислимая функция. Тогда <tex>D(f)</tex> — [[Перечислимые_языки|перечислимое]] множество, где <tex>D(f)</tex> — область определения функции <tex>f</tex>.
+
|id = lemma-
 +
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>D(f)</tex> {{---}} область определения функции <tex>f</tex>. Тогда <tex>D(f)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
 
Для доказательства достаточно написать полуразрешающую программу.
 
Для доказательства достаточно написать полуразрешающую программу.
  p(x)
+
  <tex>p(x):</tex>
   f(x)
+
   <tex>f(x)</tex>
 
   '''return''' 1
 
   '''return''' 1
Если функция <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>.
 
}}
 
}}
{{Утверждение
+
{{Лемма
|statement = <tex>f</tex> вычислимая функция. Тогда <tex>E(f)</tex> — перечислимое множество, где <tex>E(f)</tex> — область изменения функции <tex>f</tex>;
+
|id = lemma-
 +
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>E(f)</tex> {{---}} область значений <tex>f</tex>. Тогда <tex>E(f)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
 
Для доказательства достаточно написать полуразрешающую программу.
 
Для доказательства достаточно написать полуразрешающую программу.
  p(x)
+
  <tex>p(x):</tex>
 
   '''for''' <tex>y \in D(f)</tex>
 
   '''for''' <tex>y \in D(f)</tex>
     '''if''' x == f(y)
+
     '''if''' <tex>x == f(y)</tex>
    '''then return''' 1
+
      '''return''' 1
 
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
 
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
 
}}
 
}}
{{Утверждение
+
{{Лемма
|statement = <tex>f</tex> вычислимая функция. <tex>f(X)</tex> перечислимое множество, где <tex>X</tex> — перечислимое множество.
+
|id = lemma-
 +
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f(X)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
 
Для доказательства достаточно написать полуразрешающую программу.
 
Для доказательства достаточно написать полуразрешающую программу.
  p(x)
+
  <tex>p(x):</tex>
 
   '''for''' <tex>y \in D(f) \cap X</tex>
 
   '''for''' <tex>y \in D(f) \cap X</tex>
     '''if''' x == f(y)
+
     '''if''' <tex>x == f(y)</tex>
       '''then return''' 1
+
       '''return''' 1
Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слов, то она возвращает 1.
+
Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1.
 
}}
 
}}
{{Утверждение
+
{{Лемма
|statement = <tex>f</tex> вычислимая функция. <tex>f^{-1}(X)</tex> перечислимое множество, где <tex>X</tex> — [[Разрешимые_(рекурсивные)_языки|разрешимое множество]].
+
|id = lemma-
 +
|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f^{-1}(X)</tex> является перечислимым множеством.
 
|proof =  
 
|proof =  
 
Для доказательства достаточно написать полуразрешающую программу.
 
Для доказательства достаточно написать полуразрешающую программу.
 +
<tex>p(x):</tex>
 +
  '''if''' <tex>f(x) \in X</tex>
 +
    '''return''' 1
 +
На проверке условия <tex>f(x) \in X</tex> программа может зависнут, если <tex>f(x)</tex> не определено или <tex>f(x) \notin X</tex>. Если <tex>f(x)</tex> не определено, то <tex>x \notin f^{-1}(X)</tex>. Условие <tex>f(x) \notin X</tex> можно проверить, так как <tex>X</tex> перечислимо.
 +
}}
 +
 +
== Характеристика перечислимых множеств через вычислимые функции ==
 +
{{Определение
 +
|definition='''Множество <tex>X</tex> называется перечислимым''' (англ. ''computably enumerable set''), если выполняется хотя бы одно из условий:
 +
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке;
 +
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>;
 +
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>;
 +
# функция <tex>f_X(x) = \begin{cases}
 +
  1, & x \in X \\
 +
  \bot, & x \notin X
 +
\end{cases}</tex> — вычислима.
 +
}}
 +
 +
{{Теорема
 +
|statement=
 +
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
 +
|proof=
 +
*<tex>1 \Rightarrow 4</tex>
 +
 +
Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.
 +
 +
Приведём программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x)</tex>:
 +
 +
<tex>q(x):</tex>
 +
    '''for''' <tex>k = 1 \ .. \ \infty</tex>
 +
        '''if''' <tex> p(k) == x </tex>
 +
            '''return''' 1
 +
 +
 +
*<tex>2 \Rightarrow 1</tex>
 +
 +
Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
 +
 +
Тогда <tex>X</tex> перечисляется такой программой:
 +
 +
<tex>q():</tex>
 +
    '''for''' <tex> TL = 1 \ .. \ \infty </tex>
 +
        '''for''' <tex> k = 1 \ ..\ TL</tex>
 +
            '''if''' <tex>p(k)|_{TL} \neq \bot </tex>
 +
                '''print''' <tex>k</tex>
 +
 +
*<tex>3 \Rightarrow 1</tex>
 +
 +
Пусть <tex>X</tex> — область значений вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
 +
 +
Тогда <tex>X</tex> перечисляется такой программой:
 +
 +
<tex>q():</tex>
 +
    '''for''' <tex> TL = 1 \ .. \ \infty </tex>
 +
        '''for''' <tex> k = 1 \ ..\ TL</tex>
 +
            '''if''' <tex>p(k)|_{TL} \neq \bot </tex>
 +
                '''print''' <tex>p(k)|_{TL}</tex>
 +
 +
 +
*<tex>4 \Rightarrow 2</tex>, <tex>4 \Rightarrow 3</tex>
 +
 +
Пусть дана <tex>f_X(x)</tex>.
 +
 +
Введём новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.
 +
 +
Очевидно, что она вычислима и что её область определения и область значений совпадают с <tex>X</tex>.
 +
 
}}
 
}}
{{Утверждение
+
 
|statement = <tex>f</tex> вычислимая функция. <tex>f^{-1}(X)</tex> — перечислимое множество, где <tex>X</tex> — перечислимое множество.
+
== Теорема об униформизации ==
 +
{{Теорема
 +
|statement = Пусть <tex>F</tex> {{---}} перечислимое множество пар натуральных чисел. Тогда существует вычислимая функция <tex>f</tex>, определённая на тех и только тех <tex>x</tex>, для которых найдется <tex>y</tex>, при котором <tex>\langle x, y \rangle \in F</tex>, причём значение <tex>f(x)</tex> является одним из таких <tex>y</tex>.
 
|proof =  
 
|proof =  
Для доказательства достаточно написать полуразрешающую программу.
+
Напишем программу, вычисляющую функцию <tex>f</tex>.
 +
<tex>f(x):</tex>
 +
  '''for''' <tex>\langle a, b \rangle \in F</tex>
 +
    '''if''' <tex>x == a</tex>
 +
      '''return''' <tex>b</tex>
 +
Так как множество <tex>F</tex> перечислимо, то его элементы можно перебрать.
 +
}}
 +
 
 +
== Теорема о псевдообратной функции ==
 +
{{Теорема
 +
|statement = Для любой вычислимой функции <tex>f</tex> существует вычислимая функция <tex>g</tex>, являющаяся псевдообратной в следующем смысле: <tex>E(f) = D(g)</tex>, и при этом <tex>f(g(f(x))) = f(x)</tex> для всех <tex>x</tex>, при которых <tex>f(x)</tex> определена.
 +
|proof =
 +
Напишем программу, вычисляющую функцию <tex>g</tex>.
 +
<tex>g(n):</tex>
 +
  '''for''' <tex>x \in D(f)</tex>
 +
    '''if''' <tex>f(x) == n</tex>
 +
      '''return''' <tex>x</tex>
 +
Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения.
 
}}
 
}}
  
== Литература ==
+
== См. также ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
+
 
 +
* [[Рекурсивные функции]]
 +
* [[Вычислимые числа]]
 +
* [[Универсальная функция]]
 +
 
 +
== Источники информации ==
 +
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 134, с. 176. ISBN 5-900916-36-7
 +
* [http://en.wikipedia.org/wiki/Computable_function Wikipedia — Computable function]
 +
* [http://en.wikipedia.org/wiki/Recursively_enumerable_set Wikipedia — Computably enumerable set]
 +
* [http://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Википедия — Вычислимая функция]
 +
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE Википедия — Перечислимое множество]
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Разрешимые и перечислимые языки]]

Текущая версия на 19:43, 4 сентября 2022

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

Определение:
Функция [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), если выполняется хотя бы одно из условий:
  1. существует программа, перечисляющая все элементы [math]X[/math] в произвольном порядке;
  2. [math]X[/math] является областью определения вычиcлимой функции [math]f[/math];
  3. [math]X[/math] является областью значений вычиcлимой функции [math]f[/math];
  4. функция [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]

См. также

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