Cтраница 2
При всем внешнем сходстве с проблемой самоприменимости имеет место, однако, следующий факт; проблема распознавания f - самопримени-мости алгоритмически разрешима. Разрешающий алгоритм 31 заключается в следующем. Для данного слова Р проверяем, является ли оно шифром какой-либо машины. Если Р не является шифром, то тем более оно не является f - самоприменимым шифром и ответ ( отрицательный) уже найден. Далее, по шифру Р восстанавливаем схему машины и, запуская ее в начальной конфигурации с записью слова Р, следим за ее работой в течение не более чем f ( Р) тактов. [16]
Кроме того, для любого х выполняется либо F ( x) l, либо G () j, но никак не оба утверждения одновременно. Таким бразом, получается следующий разрешающий алгоритм для М ( х): взяв данное х, будем проводить вычисления F ( х) и G ( х) одновременно ( или будем выполнять последовательно шаг од-н й программы, затем следующий шаг другой программы и т - А -) до тех пор, пока одна из программ не остановится. [17]
Таким образом, в отношении проблемы разрешимости исчисление предикатов коренным образом отличается от исчисления высказываний. Впрочем, если ограничиться теми или иными частными видами формул, то разрешающий алгоритм может быть построен и в случае исчисления предикатов. [18]
Для описания языка может использоваться и другой тип алгоритма. При этом втором подходе проверяемая строка выступает в виде исходных данных в разрешающем алгоритме. После необходимых вычислений алгоритм вырабатывает ответ да, строка правильная или нет, это неправильная строка. Такое определение языка называется аналитическим. Язык с аналитическим описанием разрешим, если анализатор для каждой входной строки завершает свою работу за конечное число шагов. [19]
В заметке [1] сформулирована теорема об алгоритмической разрешимости элементарных теорий конечно аксиоматизируемых подклассов класса локально абсолютно свободных алгебр и дана схема разрешающего алгоритма. Ниже эта теорема распространяется на классы локально свободных алгебр с условием симметричности основных операций, дается подробное описание соответствующего разрешающего алгоритма, более простого, чем в заметке - [1], и указываются некоторые новые свойства упомянутых алгебр. [20]
Поэтому параллельно с усилиями, направленными на поиски желаемого алгоритма, приходится прилагать усилия для доказательства невозможности такого алгоритма. В зависимости от того, на каком из этих направлений будет достигнут успех, и выяснится окончательно картина: либо будет найден разрешающий алгоритм, либо установлена алгоритмическая неразрешимость проблемы. [21]
Если таковая обнаружится, значит, это - теорема. Если же в какой-то момент вы заметите, что все, что попадает в корзину, длиннее искомой строчки, можете прекратить поиски - это не теорема. Такой разрешающий алгоритм называется восходящим, так как он исходит из основы, фундамента системы - аксиом. [22]
Мы уже с самого начала столкнулись с тем, что формальные системы могут вести себя как неукротимые и опасные бестии, когда в них есть удлиняющие и укорачивающие правила, поскольку это может привести к бесконечному поиску среди строчек. Следовательно, чтобы найти разрешающий алгоритм для формальных систем, необходимо решить проблему непредсказуемо длинного поиска - хаоса - среди строчек. Возможно, что в Арии с различными вариациями я преувеличил хаос в задачах о целых числах. [23]
Была поставлена задача построения по возможности более простых примеров. В этом направлении блестящий успех был достигнут ленинградским математиком Г, С. Цейтиным и насчитывающего всего лишь семь допустимых подстановок, проблема эквивалентности слов также алгоритмически неразрешима. В течение последних тридцати лет были выявлены и многие другие алгоритмические проблемы, для которых невозможен разрешающий алгоритм. Для некоторых из них это очень долго не удавалось установить, хотя они уже давно числились в списке кандидатов на алгоритмически неразрешимые проблемы. Лишь в конце 1969 г. молодому ленинградскому математику Ю. В. Мати-ясевичу удалось доказать, что эта знаменитая проблема алгоритмически неразрешима. [24]
Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью некоторой модификации синтаксического метода элиминации кванторов. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классическое исчисление предикатов, где эффективно описаны все разрешимые и неразрешимые классы формул, заданные в терминах расположения кванторов в формуле и вида предикатных символов, встречающихся в формуле. Описан ряд разрешимых фрагментов арифметического исчисления, элементарной теории множеств. [25]
Первый вопрос направлен на выяснение того, какие виды умственной работы могут выполнять автоматические вычислительные машины. Его актуальность и острота связаны, в частности, с тем, что достигнутые успехи могут породить и действительно порождают фантастические прогнозы и несбыточные иллюзии по поводу всемогущества машин ( гигантских электронных мозгов. Было строго доказано существование таких типов задач, для которых невозможен единый эффективный метод - алгоритм, - решающий все задачи данного типа; в этом смысле невозможно и машинное решение задач такого типа. С тех пор одной из главных целей теории алгоритмов ( и математики в целом) является исследование отдельных типов задач, возникающих в различных областях математики с целью выяснить, возможен ли для них разрешающий алгоритм. В этом направлении имеются очень крупные достижения, способствующие лучшему пониманию того, что могут делать машины и чего они не могут делать. [26]
Исчисление предикатов второй ступени в общем виде не только неразрешимо, но и ( как показал К. Гедель) не может иметь никакой полной системы аксиом. Тем не менее и в этом исчислении существуют довольно обширные разрешимые части. Такой частью является, например, так называемое исчисление И. В этом исчислении предметной областью служит множество всех натуральных чисел, а все предикаты - одноместные. Соответствующий результат был анонсирован Бюхи, который несколько ранее пбстроил разрешающий алгоритм для ослабленного варианта исчисления И, находящего применение в теории конечных автоматов. [27]
А выяснять, выводима ли А в этой теории или нет. Известно, что всякая формальная теория, содержащая нек-рый фрагмент теории рекурсивных функций, необходимо неразрешима. Отсюда следует неразрешимость элементарной арифметики, системы Цермело - Френкеля и многих других теорий. Примерами могут служить элементарная теория групп, теория двух отношений эквивалентности, элементарная теория частичного порядка. С другой стороны, имеются примеры интересных разрешимых теорий, таких, как элементарная геометрия, элементарная теория действительных чисел, теория множеств натуральных чисел с единственной операцией следования. Разрешимость теорий доказывается теоретико-модельными и синтаксич. Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью нек-рой модификации синтаксич. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классич. [28]
А выяснять, выводима ли А в этой теории или нет. Известно, что всякая формальная теория, содержащая нек-рый фрагмент теории рекурсивных функций, необходимо неразрешима. Отсюда следует неразрешимость элементарной арифметики, системы Цермело - Френкеля и многих других теорий. Примерами могут служить элементарная теория групп, теория двух отношений эквивалентности, элементарная теория частичного порядка. С другой стороны, имеются примеры интересных разрешимых теорий, таких, как элементарная геометрия, элементарная теория действительных чисел, теория множеств натуральных чисел с единственной операцией следования. Разрешимость теорий доказывается теоретико-модельными и синтаксич. Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью нек-рой модификации синтаксич. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классич. [29]