The Parable of the Black Belt

Picture a martial artist kneeling before the master sensei in a ceremony to receive a hard-earned black belt. After years of relentless training, the student has finally reached a pinnacle of achievement in the discipline.

"Before granting the belt, you must pass one more test," says the sensei.

"I am ready," responds the student, expecting perhaps one final round of sparring.

"You must answer the essential question: What is the true meaning of the black belt?"

"The end of my journey," says the student. "A well-deserved reward for all my hard work."

The sensei waits for more. Clearly, he is not satisfied. Finally, the sensei speaks. "You are not yet ready for the black belt. Return in one year."

A year later, the student kneels again in front of the sensei.

"What is the true meaning of the black belt?" asks the sensei.

"A symbol of distinction and the highest achievement in our art," says the student.

The sensei says nothing for many minutes, waiting. Clearly, he is not satisfied. Finally, he speaks. "You are still not ready for the black belt. Return in one year."

A year later, the student kneels once again in front of the sensei. And again the sensei asks:

"What is the true meaning of the black belt?"

"The black belt represents the beginning -- the start of a never-ending journey of discipline, work, and the pursuit of an ever-higher standard," says the student.

"Yes. You are now ready to receive the black belt and begin your work."

- From the book "Built to Last: Successful Habits of Visionary Companies" by James Collins and Jerry Porras

Martin discovers infinite recursion

On his next trip down to the dungeon Martin brought with him a parchment scroll. ‘‘Look dragon,’’ he called, ‘‘someone else must know about recursion. I found this scroll in the alchemist’s library.’’

The dragon peered suspiciously as Martin unrolled the scroll, placing a candlestick at each end to hold it flat. ‘‘This scroll makes no sense,’’ the dragon said. ‘‘For one thing, it’s got far too many parentheses.’’

‘‘The writing is a little strange,’’ Martin agreed, ‘‘but I think I’ve figured out the message. It’s an algorithm for computing Fibonacci numbers.’’

‘‘I already know how to compute Fibonacci numbers,’’ said the dragon.

‘‘Oh? How?’’

‘‘Why, I wouldn’t dream of spoiling the fun by telling you,’’ the dragon replied.

‘‘I didn’t think you would,’’ Martin shot back. ‘‘But the scroll says that Fib of n equals Fib of n-1 plus Fib of n-2. That’s a recursive definition, and I already know how to work with recursion.’’

‘‘What else does the scroll say?’’ the dragon asked.

‘‘Nothing else. Should it say more?’’

Suddenly the dragon assumed a most ingratiating tone. Martin found the change startling. ‘‘Dearest boy! Would you do a poor old dragon one tiny little favor? Compute a Fibonacci number for me. I promise to only ask you for a small one.’’

‘‘Well, I’m supposed to be upstairs now, cleaning the cauldrons,’’ Martin began, but seeing the hurt look on the dragon’s face he added, ‘‘but I guess I have time for a small one.’’

‘‘You won’t regret it,’’ promised the dragon. ‘‘Tell me: What is Fib of four?’’

Martin traced his translation of the Fibonacci algorithm in the dust:

Fib(n) = Fib(n-1) + Fib(n-2)

Then he began to compute Fib of four:

Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)
Fib(2) = Fib(1) + Fib(0)
Fib(1) = Fib(0) + Fib(-1)
Fib(0) = Fib(-1) + Fib(-2)
Fib(-1) = Fib(-2) + Fib(-3)
Fib(-2) = Fib(-3) + Fib(-4)
Fib(-3) = Fib(-4) + Fib(-5)

‘‘Finished?’’ the dragon asked innocently.

‘‘No,’’ Martin replied. ‘‘Something is wrong. The numbers are becoming increasingly negative.’’

‘‘Well, will you be finished soon?’’

‘‘It looks like I won’t ever be finished,’’ Martin said. ‘‘This recursion keeps going on forever.’’

‘‘Aha! You see? You’re stuck in an infinite recursion!’’ the dragon gloated. ‘‘I noticed it at once.’’
‘‘Then why didn’t you say something?’’ Martin demanded.

The dragon grimaced and gave a little snort; blue flame appeared briefly in its nostrils. ‘‘How will you ever come to master recursion if you rely on a dragon to do your thinking for you?’’

Martin wasn’t afraid, but he stepped back a bit anyway to let the smoke clear. ‘‘Well, how did you spot the problem so quickly, dragon?’’

‘‘Elementary, boy. The scroll told how to take a single step, and how to break the journey down to a smaller one. It said nothing at all about when you get to stop. Ergo,’’ the dragon grinned, ‘‘you don’t.’’

The End
_________________________

Here ends the story of Martin. Kudos to its original author David Touretzky, a prof at CMU.

The Dragon's Dream

The next time Martin returned to the dungeon, he found the dragon rubbing its eyes, as if it had just awakened from a long sleep.

‘‘I had a most curious dream,’’ the dragon said. ‘‘It was a recursive dream, in fact. Would you like to hear about it?’’

Martin was stunned to find the dragon in something resembling a friendly mood. He forgot all about the alchemist’s latest problem. ‘‘Yes, please do tell me about your dream,’’ he said.

‘‘Very well,’’ began the dragon. ‘‘Last night I was looking at a long loaf of bread, and I wondered how many slices it would make. To answer my question I actually went and cut one slice from the loaf. I had one slice, and one slightly shorter loaf of bread, but no answer. I puzzled over the problem until I fell asleep.’’

‘‘And that’s when you had the dream?’’ Martin asked.

‘‘Yes, a very curious one. I dreamt about another dragon who had a loaf of bread just like mine, except his was a slice shorter. And he too wanted to know how many slices his loaf would make, but he had the same problem I did. He cut off a slice, like me, and stared at the remaining loaf, like me, and then he fell asleep like me as well.’’

‘‘So neither one of you found the answer,’’ Martin said disappointedly.

‘‘You don’t know how long your loaf is, and you don’t know how long his is either, except that it’s one slice shorter than yours.’’

‘‘But I’m not done yet,’’ the dragon said. ‘‘When the dragon in my dream fell asleep, he had a dream as well. He dreamt about—if you can imagine this—a dragon whose loaf of bread was one slice shorter than his own loaf. And this dragon also wanted to find out how many slices his loaf would make, and he tried to find out by cutting a slice, but that didn’t tell him the answer,
so he fell asleep thinking about it.’’

‘‘Dreams within dreams!!’’ Martin exclaimed. ‘‘You’re making my head swim. Did that last dragon have a dream as well?’’

‘‘Yes, and he wasn’t the last either. Each dragon dreamt of a dragon with a loaf one slice shorter than his own. I was piling up a pretty deep stack of dreams there.’’

‘‘How did you manage to wake up then?’’ Martin asked.

‘‘Well,’’ the dragon said, ‘‘eventually one of the dragons dreamt of a dragon whose loaf was so small it wasn’t there at all. You might call it ‘the empty loaf.’ That dragon could see his loaf contained no slices, so he knew the answer to his question was zero; he didn’t fall asleep.

‘‘When the dragon who dreamt of that dragon woke up, he knew that since his own loaf was one slice longer, it must be exactly one slice long. So he awoke knowing the answer to his question.

‘‘And, when the dragon who dreamt of that dragon woke up, he knew that his loaf had to be two slices long, since it was one slice longer than that of the dragon he dreamt about. And when the dragon who dreamt of him woke up...."

‘‘I get it!’’ Martin said. ‘‘He added one to the length of the loaf of the dragon he dreamed about, and that answered his own question. And when you finally woke up, you had the answer to yours. How many slices did your loaf make?’’

‘‘Twenty-seven,’’ said the dragon. ‘‘It was a very long dream.’’

Martin visits the dragon again

‘‘Hello Dragon!’’ Martin called as he made his way down the rickety dungeon staircase.

‘‘Hmmmph! You again. I’m on to your recursive tricks.’’ The dragon did not sound glad to see him.

‘‘I’m supposed to find out what five factorial is,’’ Martin said. ‘‘What’s factorial mean, anyway?’’

At this the dragon put on a most offended air and said, ‘‘I’m not going to tell you. Look it up in a book.’’

‘‘All right,’’ said Martin. ‘‘Just tell me what five factorial is and I’ll leave you alone.’’

‘‘You don’t know what factorial means, but you want me to tell you what factorial of five is??? All right buster, I’ll tell you, not that it will do you any good. Factorial of five is five times factorial of four. I hope you’re satisfied. Don’t forget to bolt the door on your way out.’’

‘‘But what’s factorial of four?’’ asked Martin, not at all pleased with the dragon’s evasiveness.

‘‘Factorial of four? Why, it’s four times factorial of three, of course.’’

‘‘And I suppose you’re going to tell me that factorial of three is three times factorial of two,’’ Martin said.

‘‘What a clever boy you are!’’ said the dragon. ‘‘Now go away.’’

‘‘Not yet,’’ Martin replied. ‘‘Factorial of two is two times factorial of one.

Factorial of one is one times factorial of zero. Now what?’’

‘‘Factorial of zero is one,’’ said the dragon. ‘‘That’s really all you ever need to remember about factorials.’’

‘‘Hmmm,’’ said Martin. ‘‘There’s a pattern to this factorial function. Perhaps I should write down the steps I’ve gone through.’’ Here is what he wrote:

Factorial(5) = 5 x Factorial(4)
= 5 x 4 x Factorial(3)
= 5 x 4 x 3 x Factorial(2)
= 5 x 4 x 3 X 2 x Factorial(1)
= 5 x 4 x 3 x 2 x 1 x Factorial(0)
= 5 x 4 x 3 x 2 x 1 x 1

‘‘Well,’’ said the dragon, ‘‘you’ve recursed all the way down to factorial of zero, which you know is one. Now why don’t you try working your way back up to....’’

When it realized what it was doing, the dragon stopped in mid-sentence. Dragons aren’t supposed to be helpful.

Martin started to write again:
1 x 1= 1
2 x 1 x 1= 2
3 x 2 x 1 x 1= 6
4 x 3 x 2 x 1 x 1= 24
5 x 4 x 3 x 2 x 1 x 1= 120

‘‘Hey!’’ Martin yelped. ‘‘Factorial of 5 is 120. That’s the answer! Thanks!!’’

‘‘I didn’t tell you the answer,’’ the dragon said testily. ‘‘I only told you that factorial of zero is one, and factorial of n is n times factorial of n-1. You did the rest yourself. Recursively, I might add.’’

‘‘That’s true,’’ said Martin. ‘‘Now if I only knew what ‘recursively’ really meant.’’

Martin and the dragon

In ancient times, before computers were invented, alchemists studied the mystical properties of numbers. Lacking computers, they had to rely on dragons to do their work for them. The dragons were clever beasts, but also lazy and bad-tempered. The worst ones would sometimes burn their keeper to a crisp with a single fiery belch. But most dragons were merely uncooperative, as violence required too much energy. This is the story of how Martin, an alchemist’s apprentice, discovered recursion by outsmarting a lazy dragon.

One day the alchemist gave Martin a list of numbers and sent him down to the dungeon to ask the dragon if any were odd. Martin had never been to the dungeon before. He took a candle down with him, and in the furthest, darkest corner found an old dragon, none too friendly looking. Timidly, he stepped forward. He did not want to be burnt to a crisp.

‘‘What do you want?’’ grumped the dragon as it eyed Martin suspiciously.

‘‘Please, dragon, I have a list of numbers, and I need to know if any of them are odd’’ Martin began. ‘‘Here it is.’’ He wrote the list in the dirt with his finger:

(3142 5798 6550 8914)

The dragon was in a disagreeable mood that day. Being a dragon, it always was. ‘‘Sorry, boy’’ the dragon said. ‘‘I might be willing to tell you if the first number in that list is odd, but that’s the best I could possibly do. Anything else would be too complicated; probably not worth my trouble.’’

‘‘But I need to know if any number in the list is odd, not just the first number’’ Martin explained.

‘‘Too bad for you!’’ the dragon said. ‘‘I’m only going to look at the first number of the list. But I’ll look at as many lists as you like if you give them to me one at a time.’’

Martin thought for a while. There had to be a way around the dragon’s orneriness.

‘‘How about this first list then?’’ he asked, pointing to the one he had drawn on the ground:

(3142 5798 6550 8914)

‘‘The first number in that list is not odd,’’ said the dragon.

Martin then covered the first part of the list with his hand and drew a new left parenthesis, leaving

(5798 6550 8914)

and said ‘‘How about this list?’’

‘‘The first number in that list is not odd,’’ the dragon replied.

Martin covered some more of the list. ‘‘How about this list then?’’

(6550 8914)

‘‘The first number in that list isn’t odd either,’’ said the dragon. It sounded bored, but at least it was cooperating.

‘‘And this one?’’ asked Martin.

(8914)

‘‘Not odd.’’

‘‘And this one?’’

()

‘‘That’s the empty list!’’ the dragon snorted. ‘‘There can’t be an odd number in there, because there’s nothing in there.’’

‘‘Well,’’ said Martin, ‘‘I now know that not one of the numbers in the list the alchemist gave me is odd. They’re all even.’’

‘‘I NEVER said that!!!’’ bellowed the dragon. Martin smelled smoke. ‘‘I only told you about the first number in each list you showed me.’’

‘‘That’s true, Dragon. Shall I write down all of the lists you looked at?’’

‘‘If you wish,’’ the dragon replied. Martin wrote in the dirt:

(3142 5798 6550 8914)
(5798 6550 8914)
(6550 8914)
(8914)
()

‘‘Don’t you see?’’ Martin asked. ‘‘By telling me that the first element of each of those lists wasn’t odd, you told me that none of the elements in my original list was odd.’’

‘‘That’s pretty tricky,’’ the dragon said testily. ‘‘It looks liked you’ve discovered recursion. But don’t ask me what that means—you’ll have to figure it out for yourself.’’ And with that it closed its eyes and refused to utter another word.

- From the book "Common Lisp: A Gentle Introduction to Symbolic Computation"

Something to learn from paneer tikka masala

An interesting thing happened yesterday (i.e. tonite). At dinner, paneer tikka masala was served in the mess. It was ok; not too good, not too bad. As usual, I got there late (at about 9.30) and very little paneer pieces were left. After the meal, I washed my hands and was leaving for my room. Now there is a white-board near the mess entrance. On that it was written:

"Mess contractor fined Rs. 1,500 for low quality of sabji"

I was shocked more than surprised. If this "model" was extrapolated to a larger setting like pwd being fined for potholes in the road, etc. how will our country be?

Economics

Normally I consider myself a very CS centric guy. I do have other interests, and I'm quite aware of the world around me, but I certainly enjoy writing wierd looking LISP functions over reading the theory of relativity (more of that in another post). However, I came in contact with a new friend. We go to the library quite often. He generally reads books from almost every topic (and believe me any topic), while I normally confine myself to the holy precincts of the Computer Science section.

But due to our association for the last month or so, I have begun to appreciate other areas of knowledge as well. Be it through discussions, debates, expositions or whatever.

Now how does this leads to economics? A question struck me for which I could not think of an answer. I assumed that the basic foundation of all finance, markets, trade and economics is money changing hands. Now put in the law of conservation of energy. Can I say that all the money in the world is always constant? It is just changing hands, right?

Another question is if all of a sudden all of the countries of the world decided to have a common currency something like the Euro, what will happen? No question of the Rupee falling, forex reserves and all that. Will it be a step towards having a more equitable society? Will it be good or bad?

People who have the answers, please comment.

Cogito ergo sum - I think, therefore I am

This statement by Rene Decartes (Renay Daycart) is perhaps one of the most important foundations of any rational thought. Most of us know Decartes as the originator of Cartesian coordinate geometry, but he did much more than that. He was the founder of both modern philosophy as well as modern mathematics. As you can see from the last three letters of the translation, this blog is my ode to the master.

Well this blog is not about I or me (depends on which side of the evolutionary curve you are on), nor is it about Descartes, it is about my thoughts - meine Gedanken.