Cтраница 1
Разрешающий алгоритм представляет собой л-кратное повторение алгоритма решения одной системы такого вида, и соответствующую программу для машины можно было бы легко составить по указанному выше образцу так, чтобы 6л коэффициентов располагались в 6л ячейках памяти, и чтобы программа насчитывала 11л 1 команд. [1]
Разрешающий алгоритм базируется на следующих трех основных алгоритмах. Пусть G - полициклическая группа, заданная порождающими и определяющими соотношениями. [2]
Требуется найти разрешающий алгоритм для проблемы эквивалентности слов в этом исчислении. [3]
Имеется ли разрешающий алгоритм для теорем. [4]
Основой описываемого ниже разрешающего алгоритма является следующее утверждение. [5]
Вопрос о возможности или невозможности разрешающего алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или несуществовании машины Тьюринга, обладающей нужным свойством. [6]
Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью некоторой модификации синтаксического метода элиминации кванторов. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классическое исчисление предикатов, где эффективно описаны все разрешимые и неразрешимые классы формул, заданные в терминах расположения кванторов в формуле и вида предикатных символов, встречающихся в формуле. Описан ряд разрешимых фрагментов арифметического исчисления, элементарной теории множеств. [7]
По определению теория разрешима, если она допускает разрешающий алгоритм. Она полуразрешима или частично разрешима, если допускает разрешающую процедуру. [8]
Даже к разрешимым теориям иногда применяются методы ИИ, когда не известно никакого разрешающего алгоритма. В частности, именно так обстоит дело в области теории игр. [9]
Вместе с тем становятся уже осмысленными постановки таких вопросов, как вопрос, о возможности или невозможности разрешающего алгоритма для задачи того или другого типа. [10]
Кстати, в системе рг есть некое свойство, позволяющее нам с уверенностью сказать, что данная система имеет разрешающий алгоритм, еще до того, как мы нашли критерий сложения. Это свойство заключается в том, что система рг не усложнена встречными укорачивающими и удлиняющими правилами; в ней имеются лишь удлиняющие правила. Любая формальная система, которая говорит нам, как получать более длинные теоремы из более коротких, но никогда не говорит нам обратного, должна иметь алгоритм разрешения для своих теорем. Представьте себе, что вам дана какая-либо строчка. Если это аксиома, то, следовательно, по определению она является теоремой, и проверка на этом заканчивается. Предположим теперь, что наша строчка - не аксиома. В таком случае, чтобы быть теоремой, она должна была быть получена из более короткой строчки путем применения одного из правил. Таким образом, проблема сводится к определению того, какие из новых, более коротких строчек являются теоремами. Каждая из них, в свою очередь, может быть подвергнута такой же проверке. [11]
Однако все эти процедуры строились, как правило, в сугубо теоретическом аспекте и для превращения их в практические разрешающие алгоритмы предстсит затратит. [12]
В заметке [1] сформулирована теорема об алгоритмической разрешимости элементарных теорий конечно аксиоматизируемых подклассов класса локально абсолютно свободных алгебр и дана схема разрешающего алгоритма. Ниже эта теорема распространяется на классы локально свободных алгебр с условием симметричности основных операций, дается подробное описание соответствующего разрешающего алгоритма, более простого, чем в заметке - [1], и указываются некоторые новые свойства упомянутых алгебр. [13]
Полезно заметить, что зачастую внешне незначительная и безобидная модификация проблемы на самом деле коренным образом изменяет характер трудностей, связанных с поиском разрешающего алгоритма. [14]
В результате многочисленных, но безрезультатных попыток создания таких алгоритмов стало ясным, что налицо имеются трудности принципиального характера, и возникло подозрение, что далеко не для всякого класса задач возможно построение разрешающего алгоритма. [15]