Об арифметизации функций

Анри Пуанкаре (1854 — 1912), рассуждая о будущем математики, указывает «Лучший метод для предвидения будущего развития математических наук заключается в изучении истории и нынешнего состояния этих наук».
Ретроспективный взгляд должен убедить нас в том, что последовательно проведенный позиционный способ обозначений, имеющий огромные преимущества перед литерным, не должен останавливаться на числах, а должен быть продолжен и на функции: ведь понятие функции — это следующие после числа фундаментальное понятие в математике. И если это не было сделано, то у нас есть все основания утверждать, что либо понятие позиционности не было осознано до конца, либо не извлекаются уроки из истории нашей математической науки. В самом деле, в современной математике в представлении функции f(x) используется позиционность лишь для x но для f мы продолжаем использовать непозиционные символы. Действительно, те задачи дискретной математики и искусственного интеллекта (логические преобразования, логический вывод, логическое и функциональное программирование и многое другое), которые рассматриваются в теории NP-полноты, используют текст в непозиционной записи. В самом деле, символы логических операций: & (конъюнкция), v (дизъюнкция), O (сложение по модулю два), ! (функция Вебба), / (штрих Шеффера) и другие не изменяют свой смысл от местоположения. Те же расширения системы операций, которые предпринимаются по линии увеличения арности, тоже сохраняют свой литерный характер, а потому не избавляют и избавить не могут от «комбинационных взрывов».
Единственный путь — это расширение принципа позиционности с аргументов функции и на символы этих функций, то есть осуществление полной арифметизации функций.
Заметим, что арифметизация К.Геделя (1906 — 1978), осуществленная им в 1931 году при доказательстве теоремы о неполноте, так же далека от сформулированной выше цели, как системы Архимеда и Аполлония, изложенные в их »Псаммите» и »Быстросчете» от позиционного представления чисел, но эти аналогии весьма полезны в том плане, что они указывают на новые возможности, которые еще должны быть реализованы.
Необходимость полной арифметизации функций на базе принципа позиционности становится актуальной задачей не только в прикладной (вычислительной) математике, но и для информационных технологий и для разработчиков новых архитектур компьютеров, в особенности с приближением к предельным значениям физических ограничений (скорость, миниатюризация). Проиллюстрируем сказанное на следующих фактах недавней истории.
Как известно, общая цель японского проекта — разработать компьютеры более производительные, более гибкие, более компетентные, более интеллектуальные. Решения задач и получение логических выводов — это главная цель системы пятого поколения, которая, кроме всего прочего, должна позволить достигнуть «дружелюбия» по отношению к пользователю.
Теперь мы знаем, что сформулированные цели не были достигнуты в полной мере (срок ввода в строй первого прототипа системы предполагался в 1991 году) и не могли быть достигнуты без соответствующего фундаментального открытия (о нем ниже).
После опубликования проекта (1981 год) он был подвергнут критическому анализу. Например, автор знаменитого метода резолюций Дж.Робинсон в публичной лекции, прочитанной в институте ICOT в Токио в 1983 году, указал в очень мягкой форме, что из намеченного может быть достигнуто, а что — проблематично.
Критика привела к тому, что характер проекта был уточнен и, самое главное, была изменена конечная цель, а именно, указывалось, что проект вовсе не предполагает создания по завершении десятилетнего этапа какого-либо коммерческого продукта: его цель — выполнение основных исследований, связанных с разработкой новой технологии компьютеров.
Критика имела сильные доводы. Ко времени создания японского проекта математикам было известно, что на пути создания эффективных методов решения дискретных задач возникает центральная теоретико-методологическая проблема всей дискретной математики: можно ли исключить перебор при решении дискретных задач? Иначе говоря, речь идет о принципиальной возможности найти нужное решение не перебирая всех или почти всех вариантов в задаче. Эта проблема имеет не только чисто математическое, но и глубокое познавательное значение. Прикладная сторона (заметим, что задача логического вывода — это задача дискретной математики) этой проблемы такова: в переборных задачах, как правило, имеется конечное множество вариантов, среди которых нужно найти решение. Например, двоичных векторов размерности n имеется 2n и, перебрав это экспоненциальное множество векторов, мы можем найти те вектора, которые удовлетворяют заданному свойству. Но с ростом n число векторов быстро растет, и задача становится «труднорешаемой», то есть практически неразрешимой. Стало общепринятым считать переборную задачу решаемой эффективно, если имеется алгоритм, решающий ее за время, ограниченное полиномом от размерности задачи.
Таким образом, в указанной выше проблеме главными объектами теории являются: класс NP всех переборных задач и класс P переборных задач, решаемых за полиномиальное время. Относительно классов P и NP имеется целый ряд исследователей, среди которых здесь отметим лишь результаты двух лауреатов премии Тьюринга: С.Кука и Р.Карпа.
В 1971 году С.Кук показал в своей основополагающей работе , что проблема выполнимости полна в классе NP относительно полиномиальной редукции, или короче, NP-полна. Грубо говоря, NP-полные проблемы имеют максимальную трудность среди всех проблем перебора. Отсюда следует, что если проблема выполнимости легка, то любая проблема перебора легка (то есть принадлежит к классу P). Из более точной формулировки теоремы Кука вытекает даже более сильное утверждение, а именно такое: быстрый алгоритм для решения проблемы выполнимости вполне механическим способом приводил бы к быстрой разрешающей процедуре для любой эффективно заданной проблемы перебора. Такой алгоритм служил бы отмычкой к проблемам перебора из всех областей математики.
В 1972 году Р.Карп значительно расширил список NP-полных проблем. К настоящему моменту большинство естественно возникающих проблем перебора классифицированы либо как P, либо как NP-полные.
«Вопрос о том, действительно ли NP-полные задачи труднорешаемы, в настоящее время считается одним из основных открытых вопросов современной математики и теоретической кибернетики. Вопреки готовности большинства специалистов считать, что все NP-полные задачи труднорешаемы, прогресс как в доказательстве, так и в опровержении этого далеко идущего предположения весьма незначителен. Однако, несмотря на отсутствие доказательства того, что из NP-полноты следует труднорешаемость, NP-полнота задачи означает, что для ее решения полиномиальным алгоритмом требуется по крайней мере крупное открытие».
И тем не менее, имеются все основания утверждать, что для того, чтобы NP-полные задачи имели решение полиномиальным алгоритмом, необходимо распространить принцип позиционности и на представления функций, с помощью которых записываются условия NP-полной задачи. В случае задачи выполнимости, к которой сводятся труднорешаемые задачи, это значит, что принцип позиционности должен быть распространен на представления функций алгебры логики.
Арифметизация функций алгебры логики на базе принципа позиционности, то есть разработка позиционного счисления функций и системы исчисления, то есть системы оперирования с функциями в позиционном их представлении, началась в первой половине 1978 года. Первые публикации на эту тему появились лишь в 1981 году. Список работ не охватывает всего объема работы: начало исследований отражено в краткой форме в статье. В более развернутом виде это сделано в последующих публикациях. Расширение принципа позиционности и его развитие отражено в следующих работах. Позднее было показано, что принцип позиционности аналогичным образом распространяется и на функции k-значной и k * m-значной логиках. Но все же самое главное — осмысление и систематичность, имеющихся к этому времени результатов, составляют излагаемый на этом ресурсе материал.

 Области применения алгоритмов позиционной алгебры логики.