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




Состояние Левое слово Знак Правое слово - часть 2


Идея доказательства. Отношение следования на регистровых машинах оказывается примитивной рекурсией.

Нужно исходить из единственного понятия вычислимости, как оно формализуется с помощью рекурсивных функций, машин Тьюринга или регистровых машин, и обратиться к общим вопросам вычислимости.

Тезис Чёрча

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

Уже в 1936 г. А. Чёрч сформулировал это обстоятельство в своем знаменитом тезисе Чёрча:

«Любая интуитивно вычислимая функция является частично рекурсивной».

Обратим внимание, что тезис Чёрча математически недоказуем,ноего можно опровергнуть. Поскольку определение «интуитивно вычислимая» в тезисе Чёрча используется неформально, невозможно провести никакого формального доказательства. До сих пор не опровергнутый и общепринятый тезис гласит:

«Понятие вычислимости, определенное с помощью рекурсивных функций, ведет к самому мощному реалистическому понятию вычислимости, которое также эквивалентно другим предложенным понятиям вычислимости».

Было предложено несколько  определений понятия алгоритма:

(а) m-рекурсивность (частичные рекурсивные функции, Чёрч, 1936 г.),

(Ь) общерекурсивные функции (исчисление равенств

Гёделя - Хербранда - Клини, 1936; Клини, 1952; Мендельсон, 1964),

(с) -исчисление (Чёрч, 1936),

(d) машины Тьюринга (Тьюринг, 1936),

(е) система подстановок Поста (Пост, 1943),

(f)        алгоритмы Маркова (Марков, 1951),

(g)        регистровые машины (Шепердсон - Штургис, 1963).

Все эти формализации понятия алгоритма ведут к тому же самому понятию вычислимости.

Понятие вычислимости, лежащее в основе тезиса Чёрча, исходит из бесконечного множества состояний. Число состояний может быть неограниченно большим. Это, конечно, нереально. Каждая конкретная ЭВМ имеет лишь конечное пространство состояний и поэтому соответствует конечному автомату.  Понятие алгоритма по Черчу позволяет рассматривать вычисления для множества всех конечных автоматов. Любое завершающееся вычисление может быть успешно проведено, если конечный автомат, на котором оно проводится, достаточно велик.




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