205
правок
Изменения
м
→Свойства вычислимой функции
|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>.
|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.
}}
{{Утверждение
|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.
}}
{{Утверждение
|statement = <tex>f</tex> — вычислимая функция. , <tex>f^{-1}(X)</tex> — перечислимое множество, где <tex>X</tex> — [[Разрешимые_(рекурсивные)_языки|разрешимое множество]].|proof = Для доказательства достаточно написать полуразрешающую программу.}}{{Утверждение|statement = <tex>f</tex> — вычислимая функция. <tex>f^{-1}(X)</tex> — перечислимое множество, где <tex>X</tex> — перечислимое множество.
|proof =
Для доказательства достаточно написать полуразрешающую программу.
