Изменения

|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}

Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>:

<tex>q(x):</tex>

*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>\bot</tex>.

<tex>q():</tex>

Если print*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> заменить на print( '''if''' <tex>p(k)|_{TL}\neq \bot </tex>), то '''print'''<tex>q</tex> станет перечислять область значений <tex>f(xp(k)|_{TL})</tex>.

Очевидно, что она вычислима, и что ее область определения и область значений совпадают с <tex>X</tex>.