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

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

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

Теорема:

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

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

[math]\triangleright[/math]

1 [math]\Rightarrow[/math] 4 Пусть [math]A[/math] - программа перечисляющая [math]X[/math]. Приведем программу [math]B[/math], вычисляющую [math]p_X(i):[/math] [math]B(i)[/math] for (n = 1 ... [math]+\infty[/math]) if (A(n) == i) return 0 2 [math]\Rightarrow[/math] 1, 3 [math]\Rightarrow[/math] 1 Пусть [math]X[/math] область определения вычислимой функции [math]f[/math], вычисляемой программой [math]B[/math]. Введем обозначение: [math]B(i)|_{TL}[/math]   [math]-[/math]   запустить   [math]B(i)[/math]   на   [math]TL[/math]   секунд. Если   [math]B(i)|_{TL}[/math]   за   [math]TL[/math]   секунд так и не вернула значение функции [math]f(i)[/math], то возвращаем -1. Тогда [math]X[/math] перечисляется такой программой [math]A:[/math] [math]A()[/math] for ([math]TL[/math] = 1 ... [math]+\infty[/math]) for (n = 1 ... [math]TL[/math]) if ([math]B(n)|_{TL}[/math] != -1) print(n) Если print(n) заменить на print([math]B(n)|_{TL}[/math]), то [math]A()[/math] станет перечислять область значений [math]f[/math]. 4 [math]\Rightarrow[/math] 2, 4 [math]\Rightarrow[/math] 3 Пусть дана [math]p_X(i).[/math] Введем новую функцию: [math]l(n) = n,[/math] если [math]p_X(n).[/math] Очевидно, она вычислима, и ее область определения и область значений совпадают с [math]X.[/math] ч.т.д.

[math]\triangleleft[/math]

Литература

• Н.К.Верещагин, А.Шень "Вычислимые функции"