|
|
| Строка 1: |
Строка 1: |
| − | == Определение ==
| + | [[Категория: Удалить]] |
| − | {{Определение
| |
| − | |definition='''Множество <tex>X</tex> называется перечислимым''', если выполняется хотя бы одно из условий:
| |
| − | # существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке;
| |
| − | # <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>;
| |
| − | # <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>;
| |
| − | # функция <tex>f_X(x) = \begin{cases}
| |
| − | 1, & x \in X \\
| |
| − | \bot, & x \notin X
| |
| − | \end{cases}</tex> — вычислима.
| |
| − | }}
| |
| − | | |
| − | == Эквивалентность определений ==
| |
| − | | |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
| |
| − | |proof=
| |
| − | *1 <tex>\Rightarrow</tex> 4.
| |
| − | | |
| − | Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.
| |
| − | | |
| − | Приведём программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x)</tex>:
| |
| − | | |
| − | <tex>q(x):</tex>
| |
| − | '''for''' <tex>k = 1 \ .. \ \infty</tex>
| |
| − | '''if''' <tex> p(k) == x </tex>
| |
| − | '''return''' 1
| |
| − | | |
| − | | |
| − | *2 <tex>\Rightarrow</tex> 1.
| |
| − | | |
| − | Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
| |
| − | | |
| − | Тогда <tex>X</tex> перечисляется такой программой:
| |
| − | | |
| − | <tex>q():</tex>
| |
| − | '''for''' <tex> TL = 1 \ .. \ \infty </tex>
| |
| − | '''for''' <tex> k = 1 \ ..\ TL</tex>
| |
| − | '''if''' <tex>p(k)|_{TL} \neq \bot </tex>
| |
| − | '''print''' <tex>k</tex>
| |
| − | | |
| − | *3 <tex>\Rightarrow</tex> 1.
| |
| − | | |
| − | Пусть <tex>X</tex> — область значений вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
| |
| − | | |
| − | Тогда <tex>X</tex> перечисляется такой программой:
| |
| − | | |
| − | <tex>q():</tex>
| |
| − | '''for''' <tex> TL = 1 \ .. \ \infty </tex>
| |
| − | '''for''' <tex> k = 1 \ ..\ TL</tex>
| |
| − | '''if''' <tex>p(k)|_{TL} \neq \bot </tex>
| |
| − | '''print''' <tex>p(k)|_{TL}</tex>
| |
| − | | |
| − | | |
| − | *4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3.
| |
| − | | |
| − | Пусть дана <tex>f_X(x)</tex>.
| |
| − | | |
| − | Введём новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.
| |
| − | | |
| − | Очевидно, что она вычислима и что её область определения и область значений совпадают с <tex>X</tex>.
| |
| − | | |
| − | }}
| |
| − | | |
| − | == Литература ==
| |
| − | * Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
| |
