Материал из Викиконспекты
| Определение: |
Множество [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}
1 & 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 1
- 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] |
