- •Тема № 3 Алгоритмические основы вычислительных процессов. Элементы теории алгоритмов и формальных языков.
- •3.3. Сведение произвольных алгоритмов к числовым функциям. Понятие вычислимой функции. Алгоритмическая полнота эвм.
- •3.4. Понятие о формальных языках и порождающих грамматиках. Описание алгоритмических языков с помощью порождающих грамматик.
- •3.5. Необходимость формализации интуитивного понятия алгоритма. Понятие формальной алгоритмической системы. Алгоритмические системы Тьюринга и Поста.
- •Машина тьюринга
- •Машина поста
- •3.6. Понятие алгоритмической неразрешимости массовых проблем. Примеры алгоритмических неразрешимых массовых проблем в области информатики.
- •2.5. Законы алгебры Буля, их применение для преобразования формул булевых функций.
Машина поста
Эмиль Пост предложил абстрактную вычислительную машину – машину Поста. Она отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции ленты, считающейся условно бесконечной в обе стороны. В каждой клетке может быть записан символ из фиксированного алфавита. В любой конкретный момент головка обозревает одну клетку и способна работать только с ней.
Работа машины Поста определяется программой с конечным числом строк. Программы состоит из команд, имеющих по 3 поля, в которых записываются: № команды, операция и отсылка.
Команда машины Поста имеет следующую структуру:
n K m,
где n – порядковый номер команды, K – действие, выполняемое головкой, m – номер следующей команды, подлежащей выполнению.
Существует всего шесть команд машины Поста.
Для машины Поста определены операции 6 видов:
Движение головки на 1 клетку вправо.
Движение головки на 1 клетку влево.
Запись метки.
Удаление метки.
Условный переход по метке.
STOP – остановка (завершение работы машины Поста);
С точки зрения свойств алгоритмов, изучаемых с помощью машины Поста, наибольший интерес представляют причины останова машины при выполнении программы:
останов по команде «стоп»; такой останов называется результативным и указывает на корректность алгоритма (программы);
останов при выполнении недопустимой команды; в этом случае останов называется безрезультативным;
машина не останавливается никогда; в этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).
Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:
неделимые носители информации (клетки – биты), которые могут быть заполненными или незаполненными;
ограниченный набор элементарных действий – команд, каждая из которых выполняется за один такт (шаг).
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:
работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
работа может закончиться командой Stop;
работа никогда не закончится.
Обе машины работают на основе программы. Однако, в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста и т.д.
3.6. Понятие алгоритмической неразрешимости массовых проблем. Примеры алгоритмических неразрешимых массовых проблем в области информатики.
В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому, что его пока не придумали, а потому что он невозможен в принципе.
Разумеется, алгоритм надо понимать в смысле машин Тьюринга и рекурсивных функций. Сформулируем одну из этих задач.
Проблема остановки машины Тьюринга. Машина Тьюринга – это объект, определяемый конечным числом параметров. Все частичные отображения одного конечного множества в другое могут быть эффективным образом перенумерованы.
Поэтому каждой машине Тьюринга можно присвоить номер (натуральное число). Пусть T(n) машина Тьюринга с номером n.
Некоторые машины, начинающие работать на пустой ленте, в конце концов останавливаются, а некоторые работают бесконечно долго.
Возникает задача: по натуральному числу n определить, остановится или нет машина Тьюринга T(n) запущенная на пустой ленте.
Эта задача алгоритмически неразрешима. То есть не существует автоматической процедуры, для каждого n решающей, останавливается или нет машина T(n).
Это не исключает того, что для какой-либо конкретной машины мы установим, останавливается она или нет. Не существует метода, решающего это сразу для всех машин.