Существование - алгоритм
Cтраница 2
Вопрос разрешимости эквивалентности схем программ тесно связан с существованием упрощающих алгоритмов. Если проблема эквивалентности разрешима, то в принципе существует алгоритм для сведения схемы к простейшей ( в некотором смысле) возможной форме. В разделах 4 и 5 мы показываем, что для почти всякого разумного - понятия эквивалентности между машинными программами оба вопроса: об эквивалентности и о неэквивалентности пары схем не являются частично разрешимыми. Здесь под частичной разрешимостью понимается рекурсивная перечислимость, а именно: отношение г ( а, Ъ) частично разрешимо, но не разрешимо, если существует алгоритм для порождения списка всех пар ( а, Ь), таких, что г ( а, Ъ) выполняется, но не существует алгоритма, перечисляющего все такие пары, для которых г ( а, Ь) не выполняется. Отсюда следует, что не существует оптимизирующих алгоритмов для полного сведения схемы &, так сказать, к кратчайшей возможной форме. Фактически, как будет показано, таких алгоритмов не существует даже в случае строго ограниченных классов схем. Доказательства используют некоторые свойства многоголовочных автоматов; последние рассматриваются в разд. [16]
В заключение этого раздела отметим, что вопрос о существовании алгоритма первого типа, который выясняет, является ли данное многообразие достаточно большим, естественным образом распадается на две части: является ли оно неприводимым и содержит ли оно несжимаемую поверхность. Проверка несжимаемости данной поверхности основана на том же методе, примененном к ее дополнению: поверхность сжимаема тогда и только тогда, когда среди фундаментальных поверхностей дополнения найдется нетривиальный сжимающий диск. [17]
Доказательство будет носить конструктивный характер в том смысле, что будет доказано существование алгоритма построения такого рода разбиения. Процедура ПОП, когда она приложима, образует новую пару в дополнение к уже построенным, а процедура ОПП применяется только тогда, когда ПОП не приложима. В этом случае ОПП также приводит к увеличению числа образованных пар k на единицу. [18]
Распределения с плотностью (2.180) образуют экспоненциальное семейство, для которого выполняются условия существования РНМ алгоритма обнаружения. [19]
Указанная нумерация группы R IH дает отрицательный ответ также на вопрос о существовании алгоритма, позволяющего в каждой конструктивной абелевой группе ранга 2 без кручения находить пару базисных элементов. Более точно: пусть U ( п, х, у) - универсальная частично рекурсивная функция Клини, при различных значениях п дающая всевозможные двуместные частично рекурсивные функции. Спрашивается, существуют ли общерекурсивные функции ф ( тг), i) ( п) такие, что если при некотором п функция U ( ft, х, у ] будет групповой операцией на множестве натуральных чисел, обращающей это множество в полную абелеву группу без кручения ранга 2, то числа ф ( ft), i) ( ft) будут линейно независимыми элементами этой группы. Из теоремы 3 вытекает отрицательный ответ на этот вопрос. [20]
Типичная массовая алгоритмическая проблема для формальных языков состоит в том, что требуется установить существование алгоритма, который для произвольного языка L, заданного порождающей грамматикой или другой порождающей системой, устанавливает, обладает ли этот язык некоторым свойством. Например, проблема принадлежности связана с проверкой, принадлежит ли произвольное слово а языку L; в проблеме пустоты следует выяснить, пусто ли множество L; в проблеме конечности задача состоит в выяснении, является ли L конечным множеством. [21]
Существование алгоритма для распознавания вложимости конечных частичных алгебр квазипримитивного класса К в обычные алгебры этого класса равносильно существованию алгоритма для решения проблемы тождества в обычных алгебрах класса К. [22]
Вопрос о существовании алгоритма, позволяющего распознавать разрешимость диофантовых уравнений в рациональных числах, эквивалентен вопросу о существовании алгоритма, позволяющего распознавать разрешимость однородных диофантовых уравнении в целых-числах. Эта важная проблема пока ( 1978) остается открытой и малоисследованной. [23]
 |
LR-распознаватель для грамматики Рн. [24] |
В работе [7], основанной на LR ( й) - грамматиках Кнута 127 ], говорится о существовании алгоритмов, имеющих такую же эффективность и значительно более общий характер. [25]
В определении полноты нумерации требуется не только разрешимость уравнения af ( т) am для каждой общерекурсивной функции /, но и существование алгоритма для нахождения решения. Если требовать только существование решения, то нумерацию можно называть формально полной. В доказательстве теоремы 2.3.5 используется только такая формальная полнота, и потому теорема справедлива для любых формально полных нумераций. [26]
Не для всякой вычислимой функции можно реально осуществить вычисление ее значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма. [27]
Один из способов состоит в построении, или вычислении, грокзводного объекта из исходного. Этот способ получения подразумевает существование алгоритма - правила, или предписания, убедительно описывающего отдельные шаги вычислительного процесса, приводящего к построению или нахождению производного объекта. Убедительность означает, что при выполнении алгоритма мы всегда можем выполнить любой очередной шаг, всегда точно зп.ем. какой шаг надо выполнить, всегда знаем, что наш процесс окончится. [28]
Иными словами, определенный морфизм - это такое отображение, когда одинаковые подсистемы имеют одинаковые образы. Существование определенного морфизма равносильно существованию однозначного алгоритма преобразования подсистем. [29]
 |
Четыре структуры данных, необходимые для алгоритма обнаружения тупиков. [30] |
Страницы: 1 2 3 4