|
|
| (не показано 15 промежуточных версий 5 участников) |
| Строка 1: |
Строка 1: |
| − | {{Определение
| + | [[Категория: Удалить]] |
| − | |definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы 1 условие из приведенных ниже:
| |
| − | # Существует программа(алгоритм) печатающая(перечисляющая) все элементы <tex>X</tex> в произвольном порядке
| |
| − | # <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>
| |
| − | # <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>
| |
| − | # Функция <tex>p_X(i) = \begin{cases}
| |
| − | 1 & i \in X \\
| |
| − | \bot & i \notin X
| |
| − | \end{cases}</tex> - вычислима
| |
| − | }}
| |
| − | | |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
| |
| − | |proof=
| |
| − | *1 <tex>\Rightarrow</tex> 4
| |
| − | | |
| − | Пусть <tex>A</tex> - программа перечисляющая <tex>X</tex>.
| |
| − | | |
| − | Приведем программу <tex>B</tex>, вычисляющую <tex>p_X(i):</tex>
| |
| − | | |
| − | <tex>B(i)</tex>
| |
| − | for (n = 1 ... <tex>+\infty</tex>)
| |
| − | if (A(n) == i)
| |
| − | return 1
| |
| − | | |
| − | | |
| − | *2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1
| |
| − | | |
| − | Пусть <tex>X</tex> область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>B</tex>.
| |
| − | | |
| − | Введем обозначение: <tex>B(i)|_{TL}</tex> <tex>-</tex> запустить <tex>B(i)</tex> на <tex>TL</tex> секунд. Если <tex>B(i)|_{TL}</tex> за <tex>TL</tex> секунд так и не вернула значение функции <tex>f(i)</tex>, то возвращаем -1.
| |
| − | | |
| − | Тогда <tex>X</tex> перечисляется такой программой <tex>A:</tex>
| |
| − | | |
| − | <tex>A()</tex>
| |
| − | for (<tex>TL</tex> = 1 ... <tex>+\infty</tex>)
| |
| − | for (n = 1 ... <tex>TL</tex>)
| |
| − | if (<tex>B(n)|_{TL}</tex> != -1)
| |
| − | print(n)
| |
| − | | |
| − | Если print(n) заменить на print(<tex>B(n)|_{TL}</tex>), то <tex>A()</tex> станет перечислять область значений <tex>f</tex>.
| |
| − | | |
| − | | |
| − | *4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3
| |
| − | | |
| − | Пусть дана <tex>p_X(i).</tex>
| |
| − | | |
| − | Введем новую функцию: <tex>l(n) = n,</tex> если <tex>p_X(n).</tex>
| |
| − | | |
| − | Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X.</tex>
| |
| − | | |
| − | | |
| − | ч.т.д.
| |
| − | }}
| |
