Отображение естественных и распознаваемых языков в конечной машине Тьюринга
Я изо всех сил пытался найти ответ на этот теоретический вопрос, даже если это не прямой вопрос программирования, я считаю, что он действительно связан.
Предположим, что тип машины Тьюринга не может иметь более 1000 квадратов. Какова была бы связь между множеством таких распознаваемых языков и множеством нормальных распознаваемых языков?
4 ответа:
Если я правильно понял ваш вопрос, вы говорите о машине Тьюринга с лентой, которая ограничена некоторыми постоянными legnth (в вашем вопросе 1000) элементами конечного алфавита. Длина ленты не зависит от размера входного сигнала (что было бы справедливо для линейного ограниченного Автомотона).
В этом случае число состояний, которые можно представить лентой, является постоянным. Более конкретно, если длина ленты равна T и размер алфавит A тогда лента может кодировать только A T Штаты.
Кроме того, машина Тьюринга имеет некоторые внутренние состояния (допустим, что число этих состояний равно S). В каждой точке машина имеет некоторое внутреннее состояние и некоторое состояние ленты, поэтому мы можем моделировать машину Тьюринга с лентой постоянной длины, используя обычную конечную машину .
Чтобы построить конечный автомат, вам нужно будет взять все возможные состояния вашей ограниченной машины Тьюринга. Это комбинация внутренних состояний машины (существует S из них) и состояний ленты (A T из них), так что вы получите конечный автомат с S*A T Штаты. Это довольно много, но теоретически нас это не волнует - это константа.
Итак, мой ответ заключается в том, что ваша ограниченная машина Тьюринга с постоянной лентой может распознавать те же языки, что и конечность-государственная машина.
Я думаю, что то, что вы описываете, более близко к линейному ограниченному Автомотону, чем к машине Тьюринга. LBA может распознавать контекстно-зависимые языки.
Интуитивно я думаю, что ваши ограниченные машины могут распознавать строгое подмножество языков, распознаваемых по Тьюрингу. Чтобы доказать это, вам нужно построить распознаваемый язык Тьюринга таким образом, чтобы наиболее эффективная машина Тьюринга, которая распознает язык, требовала более 1000 позиций на своей ленте.