1

この初心者の質問で申し訳ありませんが、友人にそれが可能かどうかを伝えるために、簡単な回答が必要です.

4

3 に答える 3

6

わお。この質問への回答の多くは、そのようなことが何を意味するかを決定することに帰着します。

簡単な答えは「いいえ」です。

言語で書かれたプログラムを解釈できます。FSM を「解釈」することはできません。できることは、ある FSM を別の FSM にエミュレートさせることです。些細で面白くない方法で、FSM は自分自身をエミュレートできます。FSM は、それより小さい別の FSM をエミュレートするように設定することもできます。一般に、それよりも大きい FSM をエミュレートすることはできません。全体の状態が少なすぎて、より大きな FSM の状態を表すことができません。

FSM が自明ではない方法で自分自身をエミュレートすると見なすことができるかどうかは、セマンティクスにかかっています。シーケンス 1,1,1,1 を生成する FSM を考えてみましょう。次に、毎秒の出力を見てください。まったく同じ配列です。同じことが、5 つのステップ シーケンス 1,0,1,1,1 を繰り返し生成する FSM にも当てはまります。それ自体を解釈するインタープリターの興味深い動作 - 異なるスケールでのみまったく同じ出力が表示される - が存在します。それで、答えは「はい」になりますか？

その「フラクタル」特性自体は、そのような FSM が自己エミュレーターと呼ばれるに値するのに十分であると言えますが、自己インタープリターではありません。自己解釈者は、少なくとも賢明な定義については、より活力を持たなければなりません。

  • 言語 'HALT' を解釈するヌル インタープリターは、セルフ インタープリターとしてカウントされるべきではありません。言語はもっと複雑でなければなりません。上記の例では、FSM に十分なことを要求していません。入力を無視しています。
  • 自分自身を解釈できるインタープリターは、最小限の変更で同じ言語で記述された他のプログラムも解釈できるため、興味深いだけです (大まかに言えば、最小限の変更とは、別のプログラムを指すポインターのみを変更することを意味します)。

だから今問題。FSM は、プッシュダウン オートマトンと同様に、入力テープを逆戻りすることはできません。テープ上の入力記号をコンピューター言語のプログラムと見なすと、FSM もプッシュダウン オートマトンも、従来の意味でのインタープリターとしての資格を得ることができません。

ええと、FSM やプッシュダウン オートマトンを使用してチューリング完全な言語を解釈できないことは既にわかっていました。たとえば、任意の長さの繰り返しバイナリ パターンを生成できる、より制限的な言語についてはどうでしょうか。

3 つの命令を許可します。

  • OUT0 - 0 を出力
  • OUT1 - 1 を出力
  • RESTART - 最初に戻ります。

この言語で任意のプログラムの FSM を作成できます。それは本当に簡単です。この言語で任意のプログラムを解釈できる 1 つの FSM を作成することはできません。

同じことがプッシュダウン オートマトンにも当てはまります。シーケンスの特定のサイズを超えると、メモリにスタックを使用する必要があります。問題は、スタックから読み返すとすぐに、プッシュダウン オートマトンのスタック部分がそこにあったものを忘れてしまうことです。一方、FSM 部分は限られたサイズのシーケンスしか保存できません。

プッシュ ダウン オートマトンと FSM は、単純な 3 つの命令言語を解釈できません。固定 FSM またはプッシュダウン オートマトンがある言語で任意のプログラムを実行できる場合、その言語はチューリング完全でないだけでなく、与えられた言語よりも単純でなければなりません。これは非常に制限的であるため、FSM とプッシュダウン オートマトンは自己解釈できないと言うのが妥当です。

于 2011-03-13T14:15:35.307 に答える