Материал из Викиконспекты
Определение
| Определение: |
Множество [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.
Пусть [math]X[/math] — область определения вычислимой функции [math]f[/math], вычисляемой программой [math]p[/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]
- 3 [math]\Rightarrow[/math] 1.
Пусть [math]X[/math] — область значений вычислимой функции [math]f[/math], вычисляемой программой [math]p[/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]p(k)|_{TL}[/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. С. 134. ISBN 5-900916-36-7
