튜링 기계

example

• http://www.soc.napier.ac.uk/~andrew/tm/ryo.htm
• Unary increment - this function takes a string of 1's and adds another: 111→1111
• Unary decrement - this function takes a string of 1's and removes one: 111→11
• Binary double - this function doubles a binary string: 111→1110
• Binary increment - add one to a binary number: 101→110
• Unary double - double the length of a unary string 111→111111
• Palindrome cheker
• Binary addition

unary double

• x,1,a,R,y
• x,b,1,R,x
• x, , ,R,HALT
• y,1,1,R,y
• y,b,b,R,y
• y, ,b,L,z
• z,1,1,L,z
• z,b,b,L,z
• z,a,1,R,x