ラムダトランジションがチューリングマシンにないのはなぜですか？

ラムダ遷移はチューリングマシンで定義されていませんか？その理由は何ですか？誰かが私を説明してください。ラムダトランジションがチューリングマシンにないのはなぜですか？

ありがとうございます。

2017-06-02 blackilDiamond

[lambda transition]（https://en.wikipedia.org/wiki/Lambda_transition）は、チューリングマシンとは無関係のようです... –

「計算理論」の私の最後のコースでは、以下のことを学びますシーケンス：ポンピング補題、有限オートマトン（DFA、NFS）、プッシュダウンオートマトン、チューリングマシン、決定的な問題、NP、NP完全。 NFAの "lambda transition"は事をもっとシンプルでクリーンにしますが、非常に複雑なチューリングモデルと結びつき、この質問を出すのは本当に悪いことではありません。 –

私の記憶は20年前から有効ですが、間違いがあれば修正してください！

NFAのラムダ移行についてお話ししていますか？ NFAにおけるラムダ遷移は、主にFAのみの複雑さを単純化することである。また、NFAをDFA s.tに変換する方法も学ぶ必要があります。決定論的であり、「機械」は、それを反映した形式的言語を処理するために、それを段階的に「実行」することができる。

チューリングマシンは、チューリング理論の下で抽象的なマシンであり、今日のコンピュータモデルのほとんど（量子コンピュータは、私たちの世界ではまれです）を除きます。私の理解では、Turing Machineは決定論的であり、タップを介して「計算」を実行します。内部には非決定的な要素はありません。

出典

2017-06-02 01:25:07

ありがとう、ええ、私はNFAのラムダトランジションについて取っています。そして、私はグーグルグーグルで、チューリングマシンが決定論的だと分かりました。この文章を少し説明してください。 "内部には確定的でない要素はありません" ありがとうございます。 – blackilDiamond

私の貧しい人の英語のために申し訳ありません。チューリングマシンではすべてが決定的でなければならないことを明確にしたい。一度ラムダトランジションが行われると、有効で可能な「次の状態」が2つ以上ある可能性があります。これにより、TMは次に何をすべきかを判断できなくなります。 –

とても感謝しています。 – blackilDiamond

ラムダトランジションがチューリングマシンにないのはなぜですか？

答えて

関連する問題