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