Все, кто знаком с историей информатики, сразу поймут, что речь пойдет о Машине Поста и Машине Тьюринга. Почему проблема универсального формального исполнителя продолжает быть актуальной и до сегодняшнего дня?
Один из важнейших вопросов теоретической информатики звучит так: существует ли такой формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя? Такого исполнителя естественно назвать универсальным. Что это значит? Говорят, что формальный исполнитель А имитирует формального исполнителя В, если
- каждому объекту, над которым выполняет действия исполнитель В, однозначно соответствует объект, над которым выполняет действия исполнитель А (имитация среды исполнителя);
- каждому допустимому действию исполнителя В над тем или иным объектом среды однозначно сопоставлено допустимое действие исполнителя А над соответствующим объектом его среды (имитация действия);
- каждая инструкция, составленная для исполнителя В и приводящая при ее исполнении к определенному результату (т.е. к определенному состоянию среды исполнителя и него самого), может быть преобразована имитацией допустимых действий в инструкцию для исполнителя А, исполнение которой приводит соответствующему результату в среде исполнителя А.
При этом, с информационной точки зрения не принципиально, что у исполнителей А и В разная среда, в которой они существуют. Так как, если при кодировании информации используется двоичный код, можно считать, что среда исполнителей одинакова.
Итак, формальный исполнитель, как нам известно, выполняет действия по заданному алгоритму. Нам известны свойства алгоритма (дискретность, массовость, результативность, конечность). А как определить, что такое «алгоритм». В информатике, как ни в какой другой научной области (науке) очень многие определения не сформулированы до сих пор. Мы не имеем определения самого важного для нас объекта - «информация». Так же нет строгого математического определения понятию «алгоритм». Но мы пользовались и продолжаем пользоваться этим понятием, вкладывая в него свое интуитивное понимание этого термина.
За время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Собственно, цель математики – это построение алгоритмов решения поставленных задач. Для нахождения решения и построения алгоритма и существует весь тот математический аппарат, который построен за многие века развития математики.
Если алгоритм построен, эта задача (класс задач) перестает существовать для математиков. Если решения (алгоритма) нет, то математики продолжают «ломать голову». А всегда ли задача имеет решение? Наше воображение допускает, что, наверное, существуют задачи, которые невозможно решить. А если это так, то можно положить жизнь на поиск решения, которого нет! Как же быть? Можно ли заранее знать, имеет ли задача решение, стоит ли искать его, или это бесполезно?
Постепенно математики подходили к постановке и решению все более сложных задач. Так, например, Г. Лейбниц в XVII веке пытался построить общий алгоритм решения любых математических задач. В XX веке эта идея приобрела более конкретную форму: построить алгоритм проверки правильности любой теоремы при любой системе аксиом. Построить такие алгоритмы не удавалось, и математики выдвинули предположение: а вдруг для того или иного класса задач в принципе невозможно построить алгоритм решения? Следовательно, если алгоритма не существует, то они ищут то, чего нет.
На основе этого предположения возникло понятие алгоритмически неразрешимой задачи– задачи, для которой невозможно построить процедуру решения. Но для того, чтобы прекратить поиски решения задачи, относительно которой выдвинуто предположение об алгоритмической неразрешимости, надо было научиться математически строго доказывать факт отсутствия соответствующего алгоритма. А это возможно только в том случае, если существует строгое определение алгоритма. Первой фундаментальной теоретической работой, связанной с доказательством алгоритмической неразрешимости, была работа Курта Гёделя – его известная теорема о неполноте символических логик. Это была строго формулированная математическая проблема, для которой не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем был значительно расширен.
Что же представляют собой такие задачи? Приведем несколько примеров алгоритмически неразрешимых задач.
В начале XX века известный немецкий математик Давид Гильберт в 1900 г. сформулировал 23 математические проблемы. Сегодня решение (даже частичное) какой-либо проблемы Гильберта расценивается во всем мире как высшее математическое достижение. Десятая проблема Гильберта о диофантовых уравнениях (в упрощенной формулировке) звучит так:
Дано произвольное алгебраическое уравнение P(x1, х2, ..., хп) = 0, где Р - многочлен с целыми коэффициентами (например, ах11 + bх22 + сх33 =0). Требуется выяснить, существует ли у данного уравнения решение в целых числах.
Иная формулировка: требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.
В 1970 г. советский математик Ю. В. Матиясевич доказал невозможность построения алгоритма для решения этой задачи.
Попытки выработать формальное определение алгоритма привели в 20-30-х годах XX века к возникновению нового раздела математики Теории алгоритмов. В первой половине XX века разные математики (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.) предложили несколько подходов к формальному определению алгоритма: нормальный алгоритм Маркова, машина Тьюринга, машина Поста и т. д. В дальнейшем было показано, что все эти определения эквивалентны.
Одной из причин расплывчатости интуитивного понятия алгоритма является разнообразие объектов, с которыми работают алгоритмы. В вычислительных алгоритмах объектами являются числа. В алгоритме шахматной игры объектами являются фигуры и их позиции на шахматной доске. В алгоритме форматирования текста — слова некоторого языка и правила переноса слов. Однако во всех этих и других случаях можно считать, что алгоритм имеет дело не с объектами реального мира, а с некоторыми изображениями этих объектов. Например, есть алгоритм сложения двух целых чисел. Результатом сложения числовых объектов 26 и 22 будет числовой результат 48. Но мы можем считать, что объектом этого алгоритма является входная последовательность, состоящая из пяти символов: «26 + 22», а результатом является последовательность, состоящая из двух символов: «48».
При этом мы исходим из того, что имеется набор из 11 различных символов {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +}. Используемые символы будем называть буквами, а их набор — алфавитом. В общем случае буквами могут служить любые символы, требуется только, чтобы они были различны между собой, и чтобы их число было конечным.
Так, алгоритм сложения двух целых чисел перерабатывает слово, которое состоит из двух слагаемых, разделенных символом «+», в слово, изображающее сумму.
Так, объекты реального мира можно изображать словами в различных алфавитах. Это позволяет считать, что объектами работы алгоритмов могут быть
только слова.
только слова.