205
правок
Изменения
Нет описания правки
}}
== Теорема об униформизации ==
{{Теорема
|statement = Пусть <tex>F</tex> — перечислимое множество пар натуральных чисел. Тогда существует вычислимая функция <tex>f</tex>, определенная на тех и только тех <tex>x</tex>, для которых найдется <tex>y</tex>, при котором <tex>\langle x, y \rangle \in F</tex>, причем значение <tex>f(x)</tex> является одним из таких <tex>y</tex>.
|proof =
Напишем программу, вычисляющую функцию <tex>f</tex>.
f(x)
'''for''' <tex>\langle a, b \rangle \in F</tex>
'''if''' x == a
'''then return''' b
Так как множество <tex>F</tex> перечислимо, то его элементы можно перебрать.
}}
== Теорема о псевдообратной функции ==
{{Теорема
|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 =
}}
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
