一元可以用在圖靈機嗎？

Question

給定一個一元數字（0 = 1,1 = 11,2 = 111,3 = 1111，...），在其後留下一個空白符號，並寫入相同數字的二進制表示（0 = 0， 1 = 1,2 = 10,3 = 11,4 = 100，...）。以相反的順序寫入數字是可以接受的（不是必需的）。完成後，TM應切換到接受狀態。不需要驗證輸入，假設輸入是100％一個一元數字，並且磁帶上沒有其他東西寫入。

Answer 1

這是一個基於Welbog提示的解決方案。

TM將在1s結束後寫入0空格開始。我們知道磁帶上至少會有一個1。然後，我們可以爲我們在第一個空白左邊看到的每個1添加一個二進制表示。我們可能還記得我們已經通過將它們更改爲0來處理哪個1。如果我們想讓磁帶恢復到原來的狀態，我們可以在二進制表示的左側將0寫回。

Q T Q' T' d 
----------------------- 
q0 1 q0 1  R // scan right to first blank space 
q0 # q1 #  R // after unary. then, write a 0 
q1 # q2 0  L // to start the binary. 

q2 # q3 #  L // scan left past any binary data 
q2 0 q2 0  L // to get to the blank separating 
q2 1 q2 1  L // unary and binary 

q3 # hA #  R // scan left for another unary 
q3 0 q3 0  L // digit, ignoring ones that have 
q3 1 q4 0  R // been processed. if done, halt. 

q4 # q5 #  R // scan right to the blank separating 
q4 0 q4 0  R // unary and binary 

q5 # q2 1  L // add one to the binary representation 
q5 0 q2 1  L // by toggling bits until you toggle a 
q5 1 q5 0  R // zero to a one, completing the addition 

例子：

#111#### => #111#### => #111#### => #111#### => (next line) 
^q0   ^q0   ^q0   ^q0 

#111#### => #111#0## => #111#0## => #110#0## => (next line) 
    ^q1   ^q2   ^q3   ^q4 

#110#0## => #110#1## => #110#1## => #110#1## => (next line) 
    ^q5   ^q2   ^q3   ^q3 

#100#1## => #100#1## => #100#1## => #100#0## => (next line) 
    ^q4   ^q4   ^q5   ^q5 

#100#01# => #100#01# => #100#01# => #100#01# => (next line) 
    ^q2   ^q2   ^q3   ^q3 

#100#01# => #000#01# => #000#01# => #000#01# => (next line) 
^q3   ^q4   ^q4   ^q4 

#000#01# => #000#11# => #000#11# => #000#11# => (next line) 
    ^q5   ^q2   ^q3   ^q3 

#000#11# => #000#11# => #000#11# 
^q3   ^q3   ^hA