Разрешимое множество

Cтраница 3

Из [1] нам известно, что Q ( n) L ( n) означает, что все Q ( n) - разрешимые множества L ( n) - разрешимы, L ( n) Q ( n) означает, что класс Q ( n) - разрешимых множеств и класс L ( n) - разрешимых множеств одинаковы, и L ( n) Q ( n) означает, что некоторые Q ( n) - разрешимые множества не являются L ( n) - разрешимыми, если Q ( n) конструируема. [31]

Очевидно, не любое множество полуразрешимо, так как если X бесконечно, то множество всех подмножеств X несчетно, а множество полу разрешимых множеств счетно, так как счетно множество алгоритмов. [32]

Мы уже говорили, что перечислимые множества можно эквивалентно определить как проекции разрешимых множеств: множество А С N перечислимо тогда и только тогда, когда существует разрешимое множество В С С N х BJ, проекцией которого оно является. [33]

Неравенство означает, что L ( n) - Q ( n) / N для некоторого большого N, и потому L ( n) - ленточно разрешимым множеством автоматически является [ Q ( n) / Л - лен-точно разрешимое и, следовательно, Q ( n) - ленточно разрешимое. [34]

Второй вариант доказательства показывает, что верно следующее усиление этой теоремы: для любых различных вычислимых функций f и ф и любой главной универсальной функции U множества всех [ / - номеров функции if и функции ф не отделимы разрешимым множеством. Заметим, что эти множества не перечислимы, как мы впоследствии увидим. [35]

Разрешимое множество), то легко построить такой его В. Если же для данного отношения удастся построить слова, им не связанные, но по его инвариантам неотделимые, то тем самым будет доказана также и неразрешимость рассматриваемого отношения. [39]

При определении через род и видовое отличие задается нек-рая объемлющая совокупность объектов ( род) и указывается признак ( видовое отличие), выделяющий среди объектов указ, совокупности класс определяемых объектов. Тем самым разрешимые множества отождествляются с множествами, конструктивно определяемыми через род и видовое отличие. [40]

ПРОСТОЕ МНОЖЕСТВО - рекурсивно перечислимое множество натуральных чисел, дополнение к-рого есть иммунное множество. Рекурсивная теория множеств) между разрешимыми множествами и творческими ( креативными) множествами - последние являются наибрлыпими среди перечислимых множеств в смысле т - сводимости. [41]

Итак, опыт человека подсказывает другое решение проблемы разрешимости, состоящее в отказе от двузначной логики ДА / НЕТ и переходе к трехзначной логике: ДА, НЕТ, НЕ ЗНАЮ. В этом случае снимается ограничение рамками разрешимых множеств и открывается возможность наращивать концептуальную силу программ до существенно более высокого уровня. [42]

Дадим логическую интерпретацию свойств замкнутости рекурсивно перечислимых множеств. Если Е - рекурсивно перечислимое множество ( разрешимое множество), то Е ( х) - рекурсивно перечислимый ( разрешимый) предикат. [43]

Прежде чем объяснить, как доказывается теорема 3.9 о совпадении класса диофантовых множеств н класса перечислимых множеств, приведем несколько интересных приложений этой теоремы. Из логики известно существование перечисли-мых, но не разрешимых множеств. [44]

В рассмотренном примере потенциально бесконечное множество возможных выводов формулы F сводится к конечному числу F-наборов. В более сложных случаях прийти к конечному или бесконечному разрешимому множеству благоприятных наборов сложнее, однако схема доказательства в значительной степени сохраняется. В следующих параграфах эта схема детально развернута для доказательства разрешимости одного важного класса формул исчисления С. [45]

Страницы: 1 2 3 4