Ничего себе.Многие ответы на этот вопрос сводятся к решению, что означает такая вещь.
Быстрый ответ «Нет».
Вы можете интерпретировать программу написано на языке .Вы не можете «интерпретировать» FSM.Что вы можете сделать, это сделать один FSM подражать другому.Тривиальным и неинтересным способом FSM может подражать самому себе.FSM также может быть настроен для эмуляции другого FSM, который меньше его.Как правило, он не может эмулировать FSM, который больше его.В нем слишком мало штатов, чтобы представлять штаты более крупного FSM.
Можно ли считать, что ФСМ эмулирует себя нетривиальным образом зависит от семантики.Рассмотрим FSM, который генерирует последовательность 1,1,1,1.Теперь посмотрите на каждый второй вывод.Это точно такая же последовательность.То же самое касается FSM, генерирующего пятиступенчатую последовательность 1,0,1,1,1, многократно.Интригующее поведение интерпретатора, который интерпретирует себя - то, что вы видите один и тот же результат только в разных масштабах - присутствует.Так значит ли это, что ответ «Да»?
Это свойство «фрактала» само по себе, вероятно, достаточно для того, чтобы заслужить такую ФСМ, называемую самоэмулятором, но не самоинтерпретатором.Самоинтерпретатор, по крайней мере, для любого разумного определения, должен иметь больше слов.
- Нулевой интерпретатор, который интерпретирует язык 'HALT', не должен считаться самоинтерпретатором.Язык должен быть более сложным.В приведенных выше примерах мы не просим FSM сделать достаточно.Он игнорирует свои входные данные.
- Интерпретатор, который может интерпретировать себя, интересен только потому, что он также может интерпретировать другие программы, написанные на том же языке, с минимальными изменениями (грубо говоря, минимальное изменение означает изменение только указателя, указывающего надругая программа).
Так что теперь проблема.FSM и, в равной степени, автомат с нажатием кнопки вниз, не могут шагнуть назад в своей входной ленте.Если мы рассматриваем входные символы на ленте как программу на компьютерном языке, то ни ФСМ, ни автомат не могут считаться интерпретатором в общепринятом смысле.
Ну, мы уже знали, что не можем интерпретировать язык, полный по Тьюрингу, используя FSM или автомат.Как насчет более ограничительного языка, который может, скажем, генерировать повторяющийся двоичный шаблон произвольной длины?
Мы допускаем три инструкции:
- OUT0 - выводит 0
- OUT1 - выводит 1
- RESTART - возвращается в начало.
Мы можем написать FSM для любой программы на этом языке.Это действительно довольно просто.Мы не можем написать один FSM, который может интерпретировать любую программу на этом языке.
То же самое относится и к автомату.Вне определенного размера последовательности это должно использовать стек для памяти.Проблема в том, что, как только он считывает данные из стека, стековая часть автомата pushdown забывает, что там было.В то же время часть FSM может хранить только последовательность ограниченного размера.
Автомат с нажатием кнопки вниз и FSM не могут интерпретировать простые три языка инструкций.Если фиксированный FSM или автомат с автоматическим управлением могут выполнять произвольные программы на некотором языке, этот язык должен быть не только неполным по Тьюрингу, он должен быть проще, чем указанный.Это настолько ограничительно, что можно с полным основанием утверждать, что автоматы управления и автоматы не могут быть самоинтерпретируемыми.