Можно ли написать интерпретирующий FSM или Pushdown Automaton?
Я прошу прощения за этот вопрос новичка, но мне нужен быстрый ответ, чтобы сказать другу, если это возможно.
3 ответа
Вот это да. Многие ответы на этот вопрос сводятся к решению, что означает такая вещь.
Быстрый ответ - "Нет".
Вы можете интерпретировать программу, написанную на языке. Вы не можете "интерпретировать" 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 или автомат с автоматическим управлением может выполнять произвольные программы на каком-либо языке, этот язык должен быть не только неполным по Тьюрингу, он должен быть проще, чем указанный. Это настолько ограничительно, что можно с полным основанием утверждать, что автоматические автоматы и автоматы не могут быть самоинтерпретируемыми.
FSM = летающий монстр спагетти?
Вы можете написать интерпретирующую себя машину Тьюринга, но ФСМ не является полной по Тьюрингу (насколько я помню), поэтому я думаю, что ответ - нет, вы не можете.
Да (самоинтерпретирующий конечный автомат)
Здесь есть очень короткая статья...
http://arxiv.org/abs/cs/0311032
но я не уверен, доступен ли он где-нибудь бесплатно.
Вот самоинтерпретатор для brainfuck -