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

Question

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

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

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

Answer 1

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

Answer 2

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

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