205
правок
Изменения
→Теорема о псевдообратной функции
|statement = Для любой вычислимой функции <tex>f</tex> существует вычислимая функция <tex>g</tex>, являющаяся псевдообратной в следующем смысле: <tex>E(f) = D(g)</tex>, и при этом <tex>f(g(f(x))) = f(x)</tex> для всех <tex>x</tex>, при которых <tex>f(x)</tex> определена.
|proof =
Напишем программу, вычисляющую функцию <tex>g</tex>.
g(n)
'''for''' <tex>x \in D(f)</tex>
'''if''' f(x) == n
'''then return''' x
Так как область определения вычислимой функции перечислимо, то можно перебрать элементы области определения.
}}
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
