Математический аппарат инженера

Пусть, например, требуется сложить числа 4 и 6. исходное слово на ленте запишется в виде 1111+111111. В соответствии с приведенной выше схемой сложения начальные условия определяются ячейкой с крайней левой единицей и состоянием s₁. На первом такте единица стирается, выдается команда сдвига вправо и перехода в состояние s₃(∧Пs₃ ). Последующие такты сводятся к сдвигам направо сквозь все единицы (1Пs₃ ) и знак + (+Пs₃

) до тех пор, пока не будет достигнута первая пустая ячейка. Тогда в эту пустую ячейку вписывается единица и машина переходи в состояние s₂ (1Нs₂) При состоянии s₂ происходят сдвиги в обратном направлении через все символы 1 и + до первой пустой ячейки слева. После этого происходит сдвиг вправо, левая крайняя единица стирается, и машина переходит в состояние s₁ (∧Пs₁

). В результате этого цикла единица левого слагаемого оказалась перенесенной в правое слагаемое, что соответствует слову 111+1111111 (сумма не изменяется). Очевидно, через четыре таких цикла исходное слово преобразуется к виду +1111111111. К началу пятого цикла обозревается символ + при состоянии s₁, который стирается и происходит остановка (∧Н!). В результате получим слово 1111111111, соответствующее числу 10.

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

- 629 -

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

9. Алгоритмическая разрешимость. После того как понятие алгоритма получило точное определение, вопрос об алгоритмической разрешимости того или иного класса задач ставится совершенно определенно: существует ли какая-либо стандартная форма алгоритма, решающая данный класс задач? В ряде случаев на этот вопрос теория алгоритмов дает отрицательный ответ.

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

Пробным камнем теории алгоритмов явилась проблема распознавания выводимости: для любых двух формул R и S в логическим исчислении узнать, существует ли дедуктивная цепочка, ведущая от R к S, или же такой цепочки не существует. Оказалось, что эта проблема алгоритмически неразрешима. Отрицательный ответ получен и для проблемы распознавания эквивалентности слов в любом ассоциативном исчислении. Были построены конкретные примеры ассоциативных исчислений, в которых- не существует алгоритма, позволяющего для любой пары слов установить, эквиваленты они или нет. Простейший пример такого исчисления приведен в (5).

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

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

- 630 -

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