Comments on “Sleeping with Sukhi”
Comments are for the page: Sleeping with Sukhi
Recursion
Reading this again, what came to my mind was the history of mathematics question of who first used recursive definitions and who first gave a name to that style of definition.
Used in the nineteenth century for sure, especially in German language texts. This is way later than the period the story is set in, of course.
Before that … it’s a good question of what counts as a recursive, as opposed to iterative, definition. Fibonnaci’s famous problem about reproducing rabbits is a recurrence relation.
I haven’t checked, but presumably Panini’s Sanskrit grammar doesn’t have explicitly recursive grammar rules.
It's Italian sandwiches all the way down
The secondary sources I’ve read are a bit vague around the edges. However, my understanding is:
Panini’s metagrammatical formalism definitely allows recursion. It’s similar to BNF, and so can express context-sensitive grammars, including center-embedding.
You can write a non-recursive grammar in a formalism that allows recursion. However, Panini’s specific grammatical rules are recursive, and do allow the generation of unboundedly long strings. I believe this includes center-embedding (but am not completely positive about that).
Panini almost certainly didn’t intend unbounded recursion. He was writing a grammar that was meant to specify a spoken language in which excessively long strings would be pathological. The grammar was more permissive in that respect than he probably meant it to be.
However, centuries later, people exploited the flexibility of the grammar to invent much longer, highly complex constructions that would probably never naturally occur in speech, and hadn’t previously been used in writing, for use in fancy literary language. The poet/playwright Kalidasa is often mentioned as having taken this to extremes for effect. Apparently it’s clever and elegant and spiritually transporting. I don’t know even basic Sanskrit, never mind fancy literary stuff, so I have to take others’ word for that!
Panini was definitely a major influence on European grammatical theory, starting in the early 1800s.
I don’t know whether there’s influence from there to Frege (and therefore to Hilbert, Turing, etc.) I would like to, though!
Undone by recursion
A couple of days ago, I had an “undone by recursion” moment, thinking about this story. It went roughly like this:
So, you have some (formal) grammar that includes recursive definitions, and you use proof by induction to prove some theorem about all gramatically correct expressions.
But wait, thinks I. If you’re really trying to prove this sort of theorem rigorously, surely you’ld need something like Peano’s 9th axiom, only for grammars rather than integers. Some axiom that says it’s ok to do induction on grammars, because the recursion always terminates in a finite number of steps. That guarantees you no sentence in the grammar is - for example - a circularly linked list that causes the parser to run forever. You could probably write that sentence in a finite number of symbols, around the circumference of a bracelet, for example…
Love the recursion joke!
I’m (re-?)reading the whole story now and loving it!
The recursion joke(s) are particularly funny!
The “infinity unrolled” ‘being undone by recursion’ bit reminds me of something I remember experiencing as a kid – a feeling of flying or ‘zooming’, but “infinity unrolled before him” is an even better description. Thinking back on it now, I think it would happen when I was in a ‘trance’ or similar kind of ‘meditative’ state. I only remember it happening at night, after I was supposed to be asleep, and I remember it most vividly as happening when I was looking out the window of my bedroom and rubbing a part of a soft blanket folder over onto itself. Something about the sensation felt ‘infinite’. Weird!
“It is no shame to be undone by recursion” – truly! I tell my own ‘pupils’ that, and don’t qualify it with “the first time”. Indeed, even with the most careful spells (unit tests), a failure to properly tame recursion can be fatal (require killing the test job)!