Изменения

Характеристика перечислимых множеств через вычислимые функции

Нет изменений в размере, 11:00, 25 декабря 2011

Нет описания правки

Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.

~~Приведем~~ Приведём программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x)</tex>:

Пусть дана <tex>f_X(x)</tex>.

~~Введем~~ Введём новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.

Очевидно, что она вычислима и что ее её область определения и область значений совпадают с <tex>X</tex>.

}}

271

правка