I want to implement following algorithm on Turing machine:
rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars
But I don't know how to make the replacement "|0" -> "0||" because it requires 3 cells. Basically I want to insert additional cell or shift all cell symbols from current position to the left(right). Is there a simple way of doing it?
Asked By : pusheax
Answered By : ruler501
The way I'd do it is as follows: The syntax is from the Turing simulator I link to below. It is
[transition name],[symbol] [next transition],[new symbol],[direction]
The actual code:
name: Binary to Unary init: moveright2 accept: end moveright2,_ moveright1,_,> moveright2,0 moveright2,0,> moveright2,1 moveright2,1,> moveright1,_ moveleft,1,< moveright1,0 moveright1,0,> moveright1,1 moveright1,1,> moveleft,_ sub1,_,< moveleft,0 moveleft,0,< moveleft,1 moveleft,1,< sub1,0 sub1,1,< sub1,1 moveright2,0,> sub1,_ blankout2,_,> blankout2,_ blankout1,_,> blankout2,1 blankout2,_,> blankout1,1 end,_,>
Basically move till you've passed two blanks(Step 1), then write a 1(Step 2), move left till you find a blank(Step 3), treat the number to the left as a binary number and subtract one from it(see below for details on how this works)(Step 4), Then repeat steps 1-4 until you can't subtract any more(in my case the subtract routine turns all 0's in the number we've been subtracting from to 1 and then hits a blank), go back turning all ones to blanks till you hit a blank, then go one farther turning that one into a blank.
It turns 101 into 11111
Subtraction routine, start at the far right of the number, if it's 0 change it to one and move left doing the same thing to each digit you come across, if it's one see step 1
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42013
0 comments:
Post a Comment
Let us know your responses and feedback