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

João Fernandes picture João Fernandes · Jan 11, 2011 · Viewed 15.8k times · Source

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...

Answer

Eric Bainville picture Eric Bainville · Jan 12, 2011

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.