2
$\begingroup$

I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It also has to have a runtime of O(N).

So I can prove that the number of "flips" (changing a 0 to a 1 or a 1 to a 0) that occur when counting from 1 to n in base 2 approaches 2n as n goes to infinity. meaning it's O(n) in terms of runtime, but i'm not sure how to factor in the movement of the head of the tape that is writing the binary. Near as I can tell, the head may have to move at most log(n) place to go from the 1s place to the last power of 2s place. For example, going from 11111 to 000001 requires moving from the 1s to the 64s place, or 6 places. It then has to move back to the ones to create the binary representation for 65.

How is this operation as a not O(nlogn)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. Flip it to 1 and move back to LSB, stop. It is then clear that the total move distance is just double the number of flips.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For some reason I was visualizing flips wrong, despite already doing the first part of proving a total of 2n for flips. This makes everything snap into place :) thank you very much. $\endgroup$
    – Sveniat
    Commented Sep 7, 2015 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.