Может ли унарный использоваться в машине Тьюринга?

Question

Учитывая число в унарных (0 = 1, 1 = 11, 2 = 111, 3 = 1111, ...), после него оставляйте один пустой символ и записывайте двоичное представление того же числа (0 = 0, 1 = 1, 2 = 10, 3 = 11, 4 = 100, ...). Допустимо (не обязательно) записывать номер в обратном порядке. Когда это будет сделано, ТМ должна перейти в принимающее состояние. Нет необходимости проверять ввод, предположим, что вход 100% один унарный номер, и на ленте больше ничего не написано.

Answer 1

Это решение основано на подсказке Welbog.

TM начнется с записи 0-го пустого пространства после окончания 1-го. Мы знаем, что на ленте будет хотя бы один сингл. Затем мы можем добавить его к нашему двоичному представлению для каждого 1, которое мы видим слева от первого пробела. Мы также можем вспомнить, какие унарные 1 мы уже обработали, изменив их на 0. Если мы хотим вернуть ленту, как это было, когда мы закончили, мы можем записать 1s назад по 0s слева от двоичного представления.

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