Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Эквивалентность понятий вычислимости
Различные формализации понятия алгоритма могли бы привести к различным понятиям вычислимости, однако для достаточно мощных концепций алгоритмов все развитые до сих пор понятия вычислимости оказываются эквивалентными.
Эквивалентность m-вычислимости и тьюринг-вычислимости
Рассмотрев две фундаментально различные формализации алгоритмов и вычислимости: m-вычислимостью и тьюринг-вычислимостью, нужно исследовать вопрос об эквивалентности обоих понятий.
Важным методом решения вопроса вычислимости, является гёделизация, которая восходит к немецкому логику Курту Гёделю (1933 г.).
Для конечного множества знаков А отображение
f: А* -> N
назовем гёделизацией
множества А, если справедливы следующие высказывания:
1. f инъективно;
2. f вычислимо (существует алгоритм, который для всех слов w Î А* вычисляет число f(w));
3. существует алгоритм, который для всех чисел n принадлежит N определяет, справедливо ли равенство n = f(w) для слова w Î А*;
4. существует алгоритм, который для любого числа n Î f (А*) вычисляет
5. слово w Î А*, для которого справедливо n = f(w).
Таким образом, гёделизация есть трансформация представления для слов из А* в натуральные числа такого рода, что все понятия вычислимости являются переносимыми.
Теорема. Каждая m-рекурсивная функция является тьюринг-вычислимой.
Идея доказательства. Для каждой из базисных m-рекурсивных функций можно задать соответствующую Т-машину. Композицию рекурсивных функций можно реализовать через композицию Т-машин. Примитивные рекурсии и m-рекурсии также могут быть смоделированы с помощью Т-машин. Этим способом каждую
m-рекурсивную функцию можно перевести в Тьюринг-программу.
Теорема. Каждая (целочисленная) тьюринг-вычислимая функция является
m-вычислимой.
Идея доказательства. Обозначим через К множество конфигураций Т-машины. Применим инъективную («вычислимую») функцию
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-рекурсивности.
Теорема: Для каждой программы Р для k—R—машины можно задать Т-машину М с алфавитом ленты {¾, ½}, которая моделирует данную R-машину.
Доказательство. Структурная индукция по структуре программы Р:
Р =e М читает входное слово, не изменяя его;
Р = sucCi М продвигается до i-го входного значения, добавляет один штрих ½ и возвращается в исходную позицию;
Р = predj М продвигается до i-го входного значения, вычитает один штрих и возвращается в исходную позицию;
Р = P1;P2 последовательная композиция Т-машин для P1 и Р2;
Р = whilei(Po) М продвигается до i-го входного значения; если там стоит штриховое представление для числа 0, следует остановка; в противном случае М возвращается к началу, запускает программу Р0 для М0, причем все состояния останова М0 заменяются на начальное состояние М.
Можно говорить также о моделировании Т-машины на k-R-машине, кодируя ленту в регистрах.
Теорема. Для каждой детерминированной машины Тьюринга TM, которая вычисляет функцию f: Ni -> Nj в обычном кодировании через {¾, ½}, существует k-регистровая машина (причем число регистров k зависит от машины Тьюринга TM), моделирующая машину TM.
Идея доказательства. Можно выбрать примерно следующую кодировку конфигурации Т-машины TM через состояния регистров R-машины М:
