Юный техник 1958-03, страница 55
это слово, составленное из букв, скобок, символов вроде И, ИЛИ, НЕ и так дат ее. Точно так же каждая теорема — это слово с другой комбинацией букв, скобок и прочих символов Значит, путь от аксиом к теоремам — это путь в лабиринте слов, в котором буквы и символы можно менять ло вполне опс>еделенным правилам. Так, например, слова «не неправильный» можно заменить словом «правильный», вместо «прямая АВ или прямая АВ» можно написать просто «прямая АВ», «Но существует этот путь или нет?» — именно на этот вопрос и должен давать ответ «всемогущий» алгоритм. Теперь нетрудно понять, насколько заманчиво иметь такой алгоритм. Ведь тогда можно было бы почти наугад сформулировать любую теорему и с его помощью проверить, имеется ли путь в лаби ринт слов от аксиом к этой теооеме, подобно тому как мы проверяли лабиринт в игре в «Пятнадцать». При положительном огв зте алгоритм указал бы: «Пути не существуют, и не следует герять силь на попытки доказать недоказуемое». «Всемс гущий» алгоритм в руках математика явился бы мощным единым средством для решения всех сформулированных, но еще до сих пор не решенных математических задач. Более того, претворив такой алгоритм в машинное руководство к действию, можно было бы создать «гениальный» математический автомат. Поэтому многие ученые во всем мире упорно занимались поисками «всеобщего» алгоритма. Но тщетно! Все попытки оказались безуспешными. Возникло сомнение в самом существовании «всеобщего» алгоритма. Но это были лишь сомнения. Строго доказать невозможность построения его оказалось делом не менее трудным, чем найти. И вот совсем недавно математический мир узнал о выдающемся достижении советской математической науки. Член-корреспондент Академии наук СССР П. С. Новиков доказал алгоритмическую неразрешимость тождес ва спов в теории групп. Это означает, что ему удалось найти пример преобразования слов в одной из современных областей математики — теории групп, для которой строго доказана невозможность построения алгоритма. Результат работы П. С. Новикова показывает, что неразрешимые алгоритмические проблемы характерны для математики и будут в дальнейшем возникать при ее развитии, Уверенность в том, что алгоритма для той или иной задачи не существует, избавляет математиков от безнадежных поисков. А такие поиски велись, так как выгодней найти общий метод решения большого числа задач и поручить само решение машине, чем для каждо-i задачи искать свой способ решения. Работа П. С. Новикова имеет огромное значение не только д,1я развития математики. Он показал, что процесс познания в математике не может быть втиснут в рамки алгоритма, а следовательно, его нельзя полностью автоматизировать Значение работь выдающегося советского математика было высоко оценено: П. С. Новиков удостоен Ленинской премии. 45 |
