Теорема Райса-Шапиро — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Райса-Шапиро)
(Теорема Райса-Шапиро)
Строка 81: Строка 81:
 
Пусть <tex>p(x)=V(n, x)</tex>.<br>
 
Пусть <tex>p(x)=V(n, x)</tex>.<br>
 
Назовем (1) проверку на принадлежность <tex> n </tex> множеству <tex> K </tex>(просто перечисляя это множества), а (2) проверку на принадлежность <tex> p </tex> множеству <tex> A </tex>.  
 
Назовем (1) проверку на принадлежность <tex> n </tex> множеству <tex> K </tex>(просто перечисляя это множества), а (2) проверку на принадлежность <tex> p </tex> множеству <tex> A </tex>.  
Тогда программа, которая параллельно запускает проверку (1) и (2), является разрешающей программой для множества <tex>K</tex>, так как:
+
Тогда программа, которая параллельно запускает проверки (1) и (2), является разрешающей программой для множества <tex>K</tex>, так как:
 
* если <tex>n \in K</tex>, то проверка (1) завершится, а проверка (2) зависнет (<tex>p</tex> ведёт себя как <tex>h</tex>, которая не содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1;
 
* если <tex>n \in K</tex>, то проверка (1) завершится, а проверка (2) зависнет (<tex>p</tex> ведёт себя как <tex>h</tex>, которая не содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1;
 
* если <tex>n \notin K</tex>, то проверка (1) зависнет, а проверка (2) завершится (<tex>p</tex> ведёт себя как <tex>g</tex>, которая содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0.
 
* если <tex>n \notin K</tex>, то проверка (1) зависнет, а проверка (2) завершится (<tex>p</tex> ведёт себя как <tex>g</tex>, которая содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0.
Строка 107: Строка 107:
 
Назовем (1) проверку на принадлежность <tex> n </tex> множеству <tex> K </tex>(просто перечисляя это множества), а (2) проверку на принадлежность <tex> V(n, x) </tex> множеству <tex> A </tex>.
 
Назовем (1) проверку на принадлежность <tex> n </tex> множеству <tex> K </tex>(просто перечисляя это множества), а (2) проверку на принадлежность <tex> V(n, x) </tex> множеству <tex> A </tex>.
  
Тогда программа, которая параллельно запускает проверку (1) и (2), является разрешающей программой для множества <tex>K</tex>, так как:
+
Тогда программа, которая параллельно запускает проверки (1) и (2), является разрешающей программой для множества <tex>K</tex>, так как:
 
* если <tex>n \notin K</tex>, то <tex>V(n, x) \equiv g(x)</tex> для <tex>\forall n</tex>, поэтому проверка (2) завершится. Проверка (1) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0;
 
* если <tex>n \notin K</tex>, то <tex>V(n, x) \equiv g(x)</tex> для <tex>\forall n</tex>, поэтому проверка (2) завершится. Проверка (1) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0;
 
* если <tex>n \in K</tex>, то завершится проверка (1). Также, в этом случае <tex>|Dom(V(n, x))| < +\infty</tex>, так как <tex>V(n, x) = g(x)</tex> при <tex>x = 0\ldots t-1</tex> для какого-то <tex>t</tex>. <tex>g</tex> является продолжением <tex>V(n, x)</tex>. По предположению от противного <tex>V(n, x) \notin A</tex> <tex>\Rightarrow</tex> проверка (2) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1.
 
* если <tex>n \in K</tex>, то завершится проверка (1). Также, в этом случае <tex>|Dom(V(n, x))| < +\infty</tex>, так как <tex>V(n, x) = g(x)</tex> при <tex>x = 0\ldots t-1</tex> для какого-то <tex>t</tex>. <tex>g</tex> является продолжением <tex>V(n, x)</tex>. По предположению от противного <tex>V(n, x) \notin A</tex> <tex>\Rightarrow</tex> проверка (2) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1.

Версия 05:13, 24 января 2012

Определение образца

Определение:
Пусть [math]\gamma=\{\langle x_1,y_1\rangle,\langle x_2,y_2\rangle,\ldots ,\langle x_n,y_n\rangle\}[/math].
Тогда [math]\gamma[/math] называется образцом.


Свойство образца

Определение:
Пусть [math]A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge \ldots \wedge p(x_n)=y_n\}[/math], где [math]\langle x_i, y_i\rangle \in \gamma[/math].
Тогда [math]A_{\gamma}[/math] называется свойством образца [math]\gamma[/math].


Лемма о перечислимости свойства образца

Лемма:
Свойство [math]A_{\gamma}[/math] перечислимо для любого образца [math]\gamma[/math].
Доказательство:
[math]\triangleright[/math]

Построим полуразрешитель [math]A_{\gamma}[/math]:

[math]q(p):[/math]
  for [math]\langle x_i, y_i\rangle \in \gamma[/math]
      if [math]p(x_i) \not= y_i[/math]
          while True
  return 1
Полуразрешителя достаточно для доказательства перечислимости.
[math]\triangleleft[/math]


Лемма о перечислимости свойства перечислимого множества образцов

Лемма:
Пусть [math]\Gamma[/math] — перечислимое множество образцов, [math]A_{\Gamma} = \bigcup\limits_{\gamma \in \Gamma}{A_{\gamma}}[/math]. Тогда [math]A_{\Gamma}[/math] является перечислимым.
Доказательство:
[math]\triangleright[/math]

Построим полуразрешитель [math]A_{\Gamma}[/math]:

[math]q(p):[/math]
  for [math]k = 1\ldots +\infty[/math]
      for [math]\gamma \in \Gamma[1..k][/math]
          if [math](p \in A_{\gamma})|_{TL(k)}[/math]
              return 1
Полуразрешителя достаточно для доказательства перечислимости.
[math]\triangleleft[/math]

Теорема Райса-Шапиро

Теорема:
Свойство функций [math]A[/math] перечислимо тогда и только тогда, когда [math]\exists \Gamma: A = A_{\Gamma}[/math], где [math]\Gamma[/math] — перечислимое множество образцов.
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Очевидно (перебор по TL).


[math]\Rightarrow[/math]

Здесь нам потребуются две вспомогательные леммы.

Лемма:
Пусть [math]A[/math] — перечислимое свойство функций, [math]g \in A[/math], [math]h[/math] — продолжение [math]g[/math]. Тогда [math]h \in A[/math].
Доказательство:
[math]\triangleright[/math]

Докажем от противного. Пусть [math]g \in A[/math], [math]h[/math] — продолжение [math]g[/math], [math]h \notin A[/math].

Рассмотрим перечислимое и неразрешимое множество [math]K[/math] и следующую программу:

[math]V(n, x) = \begin{cases} h(x)\text{, if $n \in K$;}\\ g(x)\text{, else.} \end{cases}[/math]

[math]V[/math] — вычислимая (можно параллельно запустить [math]g(x)[/math] и проверку, принадлежит ли [math]n[/math] множеству [math]K[/math] (просто перечисляя это множество); если [math]g(x)[/math] успешно выполнится, то вернуть её результат).

Пусть [math]p(x)=V(n, x)[/math].
Назовем (1) проверку на принадлежность [math] n [/math] множеству [math] K [/math](просто перечисляя это множества), а (2) проверку на принадлежность [math] p [/math] множеству [math] A [/math]. Тогда программа, которая параллельно запускает проверки (1) и (2), является разрешающей программой для множества [math]K[/math], так как:

  • если [math]n \in K[/math], то проверка (1) завершится, а проверка (2) зависнет ([math]p[/math] ведёт себя как [math]h[/math], которая не содержится в [math]A[/math]); пусть в этом случае разрешающая программа для [math]K[/math] возвращает 1;
  • если [math]n \notin K[/math], то проверка (1) зависнет, а проверка (2) завершится ([math]p[/math] ведёт себя как [math]g[/math], которая содержится в [math]A[/math]); пусть в этом случае разрешающая программа для [math]K[/math] возвращает 0.
Получили противоречие, так как брали [math]K[/math] неразрешимым .
[math]\triangleleft[/math]


Лемма:
Если [math]A[/math] — перечислимое свойство функций, [math]g \in A[/math], то [math]\exists h[/math] такое, что [math]|Dom(h)| \lt +\infty[/math], [math]g[/math] — продолжение [math]h[/math], [math]h \in A[/math].
Доказательство:
[math]\triangleright[/math]

Докажем от противного. Пусть [math]\not\exists h[/math], которое удовлетворяет условию леммы.

Рассмотрим перечислимое и неразрешимое множество [math]K[/math] и следующую программу:

[math]V(n, x) = \begin{cases} g(x)\text{, if (0);}\\ \perp\text{, else;} \end{cases}[/math]

где условие [math](0)[/math] следующее: через [math]x[/math] шагов перечисления [math]K[/math] число [math]n[/math] не появилось.
Назовем (1) проверку на принадлежность [math] n [/math] множеству [math] K [/math](просто перечисляя это множества), а (2) проверку на принадлежность [math] V(n, x) [/math] множеству [math] A [/math].

Тогда программа, которая параллельно запускает проверки (1) и (2), является разрешающей программой для множества [math]K[/math], так как:

  • если [math]n \notin K[/math], то [math]V(n, x) \equiv g(x)[/math] для [math]\forall n[/math], поэтому проверка (2) завершится. Проверка (1) зависнет. Пусть в этом случае разрешающая программа для [math]K[/math] возвращает 0;
  • если [math]n \in K[/math], то завершится проверка (1). Также, в этом случае [math]|Dom(V(n, x))| \lt +\infty[/math], так как [math]V(n, x) = g(x)[/math] при [math]x = 0\ldots t-1[/math] для какого-то [math]t[/math]. [math]g[/math] является продолжением [math]V(n, x)[/math]. По предположению от противного [math]V(n, x) \notin A[/math] [math]\Rightarrow[/math] проверка (2) зависнет. Пусть в этом случае разрешающая программа для [math]K[/math] возвращает 1.
Противоречие, так как брали неразрешимое [math]K[/math].
[math]\triangleleft[/math]


Вернёмся к доказательству теоремы.

Функции с конечной областью определения записываются так:

[math]f(x):[/math]
    if [math]x = x_1[/math]
        return [math]y_1[/math]
    [math]\cdots[/math]
    if [math]x = x_n[/math]
        return [math]y_n[/math]
    [math]\perp[/math]

Такие функции перечислимы. Значит, такие функции, удоволетворяющие [math]A[/math], тоже перечислимы.

[math]A_{\Gamma} \subseteq A[/math] по первой вспомогательной лемме.

[math]A \subseteq A_{\Gamma}[/math] по второй вспомогательной лемме.

Значит, [math]A = A_{\Gamma}[/math].
[math]\triangleleft[/math]