Вычислимые функции — различия между версиями
м (→Свойства вычислимой функции) |
м (rollbackEdits.php mass rollback) |
||
(не показано 18 промежуточных версий 8 участников) | |||
Строка 1: | Строка 1: | ||
== Основные определения == | == Основные определения == | ||
{{Определение | {{Определение | ||
− | |definition = | + | |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>. | |
}} | }} | ||
+ | |||
{{Определение | {{Определение | ||
− | |definition = | + | |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 = | + | |statement = Приведенные определения эквивалентны. |
− | |proof = <tex> | + | |proof = <tex>\Rightarrow </tex><br/> |
Напишем полуразрешающую программу для множества <tex>F</tex>. | Напишем полуразрешающую программу для множества <tex>F</tex>. | ||
− | <tex>p(\langle x, y\rangle)</tex> | + | <tex>p(\langle x, y\rangle):</tex> |
'''for''' <tex>a \in D(f)</tex> | '''for''' <tex>a \in D(f)</tex> | ||
'''if''' <tex>a == x \land f(a) == y</tex> | '''if''' <tex>a == x \land f(a) == y</tex> | ||
'''return''' 1 | '''return''' 1 | ||
− | Так как [[# | + | Так как [[Вычислимые функции#Свойства вычислимой функции|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/> |
− | <tex> | + | <tex>\Leftarrow</tex><br/> |
Напишем программу, вычисляющую функцию <tex>f</tex>. | Напишем программу, вычисляющую функцию <tex>f</tex>. | ||
− | <tex>f(n)</tex> | + | <tex>f(n):</tex> |
'''for''' <tex>\langle x, y \rangle \in F</tex> | '''for''' <tex>\langle x, y \rangle \in F</tex> | ||
'''if''' <tex>x == n</tex> | '''if''' <tex>x == n</tex> | ||
'''return''' <tex>y</tex> | '''return''' <tex>y</tex> | ||
− | Так как <tex>F</tex> перечислимое множество, то можно перебрать элементы этого множества. | + | Так как <tex>F</tex> {{---}} перечислимое множество, то можно перебрать элементы этого множества. |
}} | }} | ||
=== Замечание === | === Замечание === | ||
− | Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и | + | Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и многое другое. Поэтому аналогичным образом можно определить понятие вычислимой функции для счётных множеств. |
=== Примеры вычислимых функций === | === Примеры вычислимых функций === | ||
* Нигде не определённая функция вычислима. | * Нигде не определённая функция вычислима. | ||
− | <tex>p(x)</tex> | + | <tex>p(x):</tex> |
− | ''' | + | '''while True''' |
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число. | * <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число. | ||
− | <tex>p(x)</tex> | + | <tex>p(x):</tex> |
'''return''' <tex>x^2</tex> | '''return''' <tex>x^2</tex> | ||
== Свойства вычислимой функции == | == Свойства вычислимой функции == | ||
− | {{ | + | {{Лемма |
− | |id = | + | |id = lemma- |
− | |statement = <tex>f</tex> | + | |statement = <tex>f</tex> {{---}} вычислимая функция, <tex>D(f)</tex> {{---}} область определения функции <tex>f</tex>. Тогда <tex>D(f)</tex> является перечислимым множеством. |
|proof = | |proof = | ||
Для доказательства достаточно написать полуразрешающую программу. | Для доказательства достаточно написать полуразрешающую программу. | ||
− | <tex>p(x)</tex> | + | <tex>p(x):</tex> |
<tex>f(x)</tex> | <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> | + | |id = lemma- |
+ | |statement = <tex>f</tex> {{---}} вычислимая функция, <tex>E(f)</tex> {{---}} область значений <tex>f</tex>. Тогда <tex>E(f)</tex> является перечислимым множеством. | ||
|proof = | |proof = | ||
Для доказательства достаточно написать полуразрешающую программу. | Для доказательства достаточно написать полуразрешающую программу. | ||
− | <tex>p(x)</tex> | + | <tex>p(x):</tex> |
'''for''' <tex>y \in D(f)</tex> | '''for''' <tex>y \in D(f)</tex> | ||
'''if''' <tex>x == f(y)</tex> | '''if''' <tex>x == f(y)</tex> | ||
Строка 59: | Строка 61: | ||
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1. | Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1. | ||
}} | }} | ||
− | {{ | + | {{Лемма |
− | |statement = <tex>f</tex> | + | |id = lemma- |
+ | |statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f(X)</tex> является перечислимым множеством. | ||
|proof = | |proof = | ||
Для доказательства достаточно написать полуразрешающую программу. | Для доказательства достаточно написать полуразрешающую программу. | ||
− | <tex>p(x)</tex> | + | <tex>p(x):</tex> |
'''for''' <tex>y \in D(f) \cap X</tex> | '''for''' <tex>y \in D(f) \cap X</tex> | ||
'''if''' <tex>x == f(y)</tex> | '''if''' <tex>x == f(y)</tex> | ||
Строка 69: | Строка 72: | ||
Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1. | Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1. | ||
}} | }} | ||
− | {{ | + | {{Лемма |
− | |statement = <tex>f</tex> | + | |id = lemma- |
+ | |statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f^{-1}(X)</tex> является перечислимым множеством. | ||
|proof = | |proof = | ||
Для доказательства достаточно написать полуразрешающую программу. | Для доказательства достаточно написать полуразрешающую программу. | ||
− | <tex>p(x)</tex> | + | <tex>p(x):</tex> |
'''if''' <tex>f(x) \in X</tex> | '''if''' <tex>f(x) \in X</tex> | ||
'''return''' 1 | '''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> перечислимо. | На проверке условия <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> | + | |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</tex>. | ||
− | <tex>f(x)</tex> | + | <tex>f(x):</tex> |
'''for''' <tex>\langle a, b \rangle \in F</tex> | '''for''' <tex>\langle a, b \rangle \in F</tex> | ||
'''if''' <tex>x == a</tex> | '''if''' <tex>x == a</tex> | ||
Строка 96: | Строка 163: | ||
|proof = | |proof = | ||
Напишем программу, вычисляющую функцию <tex>g</tex>. | Напишем программу, вычисляющую функцию <tex>g</tex>. | ||
− | <tex>g(n)</tex> | + | <tex>g(n):</tex> |
'''for''' <tex>x \in D(f)</tex> | '''for''' <tex>x \in D(f)</tex> | ||
'''if''' <tex>f(x) == n</tex> | '''if''' <tex>f(x) == n</tex> | ||
Строка 103: | Строка 170: | ||
}} | }} | ||
− | == | + | == См. также == |
− | * | + | |
+ | * [[Рекурсивные функции]] | ||
+ | * [[Вычислимые числа]] | ||
+ | * [[Универсальная функция]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 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
Основные определения
Определение: |
Функция
| называется вычислимой (англ. computable function), если существует программа, вычисляющая функцию , такая, что:
Определение: |
Функция перечислимым множеством пар натуральных чисел. | называется вычислимой, если её график определено и равно является
Теорема: |
Приведенные определения эквивалентны. |
Доказательство: |
for if return 1 Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1. Так как for if return — перечислимое множество, то можно перебрать элементы этого множества. |
Замечание
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и многое другое. Поэтому аналогичным образом можно определить понятие вычислимой функции для счётных множеств.
Примеры вычислимых функций
- Нигде не определённая функция вычислима.
while True
- , где — рациональное число.
return
Свойства вычислимой функции
Лемма: |
— вычислимая функция, — область определения функции . Тогда является перечислимым множеством. |
Доказательство: |
Для доказательства достаточно написать полуразрешающую программу. Если функция return 1 определена на входе , то . Тогда необходимо вернуть 1. Иначе программа зависнет при вызове . |
Лемма: |
— вычислимая функция, — область значений . Тогда является перечислимым множеством. |
Доказательство: |
Для доказательства достаточно написать полуразрешающую программу. Так как for if return 1 перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1. |
Лемма: |
— вычислимая функция, — перечислимое множество. Тогда является перечислимым множеством. |
Доказательство: |
Для доказательства достаточно написать полуразрешающую программу. Из for if return 1 замкнутости перечислимых языков относительно операции пересечения следует, что элементы множества можно перебрать. Если программа находит слово, то она возвращает 1. |
Лемма: |
— вычислимая функция, — перечислимое множество. Тогда является перечислимым множеством. |
Доказательство: |
Для доказательства достаточно написать полуразрешающую программу. На проверке условия if return 1 программа может зависнут, если не определено или . Если не определено, то . Условие можно проверить, так как перечислимо. |
Характеристика перечислимых множеств через вычислимые функции
Определение: |
Множество
| называется перечислимым (англ. computably enumerable set), если выполняется хотя бы одно из условий:
Теорема: |
Определения 1, 2, 3, 4 эквивалентны. |
Доказательство: |
Пусть — программа, перечисляющая .Приведём программу , вычисляющую функцию :for if return 1
Пусть — область определения вычислимой функции , вычисляемой программой .Тогда перечисляется такой программой:for for if print Пусть — область значений вычислимой функции , вычисляемой программой .Тогда перечисляется такой программой:for for if print
Пусть дана .Введём новую функцию Очевидно, что она вычислима и что её область определения и область значений совпадают с , если . . |
Теорема об униформизации
Теорема: |
Пусть — перечислимое множество пар натуральных чисел. Тогда существует вычислимая функция , определённая на тех и только тех , для которых найдется , при котором , причём значение является одним из таких . |
Доказательство: |
Напишем программу, вычисляющую функцию .Так как множество for if return перечислимо, то его элементы можно перебрать. |
Теорема о псевдообратной функции
Теорема: |
Для любой вычислимой функции существует вычислимая функция , являющаяся псевдообратной в следующем смысле: , и при этом для всех , при которых определена. |
Доказательство: |
Напишем программу, вычисляющую функцию .Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения. for if return |
См. также
Источники информации
- Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 134, с. 176. ISBN 5-900916-36-7
- Wikipedia — Computable function
- Wikipedia — Computably enumerable set
- Википедия — Вычислимая функция
- Википедия — Перечислимое множество