141
правка
Изменения
Предварительная версия (пока что без трёх доказательств)
== Определение образца ==
{{Определение
|definition=
Пусть <tex>\gamma=\{<x_1,y_1>,<x_2,y_2>,...,<x_n,y_n>\}</tex>.
Тогда <tex>\gamma</tex> называется образцом.
}}
== Свойство образца ==
{{Определение
|definition=
Пусть <tex>A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge ... \wedge p(x_n)=y_n\}</tex>.
Тогда <tex>A_{\gamma}</tex> называется свойством образца <tex>\gamma</tex>.
}}
== Лемма о перечислимости свойства образца ==
{{Лемма
|statement =
Свойство <tex>A_{\gamma}</tex> перечислимо для любого образца <tex>\gamma</tex>.
|proof =
Очевидно.
}}
== Лемма о перечеслимости свойства перечислимого множества образцов ==
{{Лемма
|statement =
Пусть <tex>\Gamma</tex> - перечислимое множество образцов, <tex>A_{\Gamma} = \bigcup\limits_{\gamma \in \Gamma}{A_{\gamma}}</tex>.
Тогда <tex>A_{\Gamma}</tex> - перечислимо.
|proof =
Приведём программу, выдающую 1, если <tex>p \in A_{\Gamma}</tex>:
<tex>q(p):</tex>
for <tex>k = 1..+\infty</tex>
for <tex>\gamma \in \Gamma[1..k]</tex>
if <tex>(p \in A_{\gamma})|_{TL(k)}</tex>
return 1
Этого достаточно для доказательства перечислимости.
}}
== Теорема Райса-Шапиро ==
{{Теорема
|statement =
Свойство функций <tex>A</tex> перечислимо тогда и только тогда, когда <tex>\exists \Gamma: A = A_{\Gamma}</tex>, где <tex>\Gamma</tex> - перечислимое множество образцов.
|proof =
<tex>\Leftarrow</tex>
:Очевидно (перебор по TL).
<tex>\Rightarrow</tex>
:Здесь нам потребуются две вспомогательные леммы.
:{{Лемма
|statement =
Пусть <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, <tex>h</tex> - продолжение <tex>g</tex>.
Тогда <tex>h \in A</tex>.
|proof =
<доказательство>
}}
{{Лемма
|statement =
Если <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists h</tex>, такое что <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> - продолжение <tex>h</tex>, <tex>h \in A</tex>.
|proof =
<доказательство>
}}
<продолжение доказательства теоремы>
}}
{{Определение
|definition=
Пусть <tex>\gamma=\{<x_1,y_1>,<x_2,y_2>,...,<x_n,y_n>\}</tex>.
Тогда <tex>\gamma</tex> называется образцом.
}}
== Свойство образца ==
{{Определение
|definition=
Пусть <tex>A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge ... \wedge p(x_n)=y_n\}</tex>.
Тогда <tex>A_{\gamma}</tex> называется свойством образца <tex>\gamma</tex>.
}}
== Лемма о перечислимости свойства образца ==
{{Лемма
|statement =
Свойство <tex>A_{\gamma}</tex> перечислимо для любого образца <tex>\gamma</tex>.
|proof =
Очевидно.
}}
== Лемма о перечеслимости свойства перечислимого множества образцов ==
{{Лемма
|statement =
Пусть <tex>\Gamma</tex> - перечислимое множество образцов, <tex>A_{\Gamma} = \bigcup\limits_{\gamma \in \Gamma}{A_{\gamma}}</tex>.
Тогда <tex>A_{\Gamma}</tex> - перечислимо.
|proof =
Приведём программу, выдающую 1, если <tex>p \in A_{\Gamma}</tex>:
<tex>q(p):</tex>
for <tex>k = 1..+\infty</tex>
for <tex>\gamma \in \Gamma[1..k]</tex>
if <tex>(p \in A_{\gamma})|_{TL(k)}</tex>
return 1
Этого достаточно для доказательства перечислимости.
}}
== Теорема Райса-Шапиро ==
{{Теорема
|statement =
Свойство функций <tex>A</tex> перечислимо тогда и только тогда, когда <tex>\exists \Gamma: A = A_{\Gamma}</tex>, где <tex>\Gamma</tex> - перечислимое множество образцов.
|proof =
<tex>\Leftarrow</tex>
:Очевидно (перебор по TL).
<tex>\Rightarrow</tex>
:Здесь нам потребуются две вспомогательные леммы.
:{{Лемма
|statement =
Пусть <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, <tex>h</tex> - продолжение <tex>g</tex>.
Тогда <tex>h \in A</tex>.
|proof =
<доказательство>
}}
{{Лемма
|statement =
Если <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists h</tex>, такое что <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> - продолжение <tex>h</tex>, <tex>h \in A</tex>.
|proof =
<доказательство>
}}
<продолжение доказательства теоремы>
}}
