Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Состояние Левое слово Знак Правое слово
Конфигурация TM: si w1 a w2
Регистры машины М имеют следующее содержимое:
1. Регистр: <а> о w как зеркально отраженное двоичное число. (½= L,¾ = 0)
2. Регистр: W1 как двоичное число.
3. Регистр: i для состояния si.
Последующие регистры могут использоваться для запоминания переходов состояний. Это требует кодирования входных знаков и состояний числами.
Программа R-машины имеет следующую структуру, причем без oгpaничения общности считается, что sw есть единственное заключительное состояние Т-машины:
While3 (вычислим новое состояние и изменения ленты).
При выбранном представлении конфигураций Т-машины через содержимое регистров чтение знака под головкой Т-машины соответствует выяснению четности или нечетности содержимого первого регистра, а запись соответствует операции целочисленного деления на два с дальнейшим действием +1, если должен записываться знак L, +0 - в противном случае.
Сдвигу головки вправо соответствуют следующие операции:
· содержимое второго регистра умножить на два; записать знак L путем прибавления единицы ко второму регистру, если содержимое первого регистра нечетно;
· содержимое первого регистра разделить на два.
Сдвигу головки влево соответствуют следующие операции:
· содержимое первого регистра умножить на два; записать знак L путем прибавления единицы к первому регистру, если содержимое второго регистра нечетно;
· содержимое второго регистра разделить на два.
Теорема. Любая частично рекурсивная функция RM-вычислима.
Идея доказательства. Принципы, по которым строятся частично рекурсивные функции, могут быть смоделированы на R-машинах.
Теорема. Любая RM-вычислимая функция частично рекурсивна.
Идея доказательства. Отношение следования на регистровых машинах оказывается примитивной рекурсией.
Нужно исходить из единственного понятия вычислимости, как оно формализуется с помощью рекурсивных функций, машин Тьюринга или регистровых машин, и обратиться к общим вопросам вычислимости.
Тезис Чёрча
Существует много возможностей для формального определения понятий алгоритма и вычислимости, но ни одну из них невозможно формально квалифицировать как правильную или ложную. Впрочем, разнообразные понятия вычислимости можно сравнивать между собой, однако до сих пор все введенные понятия вычислимости оказывались эквивалентными (или, при ограниченном выборе понятий алгоритма, самое большее были слабее) m-вычислимости (соответственно, Т-вычислимости).Это является основополагающим адекватным понятием вычислимости.
Уже в 1936 г. А. Чёрч сформулировал это обстоятельство в своем знаменитом тезисе Чёрча:
«Любая интуитивно вычислимая функция является частично рекурсивной».
Обратим внимание, что тезис Чёрча математически недоказуем,ноего можно опровергнуть. Поскольку определение «интуитивно вычислимая» в тезисе Чёрча используется неформально, невозможно провести никакого формального доказательства. До сих пор не опровергнутый и общепринятый тезис гласит:
«Понятие вычислимости, определенное с помощью рекурсивных функций, ведет к самому мощному реалистическому понятию вычислимости, которое также эквивалентно другим предложенным понятиям вычислимости».
Было предложено несколько определений понятия алгоритма:
(а) m-рекурсивность (частичные рекурсивные функции, Чёрч, 1936 г.),
(Ь) общерекурсивные функции (исчисление равенств
Гёделя - Хербранда - Клини, 1936; Клини, 1952; Мендельсон, 1964),
(с) -исчисление (Чёрч, 1936),
(d) машины Тьюринга (Тьюринг, 1936),
(е) система подстановок Поста (Пост, 1943),
(f) алгоритмы Маркова (Марков, 1951),
(g) регистровые машины (Шепердсон - Штургис, 1963).
Все эти формализации понятия алгоритма ведут к тому же самому понятию вычислимости.
Понятие вычислимости, лежащее в основе тезиса Чёрча, исходит из бесконечного множества состояний. Число состояний может быть неограниченно большим. Это, конечно, нереально. Каждая конкретная ЭВМ имеет лишь конечное пространство состояний и поэтому соответствует конечному автомату. Понятие алгоритма по Черчу позволяет рассматривать вычисления для множества всех конечных автоматов. Любое завершающееся вычисление может быть успешно проведено, если конечный автомат, на котором оно проводится, достаточно велик.
