205
правок
Изменения
Нет описания правки
'''return''' <tex>x^2</tex>
== Свойства вычислимой функции ==
{{Утверждение
|statement = <tex>f</tex> — вычислимая функция. Тогда <tex>D(f)</tex> — [[Перечислимые_языки|перечислимое]] множество, где <tex>D(f)</tex> — область определения функции <tex>f</tex>.
|proof =
p(x)
f(x)
'''return''' 1
Если функция <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>E(f)</tex> — область изменения функции <tex>f</tex>;
|proof =
p(x)
'''for''' <tex>y \in D(f)</tex>
'''if''' x == f(y)
'''then return''' 1
Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
}}
{{Утверждение
|statement = <tex>f</tex> — вычислимая функция. <tex>f(X)</tex> — перечислимое множество, где <tex>X</tex> — перечислимое множество.
|proof =
p(x)
'''for''' <tex>y \in D(f) \cap X</tex>
'''if''' x == f(y)
'''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 =
}}
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
