Cтраница 1
Детерминированная машина Тьюринга ( ДМТ) состоит из лепты, управляющего устройства и считывающей головки. [1]
Детерминированную машину Тьюринга М, распознающую язык А, можно построить, осуществив последовательную композицию ДМТ Mt, реализующей сведение / 1 к А, п ДМТ М2, распознающей язык А. Слово а в алфавите языка Аа перерабатывается ДМТ Ж4 в слово а в алфавите языка А плп в неопределенность. В последнем случае ясно, что аа. Слово а поступает затем на вход ДМТ Мг. [2]
Следствие 5.2. Если время работы детерминированной машины Тьюринга ограничено линейной функцией от длины входа, то такая обработка эквивалентна локально-конечной двухпроходовой обработке. [3]
Язык А называется полиномиально сводимым) к языку А, если существует детерминированная машина Тьюринга М, удовлетворяющая следующим условиям. Машина М имеет полиномиальную временную сложность и перерабатывает слова в алфавите языка А в слова в алфавите языка А так, что а А тогда и только тогда, когда М ( а) А. [4]
Обозначим через класс проблем ( языков), решаемых ( воспринимаемых) детерминированными машинами Тьюринга за полиномиальное время, в через / Г - класс проблем ( языков), решаемых ( воспринимаемых) недетерминированными машинами Тьюринга за полиномиальное время. [5]
Это легко проверить, посмотрев все правила; причина здесь в том, что правила моделируют работу детерминированной машины Тьюринга, в которой следующая конфигурация определена однозначно. [6]
Основным, ключевым понятием в теории NP-полных задач является недетерминированная машина Тьюринга ( НМТ), которая в отличие от детерминированной машины Тьюринга ( ДМТ) на каждом шаге осуществляет выбор дальнейшего продолжения. [7]
В классической работе Л. Г. Хачияна предложен полиномиальный алгоритм для задачи линейного программирования с целыми коэффициентами, т.е. показано, что задачу линейного программирования можно решить на детерминированной машине Тьюринга за полиномиальное от длины входа L время. Под длиной входа подразумевается число символов 0 и 1, достаточное для записи в двоичной системе всех коэффициентов задачи. [8]
В [6] Патерсон показывает, что при t ( n) n2 каждую t ( n) - ограниченную по времени недетерминированную однолен-точную машину Тьюринга можно промоделировать на л / 1 ( п) ленточно-ограничеиной детерминированной машине Тьюринга. Могут спросить, приводит ли комбинация теоремы 4 с результатами работы [3] об эффективном по объему памяти моделировании машин Тьюринга к результату Патерсона. Мы можем привести / ( п) 2 / 3-ленточно-ограниченное моделирование, но не видим очевидного способа получить границу Патерсона на основе нашего результата. [9]
При изучении моделей вычислений обычно проводят различие между детерминированными и недетерминированными машинами Тьюринга. В детерминированной машине Тьюринга общий ход вычислений полностью определяется машиной Тьюринга ( программой), начальным символом и начальными вводами с ленты. [10]
При изучении моделей вычислений обычно проводят различие между детерминистскими и недетерминистскими алгоритмами. В детерминированной машине Тьюринга общий ход вычислений полностью определяется машиной Тьюринга ( программой), начальным символом и начальными вводами с ленты; в недетерминированной машине Тьюринга на каждой стадии вычислений существуют альтернативы. [11]
Это определение представляется более узким, чем предыдущее, хотя не известно, приводят ли указанные два определения NP-полных языков к разным классам. Определение, основанное на сводимости, означает, что если М0 - детерминированная машина Тьюринга, распознающая NP-полный язык L0 за время Т ( п), то всякий язык из ЖЗ можно распознать за время Т ( р ( п)), где р - некоторый полином, с помощью детерминированной машины Тьюринга, которая обращается к Мй как к подпрограмме нуль или более раз. [12]
Если никакая последовательность шагов не приводит к допусканию входа, то детерминированное моделирование машины М могло бы продолжаться бесконечно долго, если только нет какой-нибудь априорной границы на длину кратчайшей допускающей последовательности. Поэтому естественно ожидать, что недетерминированные машины Тьюринга способны выполнять задания, которые никакие детерминированные машины Тьюринга не могут выполнить за то же время или с той же памятью. Тем не менее все еще открыт важный вопрос о существовании языков, допускаемых недетерминированной машиной Тьюринга с данной временной или емкостной сложностью, но не допускаемых никакой детерминированной машиной Тьюринга с той же сложностью. [13]
Понятие недетерминизма играет важную роль в определении вычислительной сложности алгоритмов ( С. Тьюринга способна завершить за приемлемое время такие расчеты, которые не могут быть реализованы столь же быстро никакой детерминированной машиной Тьюринга. [14]
Таким образом, AfP-полная задача - это задача, которая не менее трудна, чем любая задача из класса Л Р - задач. В настоящее время нет ответа на вопрос, может ли быть решена Л Р - полная задача за полиномиальное время на детерминированной машине Тьюринга, но так как эти задачи решались многими видными учеными не один десяток лет, то наиболее вероятной представляется гипотеза о невозможности такого решения. [15]