Почему линейно ограниченные машины Тьюринга более мощные, чем конечные автоматы?

11

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

Очевидно, я что-то здесь упускаю. Что происходит?

Бен И.
источник

Ответы:

21

Линейная ограниченная машина Тьюринга ограничена лентой, длина которой является линейной функцией длины входа.

Если бы предел длины был постоянным, то машина была бы не более мощной, чем DFA. Однако DFA не может увеличивать больше состояний, чтобы справиться с более длинным вводом, что в действительности может сделать LBTM (принимая состояние за всю конфигурацию машины). Таким образом, LBTM является строго более мощным.

RICi
источник
6
Есть интересный результат, связанный с этим. Любая машина Тьюринга, работающая в пространстве принимает обычный язык. o(loglogn)
skankhunt42
@ skankhunt42, почему это?
Бен I.
@ skankhunt42: Поправьте меня, если я ошибаюсь, но ... любая ТМ, работающая в пространстве должна выполняться в time. Но нетрудно показать, что любой TM, работающий за время выбирает язык, который также может быть выбран за время . Затем существует некоторая константа такая, что первые символов ввода определяют, является ли ввод на языке. Но тогда язык явно регулярный: просто включите состояние для каждого префикса в . Я что-то упускаю? Где моя ошибка? 2 k log log n = 2 log ( log k n ) = log k n o ( n ) O ( 1 ) c N c 0 i c { 0 , 1 } ikloglogn2kloglogn=2log(logkn)=logkno(n)O(1)cNc0ic{0,1}i
wchargin
@Choirbean Это требует доказательства с использованием пересечения последовательностей. Вы можете посмотреть его здесь cs.stackexchange.com/questions/7372/… .
skankhunt42
@wchargin Я думаю, что ошибкой может быть утверждение о том, что TM запускается за времени, потому что вам необходимо учитывать положение заголовка входной ленты также при подсчете количества конфигураций. Итак, я думаю, что ТМ работает за время . n 2 k log log n2kloglognn2kloglogn
skankhunt42
4

Я думаю, что мы должны сначала понять описание машины и размер ввода, чтобы сравнивать только действительные объекты. Допустим, N является входным размером. Это означает, что машины будут иметь эти границы ресурса.

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)MMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

Теперь, здесь более выразителен, чем . Это просто потому, что движение ленты и ограничения ограничены для .MAA

Теперь давайте сделаем недопустимое сравнение.

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)M×2NMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

Здесь и имеют одинаковую выразительную силу. Но обратите внимание, что размер зависит от входных данных экспоненциальным образом. Ранее размер не зависит от . Это означает, что для каждого ввода в вам нужно будет генерировать новый FA, даже если остается неизменным.M A N A N M MAMANANMM

Девендра Бхаве
источник