Single tape TM that converts numbers from binary notation to unary

Question

I need to construct a TM that converts a number from binary notation to unary and calculate time complexity. 

I have done the first part.

The idea is as follows:

binary number is decremented by 1 until it reaches 0. At each decrement an additional 1 is written on the left side.

e.g.

111 -> 1111111 111x (TM goes to the end of the binary number and writes x)
110x1
101x11
100x111
011x1111
010x11111
001x111111
000x1111111
1111111 (TM removes zeros and x; end)

And now comes the time complexity part. So far I have:
(1) TM will do $n$ (length of the binary number) steps to reach the end of the input word, additional 1 for writing x and 1 for moving back, so $n+2$;
(2) there are $2^{n}-1$ decrements, at that time TM will take in total $2 \times \frac{(2^{n}-1) (2^{n})}{2}$ steps on the left side, plus $2\times (2^{n}-1)$ for the x's. (no idea how many on the right side).
(3) TM will take $2n+1$ steps for removing unnecessary zeros and x at the end.

I don't know how to put this all together, plus some missing information in (2). Can anyone tell me if I'm computing correctly and how to proceed.

Any help will be much appreciated.

Answer 1

As you have said, there are $2^n-1$ total "decrements". Notice that at the $k$'th decrement, you "waste" $O(n)$ time on the left side, plus $O(k)$ at the right side. Sum everything up, from $k=1$ up to $k=2^n-1$:

$\sum_{k=1}^{2^n-1} n+k = n(2^n-1)+\sum_{k=1}^{2^n-1} k = n(2^n-1) + O(2^{2n})=O(2^{2n})$

Answer 2

put this code into https://turingmachine.io/

name: Binary to Decimal
source code: |
  input: '100#'
  blank: ' '
  B : ' '
  start state : Right
  table:
    Right : 
      [0,1] : R
      '#' : {L : q0}
    q0:
      0 : {write : 1, L}
      1 : {write : 0, R : q1}
      ' ' : {R : clear}
    q1:
      [0,1] : R
      '#' : {R : q2}
    q2 :
      ' ' : {write : 1, L : q3}
      1 : R
      '#' : {L : q3}
    q3:
      1 : L
      '#' : {L : q0}
    clear : 
      1 : {write : ' ', R}
positions:
  Right: {x: 123.15, y: 317.95}
  q0: {x: 158.84, y: 165.35}
  q1: {x: 339.94, y: 121.45}
  q2: {x: 477.32, y: 257.12}
  q3: {x: 353.45, y: 344.81}
  clear: {x: 34.35, y: 168.07}