Cтраница 1
Стирнза не является конструктивным. А) требует экспоненциальной памяти, а следовательно, и времени. Идея доказательства этого факта состоит в следующем. Строится детерминированный алгоритм моделирования, который по данной машине Тьюринга, входу и экспоненциальной оценке памяти строит регулярное выражение, представляющее вычисление на заданной машине при данном входе. Это выражение задает регулярное событие ( О V 0 тогда и только тогда, когда машина Тьюринга не принимает данный вход в пределах выбранной оценки памяти. Отсюда следует, что проблема эквивалентности регулярных выражений с возведением в квадрат так же трудна, как любая проблема, разрешимая детерминированной машиной Тьюринга с экспоненциальной памятью. [1]
Первые примеры труднорешаемых разрешаемых задач были получены в начале 60 - х годов в работах Хартнаниса и Стирнза, а также позднее в работах Фишера и Рабина. [2]
Работы Хартманиса и Стирнза [2, 3] показывают, что уменьшение размерности ленты машины Тьюринга никогда не требует больше чем квадрата обычного времени вычисления. [3]
Множество входных последовательностей, распознаваемых М2, обозначим через В. Согласно Хартманису и Стирнзу [2, 3], переход от двумерной реализации к одномерной требует самое большее квадрата времени вычисления. Теперь мы желаем найти нижнюю границу времени вычисления одномерной машины, которая распознает В. [4]
Итак, для приведенного примера время наилучшего вычисления, которого можно достичь в случае одноленточной машины с записью на ленте, пропорционально квадрату времени наилучшего вычисления, которого можно достичь в случае двулен-точной машины. С другой стороны, из работы Хартманиса и Стирнза [2] известно, что если данная двуленточная машина завершает свои вычисления за Т2 ( п) единиц времени, то должна существовать одноленточная машина, которая завершает свои вычисления за время C [ Ti ( n) ] 2, где С-константа. Другими словами, переходя от двуленточной машины к одноленточной, никогда не нужно требовать более чем квадрата времени вычисления. Однако теперь мы имеем пример, в котором квадрат необходим. Таким образом, закон квадрата Хартманиса - Стирнза не может быть, вообще говоря, улучшен. [5]
Теорема сжимания представляет собой обращение теоремы ускорения. Она весьма напоминает теорему 9 в работе Харт-маниса и Стирнза [2], где показано, что у некоторых весьма сложных функций f число шагов, необходимых для их вычисления, можно сжать между двумя близкими границами. В этой статье доказана теорема совершенно общего характера, которая для случая одноленточных машин с алфавитом, состоящим из О, 1 и b ( пусто), имеющих двоичную кодировку входных и выходных данных, при функции Ф ( я), определенной как действительное число шагов при вычислении фг - ( / г), дает следующее. [6]
Первая попытка аксиоматического подхода к измерению трудности вычислений была сделана Рабином [3, 4], который аксиоматизировал понятие меры на доказательствах и длины вычисления функции и получил некоторые начальные результаты для этих мер. Первое систематическое исследование одной специфической меры сложности вычислений и изучение соответствующих классов сложности принадлежит Хартманису и Стирнзу [5, 6], которые дали также название сложность вычислений этой новой области исследований. В докладе Кобхэма [7] обсуждалась важность исследования количественных аспектов вычисления и приводились некоторые дальнейшие, результаты. [7]
К сожалению, я-ленточная машина, распознающая множество А за время 2L ( /), не всегда может быть заменена какой-либо m - ленточной машиной, работающей в реальном масштабе времени. Однако если такое сжатие г шагов в один шаг достаточно, чтобы ускорить машину Тьюринга до реального масштаба времени, то алгоритм Хартманиса и Стирнза [ 5, теорема 2 ] дает эффективный метод этого ускорения. В частности, если / г-ленточная машина Тьюринга воспринимает входную последовательность с постоянной скоростью, этот алгоритм дает нам эквивалентную гс - МРВ. Покажем теперь, что машина, определяющая V - l ( A) для А из R, относится к этому специальному виду. [8]
Первая часть теоремы доказывается легко. Читатель может восстановить доказательство самостоятельно, рассмотрев последовательность покрытий Ch, где Ck есть совокупность всех подмножеств из X, содержащих менее k состояний, или воспользовавшись леммой 7.5 из работы Хартманиса и Стирнза [ 1, с. Для того чтобы доказать более трудную часть теоремы, нужно, получить условия, при которых можно применить лемму о ретракте, позволяющую исследовать группы перестановок. Из-за этого приходится вступить на довольно сложный путь выбора покрытий. Разумеется, доказательство следует вести по индукции, но на каждом стандартном шаге ее возникают серьезные технические трудности и поэтому приходится прибегать к искусственным методам. [9]
В главе 4 излагается доказательство Зейгера теоремы Крона - Роудза о декомпозиции автомата. Оно основывается на аппарате теории покрытий. Возможно, это доказательство будет ближе читателям, знакомым с работами Хартманиса и Стирнза по декомпозиции автоматов. [10]
Эта работа касается определения нижних границ времени вычисления некоторых входно-выходных преобразований и взаимосвязи между временем вычисления и размерностью лент машины Тьюринга. Метод, использованный при установлении этой границы, применяется в разд. Этот результат обобщается в разд. Хартманиса - Стирнза [2, 3] не может быть значительно улучшен и что имеется существенная разница между размерностью и количеством лент машины Тьюринга. [11]
В то же время Т считывает очередной входной символ не более чем через с шагов на рабочих лентах. Прибавляя лишние холостые операции, можно добиться того, чтобы Т читала с постоянной скоростью с шагов на входной символ. Именно это и делает алгоритм Хартманиса и Стирнза. [12]
Итак, для приведенного примера время наилучшего вычисления, которого можно достичь в случае одноленточной машины с записью на ленте, пропорционально квадрату времени наилучшего вычисления, которого можно достичь в случае двулен-точной машины. С другой стороны, из работы Хартманиса и Стирнза [2] известно, что если данная двуленточная машина завершает свои вычисления за Т2 ( п) единиц времени, то должна существовать одноленточная машина, которая завершает свои вычисления за время C [ Ti ( n) ] 2, где С-константа. Другими словами, переходя от двуленточной машины к одноленточной, никогда не нужно требовать более чем квадрата времени вычисления. Однако теперь мы имеем пример, в котором квадрат необходим. Таким образом, закон квадрата Хартманиса - Стирнза не может быть, вообще говоря, улучшен. [13]
Стирнза не является конструктивным. А) требует экспоненциальной памяти, а следовательно, и времени. Идея доказательства этого факта состоит в следующем. Строится детерминированный алгоритм моделирования, который по данной машине Тьюринга, входу и экспоненциальной оценке памяти строит регулярное выражение, представляющее вычисление на заданной машине при данном входе. Это выражение задает регулярное событие ( О V 0 тогда и только тогда, когда машина Тьюринга не принимает данный вход в пределах выбранной оценки памяти. Отсюда следует, что проблема эквивалентности регулярных выражений с возведением в квадрат так же трудна, как любая проблема, разрешимая детерминированной машиной Тьюринга с экспоненциальной памятью. Стирнза вытекает, что существует проблема, которая может быть решена при объеме памяти 2, но не может быть решена при объеме памяти 2п / п, то проблема эквивалентности регулярных выражений с возведением в квадрат должна требовать экспоненциальной памяти. [14]