36
правок
Изменения
Нет описания правки
== Основные определения ==
{{Определение
|definition = (1) Функция <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>.
}}
{{Определение
|definition = (2) Функция <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 = Определения (1) и (2) Приведенные определения эквивалентны.|proof = <tex>1 \Rightarrow 2</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> '''then return''' 1Так как [[Вычислимые функции#D(f)Свойства вычислимой функции|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/><tex>2 \Rightarrow 1Leftarrow</tex><br/>
Напишем программу, вычисляющую функцию <tex>f</tex>.
<tex>f(n):</tex>
'''for''' <tex>\langle x, y \rangle \in F</tex>
'''if''' <tex>x == n</tex>
}}
=== Замечание ===
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и многое другое. Поэтому аналогичным образом можно определить понятие вычислимой функции для счётных множеств.
=== Примеры вычислимых функций ===
* Нигде не определённая функция вычислима.
<tex>p(x):</tex> '''returnwhile True''' <tex>\bot</tex>
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
<tex>p(x):</tex>
'''return''' <tex>x^2</tex>
== Свойства вычислимой функции ==
{{УтверждениеЛемма|id = D(f)lemma-|statement = <tex>f</tex> — {{---}} вычислимая функция. Тогда , <tex>D(f)</tex> — перечислимое множество, где {{---}} область определения функции <tex>D(f)</tex> — область определения функции . Тогда <tex>D(f)</tex>является перечислимым множеством.
|proof =
Для доказательства достаточно написать полуразрешающую программу.
<tex>p(x):</tex> <tex>f(x)</tex>
'''return''' 1
Если функция <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>E(f)</tex> — область изменения функции . Тогда <tex>E(f)</tex>;является перечислимым множеством.
|proof =
Для доказательства достаточно написать полуразрешающую программу.
<tex>p(x):</tex>
'''for''' <tex>y \in D(f)</tex>
'''if''' <tex>x == f(y)</tex> '''then return''' 1
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
}}
{{УтверждениеЛемма|id = lemma-|statement = <tex>f</tex> — {{---}} вычислимая функция. , <tex>f(X)</tex> — {{---}} перечислимое множество, где . Тогда <tex>f(X)</tex> — перечислимое множествоявляется перечислимым множеством.
|proof =
Для доказательства достаточно написать полуразрешающую программу.
<tex>p(x):</tex>
'''for''' <tex>y \in D(f) \cap X</tex>
'''if''' <tex>x == f(y)</tex> '''then return''' 1Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит словслово, то она возвращает 1.
}}
{{УтверждениеЛемма|id = lemma-|statement = <tex>f</tex> — {{---}} вычислимая функция. , <tex>f^{-1}(X)</tex> — {{---}} перечислимое множество, где . Тогда <tex>f^{-1}(X)</tex> — [[Разрешимые_(рекурсивные)_языки|разрешимое множество]]является перечислимым множеством.
|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>fp</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)|proof _{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</tex>, определенная определённая на тех и только тех <tex>x</tex>, для которых найдется <tex>y</tex>, при котором <tex>\langle x, y \rangle \in F</tex>, причем причём значение <tex>f(x)</tex> является одним из таких <tex>y</tex>.
|proof =
Напишем программу, вычисляющую функцию <tex>f</tex>.
<tex>f(x):</tex>
'''for''' <tex>\langle a, b \rangle \in F</tex>
'''if''' <tex>x == a</tex> '''then return''' <tex>b</tex>
Так как множество <tex>F</tex> перечислимо, то его элементы можно перебрать.
}}
|proof =
Напишем программу, вычисляющую функцию <tex>g</tex>.
<tex>g(n):</tex>
'''for''' <tex>x \in D(f)</tex>
'''if''' <tex>f(x) == n</tex> '''then return''' <tex>x</tex>
Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения.
}}
== Литература См. также == * [[Рекурсивные функции]]* [[Вычислимые числа]]* [[Универсальная функция]] == Источники информации ==* ''Верещагин Н. К.Верещагин, А. Шень А.'' '''Лекции по математической логике и теории алгоритовалгоритмов. Часть 3. Вычислимые функции''' -- . — М.: МЦНМО, 1999 . с. 134, с. 176. ISBN 5- С900916-36-7* [http://en.wikipedia. 176org/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 Википедия — Перечислимое множество][[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Разрешимые и перечислимые языки]]
