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

Определение:

Множество [math]X[/math] называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже: существует программа, перечисляющая все элементы [math]X[/math] в произвольном порядке. [math]X[/math] является областью определения вычиcлимой функции [math]f[/math]. [math]X[/math] является областью значений вычиcлимой функции [math]f[/math]. Функция [math]f_X(x) = \begin{cases} 1, & x \in X \\ \bot, & x \notin X \end{cases}[/math] — вычислима.

Теорема:

Определения 1, 2, 3, 4 эквивалентны.

Доказательство:

[math]\triangleright[/math]

1 [math]\Rightarrow[/math] 4 Пусть [math]p[/math] — программа, перечисляющая [math]X[/math]. Приведем программу [math]q[/math], вычисляющую функцию [math]f_X(x):[/math] [math]q(x)[/math] for [math]k = 1 \ .. \ \infty[/math] if [math] p(k) == x [/math] return 1 2 [math]\Rightarrow[/math] 1, 3 [math]\Rightarrow[/math] 1 Пусть [math]X[/math] — область определения вычислимой функции [math]f[/math], вычисляемой программой [math]p[/math]. Введем обозначение: [math]p(x)|_{TL}[/math] — программа [math]p(x)[/math], запускаемая на [math]TL[/math] секунд. Если [math]p(x)|_{TL}[/math] за [math]TL[/math] секунд так и не вернула значение, то считаем, что это значение равно [math]\bot[/math]. Тогда [math]X[/math] перечисляется такой программой: [math]q()[/math] for [math] TL = 1 \ .. \ \infty [/math] for [math] k = 1 \ ..\ TL[/math] if [math]p(k)|_{TL} \neq \bot [/math] print[math](k)[/math] Если print[math](k)[/math] заменить на print([math]p(k)|_{TL}[/math]), то [math]q[/math] станет перечислять область значений [math]f(x)[/math]. 4 [math]\Rightarrow[/math] 2, 4 [math]\Rightarrow[/math] 3 Пусть дана [math]f_X(x)[/math]. Введем новую функцию [math]g(x) = x[/math], если [math]f_X(x) \neq \bot[/math]. Очевидно, она вычислима, и ее область определения и область значений совпадают с [math]X[/math].

[math]\triangleleft[/math]

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999