Теорема Райса-Шапиро — различия между версиями
Vincent (обсуждение | вклад) (→Теорема Райса-Шапиро) |
Vincent (обсуждение | вклад) (→Теорема Райса-Шапиро) |
||
Строка 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>, так как: |
* если <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>, так как: |
* если <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
Содержание
Определение образца
Определение: |
Пусть Тогда называется образцом. | .
Свойство образца
Определение: |
Пусть Тогда называется свойством образца . | , где .
Лемма о перечислимости свойства образца
Лемма: |
Свойство перечислимо для любого образца . |
Доказательство: |
Построим полуразрешитель :Полуразрешителя достаточно для доказательства перечислимости. for if while True return 1 |
Лемма о перечислимости свойства перечислимого множества образцов
Лемма: |
Пусть — перечислимое множество образцов, .
Тогда является перечислимым. |
Доказательство: |
Построим полуразрешитель :Полуразрешителя достаточно для доказательства перечислимости. for for if return 1 |
Теорема Райса-Шапиро
Теорема: | ||||||||||||
Свойство функций перечислимо тогда и только тогда, когда , где — перечислимое множество образцов. | ||||||||||||
Доказательство: | ||||||||||||
Очевидно (перебор по TL).
Здесь нам потребуются две вспомогательные леммы.
Функции с конечной областью определения записываются так: if return if return Такие функции перечислимы. Значит, такие функции, удоволетворяющие , тоже перечислимы.по первой вспомогательной лемме. Значит, по второй вспомогательной лемме. . | ||||||||||||