Cтраница 1
Сводимость играет большую роль для обеих из указанных проблем. Сводимость задач обычно используется для того, чтобы показать, разрешима ли задача или неразрешима. Наш подход к теории разрешимости [69, 200] основан главным образом на работах Тьюринга и его модели вычислений - машине Тьюринга. Значение машины Тьюринга состоит в том, что она служит разумным представлением вычислительной машины, и можно показать1), что не существует алгоритма, который бы решал определенные проблемы машины Тьюринга, в частности проблему остановки. На основе этого был найден ряд неразрешимых задач. И важность этой теории - в том, что невозможно создать программу для ЭВМ, которая бы решала эти задачи. Следовательно, для целей практического анализа необходимо избежать этих неразрешимых задач, иначе вопросы анализа не получат ответа. [1]
Сводимость Р к К имеет место всегда, а к Р не сводится ни одно разрешимое множество. [2]
Сводимость по Карпу также называют полиномиальной сводимостью, а часто - просто сводимостью. [3]
Сводимости и степени, между m и г лежит целый спектр сводимостей, подлежащих исследованию. Читатель, желающий глубже проникнуть в сводимость по Тьюрингу, должен основательно ознакомиться с доказательством теоремы Фрид-берга - Мучника, содержащей решение проблемы Поста, прежде чем перейти к дальнейшим результатам и доказательствам в этой области, некоторые из которых упоминались в гл. [4]
Рассматривается сводимость между сетями Петри, графами вычислений, семафорными системами, системами сложения векторов и системами замещения векторов. [5]
Используется сводимость к задаче достижимости сетей Петри для того, чтобы показать трудности анализа программ в распределенной среде. [6]
Свойства сводимости, аранжируе-мости и одновходовост. [7]
Определение сводимости по Тьюрингу ( напомним, что А сводится по Тьюрингу к В, если множество А разрешимо с оракулом для В) можно рассматривать как способ сравнивать задачи разрешения различных множеств по трудности. [8]
Что касается сводимости, то этот жупел не страшен. Дело заключается не в сводимости или несводимости, а в выходе на перекресток физики и биологии, в нахождении области их перекрывания. Конечно, никому не придет в голову утверждать, что кристалл кварца и живая лягушка не имеют качественных различий. Но познаваемы ли и кристалл и лягушка средствами единого точного естествознания. [9]
С целью сводимости и сопоставимости влияния различных факторов на себестоимость продукции рекомендуется распределять их по следующим группам: 1) изменение объема и структуры производственной программы; 2) повышение технического уровня производства; 3) повышение уровня организации производства и труда; 4) изменение природных условий; 5) народнохозяйственные и отраслевые факторы. [10]
Этот вид сводимости называется сводимостью по Тьюрингу, или Т - сводимостью. Обозначение: В т А означает, что В сводится по Тьюрингу к А. [11]
Основная идея сводимости состоит в следующем. Основной алфавит терминальных символов расширяется таким образом, что в каждом терминальном символе может запоминаться дополнительная информация ( состояния автоматов Нг и Я2 для каждого языка), характеризующая управляющие контексты. Условие принадлежности управляющего контекста определенным регулярным языкам заменяется на условие согласования дополнительной информации в ряде находящихся терминальных символах. [12]
Каждому понятию сводимости соответствует понятие эквивалентности множеств, которое является формализацией нашего интуитивного представления о том, : то два множества или две проблемы имеют одну и ту же степень сложности. [13]
Для доказательства сводимости проблемы живости к проблеме достижимости рассмотрим более детально свойства f - тупиковых разметок. [14]
Неразрешимость проблемы сводимости теории алгоритмов, Докл. [15]