Каковы полезные пределы Линейных Ограниченных Автоматов по сравнению с Машинами Тьюринга?
Существуют языки, что Машина Тьюринга может обработать это, LBA не может, но быть там какими-либо полезными, практическими проблемами, которые не может решить LBAs, но ТМ могут?
LBA является просто Машина Тьюринга с конечной лентой, и фактические компьютеры имеют конечное устройство хранения данных, таким образом, мне казалось бы, что нет ничего из практического значения, что LBA не может сделать. За исключением того, что Автомат с линейно-ограниченной памятью не имеет просто конечной ленты, но и ленты с размером, это - линейная функция размера входа. Линейность ограниченности ограничивают LBA в некотором роде?
Есть ли проблемы, с которыми не может справиться LBA, но Экспоненциально Ограниченный автомат мог (если такие вещи существуют)?
2 ответа
Я рискну и скажу "нет". Практически каждый язык программирования, который мы используем сегодня, зависит от контекста. (На самом деле даже не контекстно-зависимый, только немного сильнее, чем контекстно-свободный, IIRC). И очевидно, что если мы не можем его запрограммировать, нас это особо не волнует ...
OTOH, все зависит от вашего определения «интересного» ... Функция Акермана явно попадает в эту категорию ... . это интересно?
Статья Википедии для контекстно-чувствительных языков утверждает, что любой рекурсивный Язык (то есть, узнаваемый на машине Turging), решение которого составляет EXPSPACE - не зависит от контекста, и поэтому не может быть признан LBA. Они Приведите пример такого языка: набор пар эквивалентных регулярных выражений, включая экспоненцию.