Проблема алгоритмической разрешимости

Всякому методу соответствует задачка, для решения которой он был построен. Оборотное утверждение в общем случае является неправильным по двум причинам: во-1-х, одна и та же задачка может решаться разными методами; во-2-х, можно представить (пока), что имеются задачки, для которых метод вообщем не может быть построен.

Как ранее говорилось, термин «алгоритм» появился в арифметике довольно издавна и употреблялся длительно — под ним понималась процедура, позволявшая методом выполнения последовательности определенных простых шагов получать конкретный итог, не зависящий от того, кто эти шаги делал. Таким макаром, само проведенное решение служило подтверждением существования метода. Но был известен целый ряд математических задач, разрешить которые в общем виде не удавалось. Примерами могут послужить три древнейшие геометрические задачки: о трисекции угла, о квадратуре круга и об удвоении куба — ни одна из их не имеет общего метода решения при помощи циркуля и линейки без делений.

Энтузиазм математиков к задачкам подобного рода привел к постановке вопроса: может быть ли, не решая задачки, обосновать, что она алгоритмически неразрешима, т.е. что нельзя выстроить метод, который обеспечил бы ее общее решение? Ответ на это вопрос важен, в том числе, и с практической точки зрения, к примеру, глупо пробовать решать задачку на компьютере и разрабатывать для нее программку, если подтверждено, что она алгоритмически неразрешима. Конкретно для ответа на данный вопрос и пригодилось поначалу дать серьезное определение метода, без чего обсуждение его существования просто не имело смысла. Построение такового определения, как уже знаем, привело к возникновению формальных алгоритмических систем, что отдало возможность математического подтверждения неразрешимости ряда заморочек. Оно сводится к подтверждению невозможности построения рекурсивной функции, решающей задачку, или (что эквивалентно) к невозможности построения машины Тьюринга для нее, или несостоятельности хоть какой (какой-нибудь) другой модели из представленных на рис. 7.3. Т.е. задачка считается алгоритмически неразрешимой, если не существует машины Тьюринга (либо рекурсивной функции, либо обычного метода Маркова), которая ее решает.

1-ые подтверждения алгоритмической неразрешимости касались неких вопросов логики и самой теории алгоритмов. Оказалось, к примеру, что неразрешима задачка установления истинности случайной формулы исчисления предикатов (т.е. исчисление предикатов неразрешимо) — эта аксиома была подтверждена в 1936г. Черчем.

В 1946—47 гг. А.А. Марковым и Э. Постом независимо друг от друга обосновали отсутствие метода для определения эквивалентности слов в любом ассоциативном исчислении.

В теории алгоритмов к алгоритмически неразрешимой относится «неувязка остановки»: можно ли по описанию метода (Q) и входным данным (х) установить, закончится ли выполнение метода действенной остановкой? Эта неувязка имеет прозрачную программистскую интерпретацию. Нередко ошибки разработки программки приводят к зацикливанию — ситуации, когда цикл не заканчивается и не происходит окончания работы программки и остановки. Неразрешимость трудности остановки значит, что нельзя сделать общий (т.е. применимый для хоть какой программки) метод отладки программ. Неразрешимой оказывается и неувязка определения эквивалентности алгоритмов: нельзя выстроить метод, который для всех 2-ух алгоритмов (программ) выяснял бы, всегда ли они приводят к одному и тому же результату либо нет.

Значимость подтверждения алгоритмической неразрешимости в том, что если такое подтверждение получено, оно имеет смысл закона-запрета, позволяющего не растрачивать усилия на поиск решения, подобно тому, как законы сохранения в физике делают глупыми пробы построения нескончаемого мотора. Совместно с этим нужно сознавать, что алгоритмическая неразрешимость какой-нибудь задачки в общей постановке не исключает способности того, что разрешимы какие-то ее личные случаи. Справедливо и оборотное утверждение: решение личного варианта задачки еще не дает повода считать вероятным ее решения в самом общем случае, т.е. не свидетельствует о ее общей алгоритмической разрешимости. Роль абстрактных алгоритмических систем в том, что конкретно они позволяют оценить возможность нахождения полного (общего) решения некого класса задач. Для спеца в области информатики принципиально сознавать, что наличие алгоритмически неразрешимых заморочек приводит к тому, что оказывается неосуществимым выстроить универсальный метод, применимый для решения хоть какой задачки (и, как следует, глупо растрачивать силы на его создание). К схожим дилеммам приводят и пробы алгоритмизировать сложную умственную деятельность человека, к примеру, обучение других людей, сочинение стихов и пр.