У меня сложилось впечатление, что наши компьютеры, будучи конечными, в конечном итоге не более мощные, чем (чрезвычайно большие) конечные автоматы. Тем не менее, линейно ограниченные машины Тьюринга также конечны, но кажется, что регулярные языки являются строго неподходящим подмножеством контекстно-зависимых языков.
Очевидно, я что-то здесь упускаю. Что происходит?
Я думаю, что мы должны сначала понять описание машины и размер ввода, чтобы сравнивать только действительные объекты. Допустим, N является входным размером. Это означает, что машины будут иметь эти границы ресурса.
Теперь, здесь более выразителен, чем . Это просто потому, что движение ленты и ограничения ограничены для .M A A
Теперь давайте сделаем недопустимое сравнение.
Здесь и имеют одинаковую выразительную силу. Но обратите внимание, что размер зависит от входных данных экспоненциальным образом. Ранее размер не зависит от . Это означает, что для каждого ввода в вам нужно будет генерировать новый FA, даже если остается неизменным.M A ′ N A N M MA′ M A′ N A N M M
источник