== Определение =={{Определение|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
