http://wiki.apidesign.org/wiki/Impossible
I had a look at this and I do not understand why this problem seems to be impossible. String given to the "machine" will be always finite right?
So even if I have 1 billion zeros, and 1 billion ones, one could easily write a script that returns true or false for that string (which it will be true/accepted).
Another input could be a "00011" which makes it invalid.
I probably didn't understand something here, but this problem seems "codeable" to me.
When you say "codeable", you mean it is codeable using a computer which can be considered as a version of Turing Machine (implicitly with unlimited memory). But Finite State Machines do not have unlimited memory (say 1 billion states), when they are fed with a 1 billion and 1 zeros, they lose track of number of zeros (forget) and can not match it with equal number of ones. A complete argument could be established using a pumping lemma for regular languages: http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages