54
правки
Изменения
м
'''then return''' 1
Введем обозначение: <tex>p(x)|_{TL}</tex> — запустить <tex>p(x)</tex> на <tex>TL</tex> секунд. Если <tex>p(x)|_{TL}</tex> за <tex>TL</tex> секунд так и не вернула значение функции <tex>f(x)</tex>, то возвращаем <tex>\bot</tex>.
'''then print'''<tex>(k)</tex>
Нет описания правки
{{Определение
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
# Существует существует программа , перечисляющая все элементы <tex>X</tex> в произвольном порядке.
# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>.
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>. # Функция функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
Тогда <tex>X</tex> перечисляется такой программой:
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.
Пусть дана <tex>f_X(x)</tex>.
Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.
Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- — М.: МЦНМО, 1999
