I was given this problem:
9 bits binary code is given on input, we have to print "0" in output if amount of bits with value "1" are two times less than amount of bits with value "0", if this condition is false that we have to print "1" in output.
My idea was to introduce a counter, and then count bits that have value 1, then make an output based on this counter. But I was told that there's a way without the counter, and that I chose the hardest way. Does someone know the better way to determine what to output?
As the TM reads the input bits, the state number must capture the number of bits seen, from 0 through to 9, so that we can recognize when we get to the end, and the number of 1 bits seen, with the relevant cases being 0, 1, 2, 3, and >=4.
There are less than 10*5=50 states required to encode all the relevant possibilities. When the machine enters one of the states indicating that 9 input bits have been seen, it writes a 0 if it indicates that 3 1s have been seen, or 1 otherwise, then stops.
Note that we didn't need to use the tape for storage -- the input language is regular so it can be decided with a finite state machine and unbounded storage is unnecessary.