Cтраница 4
Примерами могут служить проблемы разрешения в логике и проблемы существования или нахождения выигрывающих стратегий в комбинаторных играх. [46]
Стетмен [3] установил такой же результат для интуиционистской логики. Берман оценил сложность проблем разрешения теорий сложения вещественных и натуральных чисел, а Козен [14] выполнил аналогичную работу для элементарной теории булевых алгебр. [47]
Неразрешимые проблемы разрешения впервые были обнаружены при исследовании основ понятия алгоритма. Как правило, базисной проблемой разрешения является проблема остановки для машины Тьюринга. В ней ставится вопрос, существует ли алгоритм, который для любого слова в ленточном алфавите некоторой машины Тьюринга решает, остановится или нет эта машина, если она начнет работу в положении, когда читающая головка стоит у первого слева символа рассматриваемого слова, которое считается отпечатанным на ленте. [48]
Обратно, всякая массовая проблема, соответств. Отсюда ясна важная роль проблем разрешения. Среди проблем разрешения выделяются проблемы, поставленные для классов доказуемых формул исчислении. [49]
Ван X а о, На пути к механич. Некоторые вопросы, связанные с проблемой разрешения для исчисления строгой импликации Аккермана, в сб. [50]
Это определение особенно ориентирует нас на проблемы разрешения. [51]
В общем легче установить, почему задача обязательно требует так много квадратов ленты, чем почему она требует так много времени. В данной работе мы ограничимся изучением так называемых проблем разрешения, но, совершенно очевидно, эти методы можно распространить и на другие задачи. [52]