Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Эквивалентность понятий вычислимости - часть 2


rep: К ® N,

которая головку чтения/записи, ленту и состояния машины, т. е. конфигурации, представляет целыми числами («геделизирует»). Отношение следования на конфигурациях оказывается примитивно-рекурсивным. Существует примитивно-рекурсивная функция

g: N -> N,

такая, что для всех конфигураций k0, k1 машины Тьюринга справедливо

ko à k1 àg(rep(ko)) = rep(k1).

С помощью различения случаев, которое также может быть выражено в примитивной рекурсии,  можно специфицировать примитивно-рекурсивную функцию h с двумя параметрами n и m таким образом, что h(n, m) Точно тогда дает значение нуль, когда Т-машина, начиная работу с конфигурации, представленной параметром n, после m шагов останавливается. Эта примитивно-рекурсивная функция

h: N2à N

специфицируется следующим образом (предполагается, что g° (n) — n):

h(n,m)=[ 0, если g”(n) соответствует терминальной конфигурации,

h(n, m) = 1 иначе.]

Нужно ввести еще одну примитивно-рекурсивную функцию it с двумя параметрами n и m, такую, что it(n, m) доставляет представление конфигурации Т-машины, которая возникает через m шагов вычислений из начальной конфигурации, представленной параметром n. Функция

it:N2àN

специфицируется через

it(n, 0) = n,‘

it(n,m+l)=g(it(n),m).

Она, очевидно, также примитивно-рекурсивна.

Функция tm: N à N, специфицированная равенством tm(n) = it(n, m(h)(n)),

соответствует функции, которую вычисляет Т-машина, и является частичнорекурсивной.

Аналогичным образом можно доказать эквивалентность и других понятий вычислимости. В частности, эквивалентны также понятия RM-вычислимости и µ-вычислимости.

Эквивалентность RM- и тьюринг-вычислимости

Модели машин Тьюринга и регистровых машин весьма близки друг к другу, так что кажется достаточно очевидным, что RM- и Т-вычисли-мости эквивалентны.

Так как m-рекурсивность и Т-вычислимость являются эквивалентными понятиями, то из эквивалентности RM-вычислимости и Т-вычислимости следует также эквивалентность RM-вычислимости и m-рекурсивности.




Содержание  Назад  Вперед