Turing Machine에서 단항 문자를 사용할 수 있습니까?

Question

숫자가 단항 (0 = 1, 1 = 11, 2 = 111, 3 = 1111, ...) 인 경우 하나의 공백 기호를 남겨두고 동일한 숫자 (0 = 1 = 1, 2 = 10, 3 = 11, 4 = 100, ...). 번호를 역순으로 쓰는 것은 허용 가능합니다 (필수는 아닙니다). 완료되면 TM은 수락 상태로 전환해야합니다. 입력을 검증 할 필요가 없으며, 입력이 단항 1 개의 100 %라고 가정하고, 그 밖의 것은 테이프에 기록되지 않습니다.

Answer 1

다음은 Welbog의 힌트를 기반으로 한 솔루션입니다.

TM은 1의 끝 뒤에 0 개의 공백을 쓰는 것으로 시작합니다. 우리는 테이프에 적어도 하나의 싱글이 있다는 것을 알고 있습니다. 그런 다음 첫 번째 공백의 왼쪽에 표시되는 각 1에 대해 이진 표현에 1을 더할 수 있습니다. 우리가 이미 처리 한 단항 1을 0으로 변경하여 기억할 수 있습니다. 우리가 작업을 마쳤던 것처럼 테이프를 되돌리고 싶다면 이진 표현의 왼쪽에있는 0에 1을 쓸 수 있습니다.

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 

다음