-1
$\begingroup$

I tried, but I could not design a turing machine for the following problem:

Turing machine that takes as input a tape containing a series of n 1s, where n >= 0, terminated by an = sign. The Turing machine head is initially positioned on the leftmost 1. The end state should be a tape containing the input, followed by the reverse of the sequence of 0s and 1s that represents n in binary.

$\endgroup$
0
$\begingroup$

One approach you could take would be to effective reduce this to a machine that adds one to a binary number that is written left to right rather than right to left. Once you figure out that logic you'd just need to mark the end of the input and write a zero after that. Then for each 1 in the input, mark it and add one to the binary number found after the input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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