[Solved]: How to replace one symbol with two on Turing machine's tape

Problem Detail: 

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

(wikipedia)

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