Алгоритмические машины (стр. 3 из 6)
Этот тезис дает алгоритмическое истолкование понятия частично рекурсивной функции. Его нельзя доказать, поскольку он связывает нестрогое математическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции. Однако исследования, проводившиеся весьма многими математиками в течение нескольких десятилетий, выявили полную целесообразность считать понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.
Тезис Чёрча оказался достаточным, чтобы придать необходимую точность формулировкам алгоритмических проблем и в ряде случаев сделать возможным доказательство их неразрешимости. Причина заключается в том, что обычно в алгоритмических проблемах математики речь идет не об алгоритмах, а о вычислимости некоторых специальным образом построенных функций. В силу тезиса Чёрча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое. Поэтому обычная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной. Именно этим путем самому Чёрчу удалось доказать неразрешимость основной алгоритмической проблемы логики предикатов – проблемы тождественной истинности формул исчисления первой ступени.
Точное описание класса частично рекурсивных функций вместе с тезисом Чёрча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Спрашивается, нельзя ли уточнить непосредственно само понятие алгоритма и уже затем при его помощи определить точно и класс вычислимых функций? Такое направление поиска привело к построению иного, нежели рекурсивные функции, класса моделей алгоритма. Основная его идея состоит в том, что алгоритмические процессы – это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком. Функционирование такой машины и есть выполнение некоторого алгоритма.
Исходя из свойств алгоритма, можно сформулировать общие требования к таким машинам:
1. характер их функционирования должен быть дискретным, т.е. состоять из отдельных шагов (команд), каждый из которых выполняется только после завершения предыдущего;
2. действия должны быть детерминированы, т.е. шаги выполняются в строгом порядке, а их результат определяется самим шагом и результатами предыдущих шагов;
3. перед началом работы машине предоставляются исходные данные из области определения алгоритма;
4. за конечное число шагов работы машины должен быть получен результат или информация о том, что считать результатом;
5. машина должна быть универсальной, т.е. такой, чтобы с её помощью можно было бы выполнить любой алгоритм.
Чем проще структура (устройство) описанной машины и чем элементарнее ее шаги, тем больше оснований считать, что ее работа и есть выполнение алгоритма. Чтобы ответить на вопрос, какие шаги работы машины следует отнести к элементарным, вернемся к тому обстоятельству, что нас интересует преобразование информации, представленной с помощью некоторого конечного алфавита. Требование конечности алфавита является очевидным следствием того обстоятельства, что решение должно быть получено за конечное число шагов. Если информация не представлена в дискретной форме, например вещественное число, то его обработка в общем случае может содержать бесконечное число шагов, например нахождение цифр числа π или извлечение квадратного корня из числа 2. Таким образом, алгоритм оказывается конечной последовательностью действий, производимых над данными, представленными с помощью конечного алфавита. С учетом сказанного становится понятным определение алгоритма, которое дает В.М. Глушков: «Алгоритм – это любая конечная система правил преобразования информации (данных) над любым конечным алфавитом».
Пусть исходные данные из области определения алгоритма представлены посредством алфавита A и образуют при этом конечную последовательность знаков {a1…an} – такая последовательность называется словом. В результате выполнения алгоритма сформируется новое слово {b1…bm}, представленное, в общем случае, в другом алфавите B. На первый взгляд для проведения такого преобразования в качестве элементарных выделяются следующие операции (шаги):
1. замена одного знака исходного слова ai знаком bj из алфавита B;
2. удаление знака исходного слова;
3. добавление к исходному слову знака из алфавита B.
Однако если в алфавиты включен знак, имеющий смысл пустого знака, добавление которого к слову слева или справа не изменяет этого слова, по аналогии добавления слева числового нуля к числу, то легко видеть, что: операция (2) есть ни что иное, как замена ai пустым знаком, а операция (3) есть замена пустого знака знаком bj. Таким образом, все возможные алфавитные преобразования сводятся к операции (1) – замене одного знака другим. Именно по этой причине функционирование абстрактной машины сводится к тому, что она считывает и распознает символы, записанные в памяти, в качестве которой выступает бесконечная лента, и, в зависимости от своего состояния, и того, каков обозреваемый символ, она заменяет его другим символом. После этого она переходит в новое состояние, читает следующий символ и т.д. до команды о прекращении работы. Поскольку подобные машины являются чисто модельным, теоретическим построением, они получили название абстрактных машин и рассматриваются в качестве одной из возможных универсальных алгоритмических систем.
3. Алгоритмическая машина Поста
На самом деле, Пост, в отличие от Тьюринга, не пользовался термином «машина», а называл свою модель алгоритмической системой. Однако, подчеркивая единство подходов обоих авторов, принято говорить о машине Поста.
Абстрактная машина Поста состоит из бесконечной ленты, разделенной на равные секции, а также считывающе-записывающей головки. Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена, т.е. в нее записана метка). Вводится понятие состояние ленты как информация о том, какие секции пусты, а какие отмечены. По-другому: состояние ленты – это распределение меток по секциям, т.е. это функция, которая каждому числовому номеру секции ставит в соответствие либо метку, либо знак «пусто». Естественно, в процессе работы машины состояние ленты меняется. Состояние ленты и информация о положении головки характеризуют состояние машины Поста.
Условимся обозначать головку знаком «
» над обозреваемой секцией, а метку – знаком «M» внутри секции. Пустая секция никакого знака не содержит. За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку. Работа машины Поста заключается в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд. Каждая команда имеет структуру xKy, где:− x – номер исполняемой команды;
− K – указание о выполняемом действии;
− y – номер следующей команды (наследника).
Система команд машины, включающая шесть действий, представлена в таблице 1.
Таблица 1 - Система команд машины Поста
| № п/п | Команда | Запись команды | Описание действий машины |
| 1 | Шаг вправо | x→y | Сдвиг головки на одну секцию вправо |
| 2 | Шаг влево | x←y | Сдвиг головки на одну секцию влево |
| 3 | Установить метку | xMy | В обозреваемую секцию ставится метка |
| 4 | Стереть метку | xCy | Из обозреваемой секции удаляется метка |
| 5 | Передача управления |  | При отсутствии метки в обозреваемой секции управление передается команде y1, при наличии – команде y2 |
| 6 | Остановка | x стоп | Прекращение работы машины |
Данный перечень должен быть дополнен следующими условиями:
− команда xMy может быть выполнена только в пустой секции;
− команда xCy может применяться только к заполненной секции;
− номер наследника любой команды y должен соответствовать номеру команды, обязательной имеющейся в данной программе.
Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата. В отличие от этой ситуации, остановка по команде x стоп является результативной, т.е. она происходит после того, как результат действия алгоритма получен. Кроме того, возможна ситуация, когда машина не останавливается никогда. Это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.
Еще одним исходным соображением является следующее: поскольку знаки любого конечного алфавита могут быть закодированы цифрами, преобразование исходного слова может быть представлено в виде некоторых правил обработки чисел. По этой причине в машине Поста предусматривается только запись (представление) целых положительных чисел.