Turing machine algorithm for counting 0 and write how many were in binary

Question

I need an algorithm for a turing machine that reads a string from 0 and then writes to tape how many were in binary format.

I understand that in practice, the machine will not actually count 0, but I'm pretty dumb about how to do this.

First of all, I want to mark the place where the binary number starts with X or something else, and then just write 1 for the first 0 and for each of the next 0, if the least significant bit is 0 it becomes 1, but what if it is 1 ? Maybe turn it into 0 and keep going, leaving all 1s to 0s until you find 0 or empty to turn into 1? Again, in this case, it is one and the same, regardless of LSB, because I will do the same, only 0 will be the first position ...

Hmm ... rubber duck ...

Answer 1

Suppose that the input tape #00000000000#, where the initial reading position is the first.

• Move right to the end #, maintaining the parity of the number of those encountered 0(initially 0, then 1, then 0, ...). Replace the first of 0each pair with -. Reading is -ignored and does not change parity.

• Write the parity of the output tape and move it to the left (to write the bit in order)

• Return the input head to the left #and go to 1.

At the end of the first pass, the input tape will be #-0-0-0-0-0-#, and the output will be 1.

At the end of the second pass: #---0---0---#and 11.

: #-------0---# 011.

: #-----------# 1011.

Answer 2

: .

, , , , , .

, 0.

1 , , , , , , ( 1) ( 1).

.

Answer 3

:

The Uber Turing machine allows you to program a Turing machine - a universal theoretical device that can be adapted to simulate the logic of any computer algorithm. Using this software, you can create new algorithms, as well as edit already prepared by someone through opening and changing them through a convenient visual development environment.