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



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


Различные формализации понятия алгоритма могли бы привести к различным понятиям вычислимости, однако для достаточно мощных концепций алгоритмов все развитые до сих пор понятия вычислимости оказываются эквивалентными.

Эквивалентность 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-вычислимой.

Идея доказательства. Обозначим через К множество конфигураций Т-машины. Применим инъективную («вычислимую») функцию




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