Вычислимость

Cтраница 2

Это равносильно вычислимости последовательности Ар. Теорема 1 показывает, что любое р-перечислимое или сильно р-перечислимое множество должно быть Лр-перечислимым. Следовательно, р-перечислимое или сильно р-перечислимое множество должно быть 1-перечислимым. Отсюда вывод, что если в качестве р брать только вычислимые действительные числа ( в частности, 1 / 2), то машина со случайным устройством не сможет перечислить ничего сверх того, что перечисляет детерминистская машина. [16]

Результаты относительно вычислимости последовательностей, приведенные в конце предыдущего раздела, остаются справедливыми для в.с. - машин. [17]

В статье Вычислимость примитивно рекурсивных термов конечного типа и примитивно рекурсивная реализация дается одно из первых в литературе доказательств сильной нормализуемости примитивно рекурсивных по Геделю А-термов конечных типов. [18]

Основное определение вычислимости у нас базируется на идеализированной вычислительной машине или машине с регистрами: при этом мы исходим из легкости, с которой такое изложение воспринимается лицами, изучающими предмет, большинство из которых знакомо с идеей компьютера. Такое знакомство, однако, не предполагается, хотя и является полезным, и еще меньше мы рассчитываем на какой бы то ни было практический опыт обращения с компьютерами или калькуляторами. Наш подход математически эквивалентен многим другим ранее предложенным подходам, включая подход, основанный на машинах Тьюринга, которому часто отдается предпочтение. Эквивалентность этих подходов мы обсудим в гл. [19]

Формальная теория вычислимости, или теория рекурсивных функций, занимается следующим вопросом: какие вычисления можно выполнить на машине, если игнорировать все технические ограничения, такие, как скорость выполнения операций и объем необходимой памяти. [20]

Безусловные предложения вычислимости в ТК Solver задаются в виде уравнений и программных отношений. [21]

Условные предложения вычислимости задают условия применимости тех или иных отношений и имеют две формы записи. [22]

Вышеописанная концепция вычислимости распространяется на функции действительного переменного. [23]

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

Вопрос о физической вычислимости отчасти зависит от того, какого рода информацию о данной системе мы хотим получить. Одним из таких вопросов мог бы быть следующий: столкнется ли когда-нибудь шарик А с шариком В. Чтобы придать задаче большую конкретность ( хотя и сделав ее при этом не особенно реалистичной), мы можем предположить, что все шарики имеют одинаковый радиус и одинаковую массу и что, скажем, сила, действующая между шариками, обратно пропорциональна квадрату расстояния между ними. В модели Фредкина-Тоффоли все основные логические операции компьютера могут выполняться с помощью шариков. [25]

Следующая теорема характеризует вычислимость по Посту. [26]

Преобразование вершин гиперсети в клики слабой инциденции. [27]

Аналогичным образом доказывается полиномиальная вычислимость задачи поиска слабой внешней Л - соединимости пары вершин в гиперсети S. [28]

Более сложное доказательство вычислимости г будет дано в гл. [29]

Следующая теорема выражает локально-конечную вычислимость через локально-конечные свойства. [30]

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