Binary to unary turing machine

Question

How to implement a turing machine that converts the input from binary to unary?

Example: given input-$101 The output should be -1^5=11111

Answer 1

The problem statement does not specifically request a single-tape Turing machine, which greatly simplifies matters. Since we know that multi-tape Turing machines have equivalent single-tape machines to which they correspond, we'll just worry about the multi-tape definition and leave transforming it to a single-tape variety as an exercise.

We will use a three-tape Turing machine that works as follows:

1. The first tape is the input tape, and we'll just be reading from it.
2. Second tape is our scratch tape. We'll be recording the unary equivalent of whatever digit we're currently looking at in the input string here (so 1, 11, 1111, etc.)
3. Third tape is our output tape. We'll record our answer here.
4. We begin by going to the last symbol of the input tape. We also initialize the scratch tape with the value 1.
5. If the current value of the input tape we're looking at is 1, then we copy the scratch tape to the output tape; otherwise, we do nothing.
6. Move the input tape head one space to the left and copy the scratch tape to the end of the scratch tape itself, effectively doubling the number of 1s on it.
7. Return to step 5 and repeat until the input tape head is at blank at the front of the single-sided tape.*

Example of how this would work:

Input:
#101#  ######### ######
^      ^         ^

After initialization:
#101#  #1####### ######
   ^    ^        ^

After first iteration of steps 5 & 6
#101#  #11###### #1####
  ^    ^          ^

After second iteration of steps 5 & 6
#101#  #1111#### #1####
 ^     ^          ^

After third iteration of steps 5 & 6
#101#  #11111111 #111111#
^      ^               ^

• I always assume we have a marker at the front of single-sided tapes so we know not to go over the edge. If you don't want to assume this, you can always enforce it yourself by shifting the input over one space and writing a blank at the front of the input tape, as the first step before doing all the other stuff.