Каковы полезные пределы линейных ограниченных автоматов по сравнению с машинами Тьюринга?

Есть языки, с которыми машина Тьюринга может справиться, но с которыми не может справиться LBA, но есть ли какие-нибудь полезные практические проблемы, которые не может решить LBA, но могут решить TM?

LBA — это просто машина Тьюринга с ограниченной лентой, а настоящие компьютеры имеют ограниченную память, поэтому мне кажется, что нет ничего практически важного, чего бы LBA не могла сделать. За исключением того факта, что линейно-ограниченный автомат имеет не просто конечную ленту, а ленту, размер которой является линейной функцией размера входных данных. Линейность конечности как-то ограничивает LBA?

Существуют ли проблемы, с которыми не может справиться LBA, но может справиться экспоненциально ограниченный автомат (если такие вещи существуют)?


complexity-theory theory turing-machines automata
person Bribles    schedule 26.01.2010    source источник
comment
Есть TM, которые в настоящее время превышают 1 BF (BigaFlops). Теоретически, вы не можете получить намного быстрее, чем это!   -  person RAL    schedule 24.02.2010
comment
@Robert Lamb: очень смешно, но мой вопрос был серьезным. Поскольку ТМ построить невозможно, нам нужна некая точка отсчета, если мы собираемся задавать вопросы о практических проблемах.   -  person Beta    schedule 24.02.2010
comment
@Beta Для скорости я бы сказал, что разумно 10^x переходов состояний в секунду, при этом x = 9 +/- 3.   -  person Bribles    schedule 25.02.2010
comment
@Beta ммм, зачем нам вообще спрашивать о практических проблемах на машине Тьюринга? Если мы находимся на уровне ТМ, мы находимся в мире теории, а слово «практика» следует избегать B-)   -  person Brian Postow    schedule 03.03.2010
comment
Я опоздал с ответом, но моя точка зрения заключалась в том, что вопрос предвзят. Практичным было слово Брайблса, и TM может превзойти LBA только при решении огромных классов проблем, и то только при выполнении много шагов. В квантовой физике есть вопросы, на которые мы знаем, как ответить, но это заняло бы слишком много времени; TM может справиться со всем этим (в отличие от любого LBA), но сначала выгорит солнце.   -  person Beta    schedule 03.03.2010
comment
@Beta Вы все еще можете опубликовать ответ. И за него еще можно проголосовать.   -  person Bribles    schedule 03.03.2010

Ответы (2)


arrow_upward
2
arrow_downward

Я собираюсь рискнуть и сказать "нет". Практически каждый язык программирования, который мы используем сегодня, является контекстно-зависимым. (На самом деле даже не зависит от контекста, только немного сильнее, чем без контекста, IIRC). И, очевидно, если мы не можем это запрограммировать, нас это не особо волнует...

OTOH, это все зависит от вашего определения «интересного»… Функция Аккермана явно вписывается в эту категорию… это интересно?

person Brian Postow    schedule 24.02.2010
comment
Вы говорите, что функция Аккермана не может быть вычислена с помощью LBA? - person Bribles; 25.02.2010
comment
Я почти уверен, что у Акермана сложный PSpace, так что да, он не вычислим LBA... На самом деле это Primitive Recursive Complete, а это значит, что он даже сложнее, чем PSPACE... - person Brian Postow; 25.02.2010

arrow_upward
2
arrow_downward

В статье Википедии для контекстно-зависимых языков говорится, что любой рекурсивный язык (то есть распознаваемый машиной Тьюринга), чье решение EXPSPACE-hard не зависит от контекста и, следовательно, не может быть признанным LBA. Они приводят пример такого языка: набор пар эквивалентных регулярных выражений, включая возведение в степень.

person Jim Lewis    schedule 27.01.2010
comment
Я искал проблемы, отличные от принятия/отклонения рекурсивных или рекурсивно перечисляемых языков. - person Bribles; 27.01.2010
comment
@Bribles: трудно дать хорошо обоснованный, самодостаточный ответ на ваш вопрос, не приводя аргументов в пользу того, что предлагаемая проблема (а) разрешима, но (б) не вычислима с помощью LBA. И сведение вычислительной задачи к проблеме выбора языка — это техника для такого рода аргументов! - person Jim Lewis; 27.01.2010
comment
Связанный с этим вопрос заключается в том, необходима ли эквивалентность по Тьюрингу для языка программирования или абстрактной машины для реального мира или достаточно эквивалентности LBA. Интересно, есть ли что-то полезное в различии между линейным ограниченным автоматом и просто конечным автоматом. Есть ли что-то, что экспоненциально ограниченный автомат может сделать, чего не может сделать линейный автомат, что было бы важно для не-теоретиков? - person Bribles; 27.01.2010
comment
Большинство игр поддерживают PSPACE, включая Go, Chess и Mahjongg. Если p больше 1 (а это кажется так), то они не могут быть решены на LBA. - person Joel; 24.02.2010
comment
@Jim - рекурсивный язык (то есть распознаваемый машиной Тьюринга) - на самом деле рекурсивные языки являются подмножеством тех, которые могут быть распознаны ТМ, в частности, они могут быть распознаны ТМ, который останавливается для всех входных данных. Общая ТМ может не останавливаться для некоторых входных данных и связана с рекурсивно перечислимыми языками (надмножество рекурсивных языков). - person RAL; 24.02.2010
comment
@ Брайан Постоу, когда я писал просто конечные автоматы, я имел в виду нелинейные ограниченные автоматы. - person Bribles; 25.02.2010