シミュレーション非決定性チューリングマシン[JFLAP]

Question

問題：開始状態Q0、と＃記号で1平方以外は完全に空のテープを考えると、それに＃や停止を見つけます。

非決定：

このマシンには、左の検索または開始状態の右側するか選択し、次のシンボルは、それがままに＃記号、されるまで、その方向にいっています。決定論

：？

は、どのように私は決定論の形でこのマシンを複製するのですか？あなただけの上で実行していない...

Answer 1

を私はいくつかの研究を行ってきた、この問題は、「木」の両方の可能性/枝をアドレス指定することで解決することができるようだが、私はここで、ドットを接続するように見えることはできません非＃のセルですが、訪れたものとしてマークします。さらに、2つのブランチを交互に行うことで、2つのブランチを同時に実行します。右へ

1. マーク「+」と、現在のセル（それはすでに＃でない限り）
2. ランあなたは+を見ながら。最初の空白が表示されたら、+をマークします。
3. +が表示されている間、左に走ります。最初の空白が表示されたら、+をマークします。

このようにして、決まった数の確定的でない分岐を決定的に処理することができます。もちろん、実際のシミュレーションよりもはるかに時間がかかります。