圖靈機 - 生成數字序列

Question

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

我將如何創建循環數列如：

01011011101111011111 ...

所以基本上添零，然後加1，然後零，然後在前一個數字之上加1。

Answer 1

寫在磁帶上的01。向右移動一個空格。如果您正在查看零點，請回到左側，直到看到零點。向右移動一個空格。如果你正在看一個，用兩個替換它，然後向右移動，直到看到一個零;然後繼續向右移動直到另一個零。用一個替換這個零。然後，移回去，直到看到兩個。用一個替換兩個。向右移動一個;如果你正在看一個，重複用兩個替換的過程，然後再回來。最終，您將耗盡先前的1，所以當您向右移動時，您正在查看零點。在這種情況下，向右移動到下一個零，並用一個替換它。在整個過程中循環（減去「寫01」部分）以獲得更長的字符串

直覺背後很簡單，如果你向右移動並看到一個零，向左移動兩個零，所有人在你找到的零之後的最後一個零和倒數第二個零之間，然後再添加一個，這兩個用於跟蹤你在複製的字符串中的位置。基本思路是合理的，但你應該嘗試寫出來的狀態和轉換這使它嚴格

例：

> 
^ 
>0 
^ 
>01 
^
>010 
^
>010 
^ 
>010 
^
>020 
^
>0200 
    ^
>0201 
^
>0201 
^
>0101 
^
>0101 
    ^
>01010 
    ^
>010110 
    ^