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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Множество [math]X[/math] называется перечислимым, если выполняется хотя бы 1 условие из приведенных ниже:
  1. Существует программа(алгоритм) печатающая(перечисляющая) все элементы [math]X[/math] в произвольном порядке
  2. [math]X[/math] является областью определения вычиcлимой функции [math]f[/math]
  3. [math]X[/math] является областью значений вычиcлимой функции [math]f[/math]
  4. Функция [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]