1

「0^n1^n2^n の形式の文字列を認識するためのチューリング マシンを作成する」という指示がありました。これは、文字列が正しい形式であれば、チューリング マシンは空白のテープで停止し、そうでない場合は停止することを意味します。正しい形式の場合、空白でないセルで停止します。」

チューリング マシンの仕組みの基本は知っていますが、Python でチューリング マシンを実装する方法はわかりません。私がオンラインで見つけた例はすべて、複数のクラスとすべてを含む非常に複雑に見えます。私のアプリケーションにとって、それが完全に必要または期待されているとは思いません。

この問題に対して、次の疑似コードを見つけました。

On input string w
   while there are unmarked 0s, do
      Mark the left most 0
      Scan right to reach the leftmost unmarked 1;
         if there is no such 1 then crash
      Mark the leftmost 1
      Scan right to reach the leftmost unmarked 2;
         if there is no such 2 then crash
      Mark the leftmost 2
   done
   Check to see that there are no unmarked 1s or 2s;
      if there are then crash
   accept

しかし、この正確な疑似コードを実装しても、実際には正当なチューリング マシンにはならないように思えます。私はこれについて間違った方法で進んでいますか？任意のガイダンスをいただければ幸いです。

4

1 に答える 1

0

その疑似コードは私には正しいと思われます。あまり複雑でない問題で何が受け入れられるかの例を示していただければ役立つかもしれません.PythonのTMで何が受け入れられているのか正確にはわかりません.

于 2012-12-23T18:41:47.657 に答える