{{Определение|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, 3 <tex>\Rightarrow</tex> 1Пусть <tex>X</tex> — область определения [[Вычислимые функции|вычислимой функцииУдалить]] <tex>f</tex>, вычисляемой программой <tex>p</tex>. Введем обозначение: <tex>p(x)|_{TL}</tex> — остановить <tex>p(x)</tex> через <tex>TL</tex> секунд. Если <tex>p(x)|_{TL}</tex> за <tex>TL</tex> секунд так и не вернула значение функции <tex>f(x)</tex>, то возвращаем <tex>\bot</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>Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</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
