Изменения

== Свойства вычислимой функции ==

|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>D(f)</tex> {{---}} область определения функции <tex>f</tex>. Тогда <tex>D(f)</tex> является перечислимым множеством.

|proof =

Если функция <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>f</tex>. Тогда <tex>E(f)</tex> является перечислимым множеством.

|proof =

Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.

}}

|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f(X)</tex> является перечислимым множеством.

|proof =

Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1.

}}

|statement = <tex>f</tex> {{---}} вычислимая функция, <tex>X</tex> {{---}} перечислимое множество. Тогда <tex>f^{-1}(X)</tex> является перечислимым множеством.

|proof =