Если я правильно понимаю ваш вопрос, вы говорите о машине типа Тьюринга с лентой, ограниченной некоторыми постоянными (в вашем вопросе 1000) элементами окончательного алфавита. Длина ленты не зависит от размера ввода (что было бы в случае Linear Bounded Automoton).
В этом сценарии число состояний, которые вы можете представить на ленте, является постоянным. Более конкретно, если длина ленты T и размер алфавита A , то лента может кодировать только A T Состояния.
Кроме того, машина Тьюринга имеет некоторые внутренние состояния (скажем, число этих состояний S ). В каждой точке машина имеет некоторое внутреннее состояние и некоторое состояние ленты, поэтому мы можем смоделировать машину Тьюринга с лентой постоянной длины, используя обычный конечный автомат .
Чтобы построить конечный автомат, вам нужно принять все возможные состояния вашей ограниченной машины Тьюринга. Это комбинация внутренних состояний машины (их S ) и состояний ленты ( A T из них), поэтому вы в итоге получим конечный автомат с состояниями S * A T . Это довольно много, но в теории нас это не волнует - это константа.
Итак, мой ответ заключается в том, что ваша ограниченная машина Тьюринга с постоянной лентой может распознавать те же языки, что и конечный автомат.