http://morphett.info/turing/turing.html
次のようなループ番号シーケンスを作成するにはどうすればよいですか。
01011011101111011111...
つまり、基本的にゼロを追加し、次に 1 を追加し、次にゼロを追加し、前の 1 の数の上に 1 を追加します。
http://morphett.info/turing/turing.html
次のようなループ番号シーケンスを作成するにはどうすればよいですか。
01011011101111011111...
つまり、基本的にゼロを追加し、次に 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
^