Изменения

|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы 1 одно условие из приведенных ниже:# Существует программа(алгоритм) печатающая(перечисляющая) все элементы <tex>X</tex> в произвольном порядке.# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex> .# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex> . # Функция <tex>p_Xf_X(ix) = \begin{cases} 0 1, & i x \in X \\ \bot , & i x \notin X \end{cases}</tex> - — вычислима.

Пусть <tex>Ap</tex> - — программа , перечисляющая <tex>X</tex>.

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

<tex>Bq(ix)</tex> '''for (n ''' <tex>k = 1 \ ... <tex>+\ \infty</tex>) '''if ''' <tex> p(A(nk) == i)x </tex> '''then return 0''' 1

Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>Bp</tex>.

Введем обозначение: <tex>Bp(ix)|_{TL}</tex> &nbsp; <tex>-</tex> — &nbsp; запустить &nbsp; <tex>Bp(ix)</tex> &nbsp; на &nbsp; <tex>TL</tex> &nbsp; секунд. Если &nbsp; <tex>Bp(ix)|_{TL}</tex> &nbsp; за &nbsp; <tex>TL</tex> &nbsp; секунд так и не вернула значение функции <tex>f(ix)</tex>, то возвращаем -1<tex>\bot</tex>.

Тогда <tex>X</tex> перечисляется такой программой <tex>A:</tex>

<tex>Aq()</tex> '''for (''' <tex>TL</tex> = 1 \ ... <tex>+\ \infty</tex>) '''for (n ''' <tex> k = 1 \ ... <tex>\ TL</tex>) '''if (''' <tex>Bp(nk)|_{TL}\neq \bot </tex> != -1) '''then print'''<tex>(nk)</tex>

Если print<tex>(nk) </tex> заменить на print(<tex>Bp(nk)|_{TL}</tex>), то <tex>A()q</tex> станет перечислять область значений <tex>f(x)</tex>.

Пусть дана <tex>p_Xf_X(ix).</tex>.

Введем новую функцию: <tex>lg(nx) = n,x</tex> , если <tex>p_Xf_X(nx).\neq \bot</tex> .

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

* ''Верещагин Н.К.Верещагин, Шень А.Шень "'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции"''' -- М.: МЦНМО, 1999