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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Предварительная версия (пока что без трёх доказательств))
(нет различий)

Версия 23:54, 7 января 2012

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

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


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

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


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

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

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

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

Приведём программу, выдающую 1, если [math]p \in A_{\Gamma}[/math]:

[math]q(p):[/math]
  for [math]k = 1..+\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]\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]\triangleleft[/math]


<продолжение доказательства теоремы>
[math]\triangleleft[/math]