1

http://morphett.info/turing/turing.html

次のようなループ番号シーケンスを作成するにはどうすればよいですか。

01011011101111011111...

つまり、基本的にゼロを追加し、次に 1 を追加し、次にゼロを追加し、前の 1 の数の上に 1 を追加します。

4

1 に答える 1

1

01テープに書き込みます。右に 1 スペース移動します。ゼロを見ている場合は、ゼロが表示されるまで左にスキャンします。右に 1 スペース移動します。1 を見ている場合は、2 に置き換えて、0 が表示されるまで右に移動します。次に、別のゼロになるまで右に移動し続けます。このゼロを 1 に置き換えます。次に、2 が表示されるまで戻ります。2つを1つに置き換えます。1 つ右に移動します。1 を見ている場合は、2 に置き換えて元に戻すプロセスを繰り返します。最終的には、前の 1 の供給を使い果たすので、右に 1 を移動するとゼロが表示されます。その場合、次のゼロに右に移動し、1 に置き換えます。このプロセス全体 (「書き込み01部分」を除く) をループして、1 の長い文字列を取得します。

この背後にある直感は単純です。右に移動してゼロが表示された場合は、2 つのゼロを左に移動し、見つけたゼロの後の最後のゼロと最後から 2 番目のゼロの間のすべての 1 をコピーしてから、さらに 1 つ追加します。この 2 つは、コピーしている文字列内の位置を追跡する方法として使用されます。基本的な考え方は正しいですが、これを厳密にするために、状態と遷移を書き出してみる必要があります。

例:

>
^
>0
 ^
>01
  ^
>010
   ^
>010
 ^
>010
  ^
>020
   ^
>0200
    ^
>0201
   ^
>0201
  ^
>0101
   ^
>0101
    ^
>01010
     ^
>010110
      ^
于 2013-02-13T16:35:27.330 に答える