Cтраница 2
Таким образом, в отношении проблемы разрешимости исчисление предикатов коренным образом отличается от исчисления высказываний. Впрочем, если ограничиться теми или иными частными видами формул, то разрешающий алгоритм может быть построен и в случае исчисления предикатов. [16]
Одно еще более серьезное упрощение теоретико-множественной проблемы разрешимости получается из геделевской теоремы о полноте1), которая утверждает, что всякая неопровержимая формула является выполнимой. [17]
Мы обсудим два подхода к проблеме разрешимости общего уравнения пятой степени, основанных на теории римановых поверхностей. [18]
Entscheidungsproblem) проблема остановки Одна из проблем разрешимости, исследовавшаяся Тьюрингом. Turing machine), на вход которой подается воздействие X. После запуска машины могут возникнуть две ситуации: машина остановится через конечное число шагов или машина будет работать бесконечно. Имеется ля возможность определить, какая из этих ситуаций реализуется на практике. В этом вопросе и содержится проблема остановки. На самом деле эффективная процедура определения возможности остановки заданной машины Тьюринга при - заданном входном воздействии отсутствует. О проблеме остановки известно, что она неразрешима. [19]
Примером ( р) служит решение проблемы разрешимости, найденное Ле-венгеймом [1915] ( упрощено Сколемом [1919]), а затем независимо Беманом [1922], для случая предикатных формул, содержащих только предикатные буквы с 0 или 1 аргументом. [20]
Наряду с попытками найти частные решения проблемы разрешимости для PrL, определенные усилия были затрачены на решение проблемы выполнимости формулы PrL, то есть на поиск алгоритмической процедуры, позволяющей определить, выполнима ли данная формула PrL или нет. [21]
Пост [1947] и Марков [1947] доказали неразрешимость проблемы разрешимости, представляющей интерес в качестве первого примера, в котором рассматривается проблема, возникшая не в области логики или оснований математики. [22]
Итак, опыт человека подсказывает другое решение проблемы разрешимости, состоящее в отказе от двузначной логики ДА / НЕТ и переходе к трехзначной логике: ДА, НЕТ, НЕ ЗНАЮ. В этом случае снимается ограничение рамками разрешимых множеств и открывается возможность наращивать концептуальную силу программ до существенно более высокого уровня. [23]
Следующая теорема играет ключевую роль для ряда проблем разрешимости, относящихся к системам векторного сложения. [24]
Такая же проблема для полугрупп прямо связана с проблемами разрешимости, касающимися / ( - рациональных степенных рядов. [25]
Ваном задача важна потому, что связана с проблемой разрешимости в математической логике. Ван предположил, что любой набор домино, которым можно замостить плоскость, позволяет построить периодическую мозаику, и показал, что если его гипотеза верна, то для задачи о построении мозаики существует решающая процедура. [26]
Эта формулировка особенно приспособлена для применений теоремы Эрбрана к проблеме разрешимости. [27]
Мы изложим здесь некоторые вопросы, связанные с теоретико-множественной трактовкой проблемы разрешимости. [28]
В настоящее время установлено большое число классов формул, для которых проблема разрешимости решается положительно. [29]
Следует подчеркнуть различие между чисто теоретическим и практическим подходом к решению проблемы разрешимости. В теоретическом плане важен прежде всего сам факт существования или несуществования разрешающей процедуры для того или иного класса формул. Процедуры разрешения, которые строятся для этой цели, в большинстве случаев оказываются совершенно не пригодными для автоматизации доказательств теорем, поскольку они приводят к чересчур громоздким и длинным построениям. [30]