Impossible

From APIDesign

Revision as of 14:14, 20 October 2014

Explaining something is impossible, is well, impossible. Or at least almost impossible as following few stories show.

You Are the Expert!

Following viral video demonstrates the principle:

You are the expert! Can you do it? And don't tell us it is impossible, as that can only be explained as your own incapability.

Finite-state Machine

This story requires you to understand what a Finite-state automaton is and how it differs in capabilities from a pushdown automaton or at least from Turing machine - e.g. classical computer. This kind of knowledge should be approachable to every expert who studied computer science, or who studied lingustics and knows who Chomsky and his hierarchy is. I heard the story when I was studying MatFyz by Michal Chytil, who at the time was not only computer scientist, but also partner of Anderson Consulting in our country and his stories about business vs. science relation were absolutely revealing.

Imagine your are an expert in the area of Finite-state automatons. Your great reputation lead another potential customer to you and you are being asked to create a new Finite-state automaton that will:

Recognize words composed from 0 and 1 alphabet letters.
Accept words that start with some number of 0 and are followed by the same number of 1.
Reject all other words.

Your new automaton should then accept word like "01" or "000000000111111111" and reject words like "10" or "00010" or "001". What should you say to such customer?

The right answer is to say: "It's impossible!" Enough to read description of pushdown automaton to understand why, but of course, your customer is clueless and won't bother. Even if you try to explain what the problem is, you are only going to be seen as incapable. Moreover there is another company specialized in construction of Finite-state automatons and when your customer visits them, they (as good business men) say: "Of course, we'll build the automaton!"

Customer gets his machine and is happy. Competing company is happy too. Only your expert reputation is being damaged. But you know the automaton cannot work! So you visit the customer and ask for permission to use his automaton for a while and yes, after a little bit of time you find a word that is accepted, even it should not be. It is not a simple word, it has tens of zeros at beginning and even more ones at the end. But you'd done it! Satisfied you run to the customer to tell him, it is all a fake.

Customer is a bit worried and contacts the supplier of the machine, who sticks to the business note and admits there is a bug in his automaton which he is going to fix. In a few weeks a new automaton, ten times bigger than the old one, is being deployed to the customer and it fixes the so called bug: the incorrectly accepted word is not being rejected. Happiness all over. Except in your camp: you know it is just another bigger fake. It is impossible to create such finite automaton!

Hurrying to save your reputation, you ask the customer again for a permission to inspect the automaton. You study it for weeks and after that you finally find another incorrectly accepted word: this time is starts with thousands of zeros followed by even more ones. Exhausted, but happy you visit the customer. He finally listens to you and is ready to accept that the competing company is a gang of ignorants. But he still may not get it:

"OK, now I see the other company can't create the finite-state automaton properly. Can you please build it for us?"

Your expert credit is back. But the fact that something is impossible is somehow not getting through. What will be your answer this time?

To be continued...