Turing machine algorithm to count 0's and write how many there were in binary

Question

I happen to need an algorithm for a turing machine that reads a string of 0's and then writes on the tape how many there were in binary.

I realize that in practice the machine won't actually count the 0's but I am pretty stumped as for how to do it.

I supose first of all I'd need to mark the place where the binary number starts with an X or something, then just write a 1 for the first 0 and for each of the following 0s if least significant bit is a 0 it becomes a 1 but what if it's a 1? Maybe turn it into 0 and keep going left turing all 1s into 0s until I find a 0 or blank to turn into 1? Then again, in that case it's the same thing regardless of the LSB because I'd be doing the same only the 0 would be the first position...

Hmm...rubber duckie...

Halfblooded

You do need to count. The output for 8 zeroes is very different fro the one for 7, and you can't know how many there are until you reach the end marker. In fact, you need one bit of memory (one state) for each bit in the binary representation of the count. – Pauperism

Not homework but college related (it's a problem I came across while studying) and the problem with counting is how do I store the counter? – Odum

You seem to have an algorithm that works. What's the problem? – Nimesh

Answer 1

Suppose the input tape is #00000000000#, where the initial read position is the first 0.

1. Move right until the end # is reached, maintaining the parity of the number of 0 encountered (initially 0, then 1, then 0,...). Replace the first 0 of each pair with a -. The - read are ignored and do not change the parity.

2. Write the parity to the output tape and move left (to write bits in order)

3. Return the input head to the left #, and goto 1.

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

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

At the end of the third pass: #-------0---# and 011.

At the end of the fourth pass: #-----------# and 1011.

Bartko

If I understand this correctly, you basically divide by two and round down on each pass? – Marymarya

Yes, exactly. Replacing the first 0 will round down correctly in all cases. – Bartko

So if I understand correctly this require 2 bits to model the 4 states of the data (i.e. #, 0, 1, -). And the internal state is just 1 bit to model the parity. Is that right? EDIT: I guess you may need additional state to model the MoveRight, MoveLeft instructions... – Yeeyegg

Answer 2

Edit: I concede to Bainville.

I figured out what I wanted to do last night and it required two separate turing machines and thats probably cheating.

The first machine's head would run over the input tape and simply start the second machine if it scanned a 0.

The second machine would simply be an adding machine and would add 1 to the current number, which is fairly easy to do, it's just long addition and you can create a state that says there is a remainder and continue moving left until you reach a zero (and replace it with 1) or find a blank spot (and create a 1).

Bainville wins my vote.

Pender

Answer 3

Check out this Turing machine simulator and its binary counting sample program:

Uber Turing Machine enables you to program the Turing machine - a universal theoretical device that can be adapted to simulate logic of any computer algorithm. With the help of this software you are able to create new algorithms, as well as edit already prepared by someone through opening and altering of them via the convenient visual IDE.

Isobath