Урок 61
Алгоритмически неразрешимые задачи
(§35. Алгоритмически неразрешимые задачи)
Содержание урока
Вычислимые и невычислимые функции
Когда задача алгоритмически неразрешима?
Когда задача алгоритмически неразрешима?
Как вы знаете, невозможно создать вечный двигатель, потому что это противоречит универсальным физическим законам сохранения. Точно так же в математике и информатике существуют задачи, для которых решение в общем виде отсутствует.
Поскольку алгоритм работает только с дискретными объектами, любая алгоритмическая задача — это функция, заданная на множестве дискретных объектов (входных слов).
Пусть, например, требуется по шахматной позиции определить, кто выигрывает при правильной игре — белые, чёрные или будет ничья. Построим функцию, соответствующую этому алгоритму. Для этого выберем способ кодирования, при котором каждая позиция может быть закодирована словом (символьной строкой) v в подходящем алфавите. Тогда приведённой задаче может соответствовать функция f(v), заданная на множестве таких слов:
Если функция, соответствующая задаче, вычислима, то задача называется алгоритмически разрешимой — для её вычисления можно построить алгоритм. Если определённая в задаче функция невычислима, то алгоритма для её решения не существует.
Алгоритмически неразрешимая задача — это задача, соответствующая невычислимой функции.
В 1900 г. на Международном математическом конгрессе в Париже известный математик Давид Гильберт сформулировал 23 нерешённые математические проблемы 1.
1 Сейчас большинство из них решено полностью или частично.
В знаменитой «десятой проблеме Гильберта» требуется найти метод, который позволяет определить, имеет ли заданное алгебраическое уравнение с целыми коэффициентами решение в целых числах. Например, уравнение
х2 + у3 + 2 = 0
имеет два целочисленных решения, (5; -3) и (-5; -3). Сложность состояла в том, что требовалось найти единый метод (алгоритм), позволяющий решить задачу для любого такого уравнения со многими неизвестными.
В начале XX века была уверенность, что такой алгоритм есть, и поэтому его упорно искали. Однако в 1970 г. советскому математику Ю. В. Матиясевичу удалось доказать, что общего алгоритма решения этой задачи не существует.
Немецкий математик Г. В. Лейбниц в XVII веке безуспешно пытался найти метод проверки правильности любых математических утверждений. Как вы знаете, почти все математические теории основаны на использовании аксиом (положений, принимаемых без доказательства), из которых выводятся все остальные утверждения (теоремы). Задача заключалась в том, чтобы разработать алгоритм, позволяющий установить, можно ли вывести формулу Б из формулы А в рамках заданной системы аксиом («проблема распознавания выводимости»).
В 1936 г. американский математик А. Чёрч доказал, что эта задача в общем виде алгоритмически неразрешима, поэтому нельзя сформулировать универсальный алгоритм, пригодный для доказательства любой теоремы 2.
2 Тем не менее отдельные классы теорем можно доказывать на компьютере.
Таким образом, уточнённые определения алгоритма, основанные на понятии универсальных исполнителей, сыграли в науке очень важную роль — позволили получить отрицательные результаты, т. е. доказать, что алгоритмов решения некоторых задач в общем виде не существует.
Для того чтобы доказать неразрешимость какой-то новой задачи, пытаются свести её к уже известным алгоритмически неразрешимым задачам. Если это удаётся, значит, и новая задача алгоритмически неразрешима 3.
3 Допустим, что (1) задача А неразрешима и (2) если мы можем построить алгоритм для решения задачи Б, то с его помощью можно построить алгоритм решения задачи А. Тогда задача Б тоже неразрешима.
Существуют также задачи, про которые неизвестно, алгоритмически разрешимы они или нет — решение не найдено, но алгоритмическая неразрешимость не доказана.
Алгоритмически неразрешимые задачи встречаются не только в математике, но и в информатике, например при разработке программ. Оказывается, невозможно написать программу для машины Тьюринга (алгоритм), которая по тексту любой программы Р и её входным данным X определяет, завершается ли программа Р при входе X за конечное число шагов или зацикливается. Это так называемая проблема останова. Её неразрешимость означает, в частности, что нельзя полностью автоматизировать тестирование любых программ, поручив это компьютеру. Однако для некоторых классов алгоритмов проблему останова решить можно. Например, линейная программа, не содержащая ветвлений и циклов, всегда завершится.
Было доказано, что алгоритмически неразрешима проблема эквивалентности: по двум заданным алгоритмам определить, будут ли они выдавать одинаковые результаты для любых допустимых исходных данных. Следовательно, невозможно полностью автоматизировать решение многих важных задач, связанных с разработкой программ, например:
• по заданному тексту программы определить, что она «делает»;
• определить, правильно ли работает программа при любых допустимых исходных данных;
• найти ошибку в программе, работающей неправильно. Поэтому при отладке программы большую роль играет интуиция. Помогают (но не решают проблему полностью!) стандартные приёмы, позволяющие найти ошибку:
• сравнение результатов работы программы с результатами ручного счёта;
• эксперименты с программой при различных исходных данных для того, чтобы выявить закономерность появления ошибок;
• временное отключение (комментирование) частей программы и др.
Поскольку многие этапы разработки программного обеспечения в принципе невозможно представить в виде алгоритмов, программирование остаётся работой человека. Полностью поручить его компьютеру не удаётся, хотя решение некоторых задач всё же можно автоматизировать.
Следующая страница 
Вопросы и задания
Cкачать материалы урока
