Algorithmic Generation: What Piṅgala Actually Achieved
Chapter Thirty-One
Syllabus topic Module 1, "Algorithmic generation", "Complexity & Limitations"
Pages 102 to 104 of 378
In one line
Piṅgala's six rules between them generate, index, count and measure a space of 2 to the power n objects, and only the first of them ever touches the whole space.
In the wording you can write in an examination: algorithmic generation is the production of the members of a set by the repeated application of a stated rule rather than by storing them. The Chandaḥśāstra's eighth chapter supplies a generator for the full set of metrical patterns, two index operations that address the set without generating it, a counting operation that gives its size in logarithmic time, and a combinatorial operation that counts its members by a property, all stated as effective procedures.
What is genuinely achieved, in one table
This is the chapter to revise from, and the third column is the part that is usually left out of accounts of Piṅgala.
| Rule | What it does | Cost | Does it build the table? |
|---|---|---|---|
| prastāra | every pattern, in a fixed order | n times 2 to the power n | yes, that is its job |
| naṣṭa | the pattern in row r | proportional to n | no |
| uddiṣṭa | the row of a pattern | proportional to n | no |
| saṅkhyā | how many patterns | proportional to log n | no |
| lagakriyā | how many with k light syllables | proportional to k for one value | no |
| adhvayoga | the written extent | proportional to log n | no |
Five of the six avoid the table. For the jagatī that is the difference between 49,152 symbol operations and twelve. The set of six is, in effect, an interface to a structure that is never materialised, and that is a design worth naming.
The five properties, collected
[The Prastāra Rule Read as an Algorithm] tested the prastāra against the five properties of an algorithm. The other five rules pass the same test, and where any of them is weaker it is worth saying which.
Input, definiteness, effectiveness, output. All six are unambiguous, executable by hand, and produce what they promise.
Finiteness. The prastāra halts after 2 to the power n minus 1 steps, proved. Naṣṭa and uddiṣṭa halt after exactly n steps by construction. Saṅkhyā halts because halving a positive integer reaches one and subtracting one from an odd number reduces it, so the descent is strictly decreasing. Lagakriyā halts because each row of the Meru is finite and rows are built in order.
Where the tradition is weakest. Adhvayoga, whose rule Halāyudha declines to state in full, so its definiteness rests on the reader supplying the arithmetic. That is a real gap and this book says so in [Lagakriyā and Adhvayoga: The Rest of the Pratyayas].
What is NOT achieved, stated plainly
A five-mark answer asked to assess critically should have three of these ready.
Algorithmic Generation: What Piṅgala Actually Achieved
No machine. Every rule is executed by a trained person. The gap between an algorithm and a machine that runs it is most of the history of computing, and none of it is here.
No notion of cost. Not one of the six rules is accompanied by a statement that it is cheaper than the alternative. The saṅkhyā saving is real and unremarked. The costs in the table above are ours.
No base, and no arithmetic on patterns. The order agrees with binary counting, which is proved in [Binary Number Systems, and Exactly Where Piṅgala's Order Agrees], and the text nowhere treats a pattern as a number or adds two of them.
No generalisation. Saṅkhyā computes powers of two, not powers. The Meru counts light syllables in a two-symbol alphabet, not selections in general. The generalisations are immediate and the text does not make them.
No validation. No rule checks its input. Naṣṭa will return a pattern for a row that does not exist.
The claim this book does make
Stated once, carefully, because it is the sentence a good answer needs.
Piṅgala chose a representation in which the questions of his subject became decidable by arithmetic, and then stated the arithmetic as procedures. The representation is the two-valued syllable. The questions are enumeration, addressing and counting. The procedures are the six pratyayas. Every part of that sentence is a fact about the text, and the whole of it is what a computer scientist means by good design.
Worked example: the answer to a cross-module question
Q.3 of MU's paper draws on both modules. Here is the shape of an answer that uses this chapter, written at the length five marks allows.
Question. Relate Piṅgala's treatment of metre to the idea of a formal system as it appears elsewhere in this course.
Answer. Both Piṅgala and Pāṇini fix a finite alphabet, state rules over it, and provide for the case where a result is needed that has not been written out. Piṅgala's alphabet has two members and his rules generate and address the whole set of strings; Pāṇini's alphabet is the sounds of Sanskrit and his rules derive particular strings on demand. The difference is the interesting part: Piṅgala's space is complete and uniform, so arithmetic suffices to navigate it, whereas Pāṇini's target language is a proper subset of the strings his alphabet admits, so his system needs conditions, exceptions and a conflict policy that Piṅgala's has no occasion for. Nyāya, in Module II, supplies the third case, in which the rules are about admitting a claim rather than producing a string, and the enforcement is social rather than arithmetical.
That answer is four sentences and it touches three of the six syllabus areas. That is the register Q.3 is asking for.
Algorithmic Generation: What Piṅgala Actually Achieved
Quick revision
- Six rules: prastāra generates; naṣṭa and uddiṣṭa index; saṅkhyā counts; lagakriyā counts by a property; adhvayoga measures.
- Five of the six never build the table. For the jagatī that is twelve operations against about 49,000.
- All six are definite and effective; the finiteness of each has a short argument; adhvayoga is the weakest because its rule is not stated in full.
- Not achieved: no machine, no statement of cost, no base or arithmetic on patterns, no generalisation, no validation.
- The claim that is true: he chose a representation that made his questions arithmetical, and then stated the arithmetic.
Test yourself
1. Which of the six pratyayas builds the table, and what follows for the rest?
Only the prastāra. The other five answer their questions without materialising the set, so they behave like an interface to a structure that is never stored.
2. Give the cost of each of naṣṭa, saṅkhyā and prastāra, for a twelve-syllable metre.
Naṣṭa is twelve steps. Saṅkhyā is five operations for n equal to twelve. The prastāra is 4096 rows of twelve symbols, about 49,000 symbol operations.
3. Name three things the text does not do, that a careless account of Piṅgala claims.
It never states that any rule is cheaper than an alternative; it never treats a pattern as a number or performs arithmetic on one; and it never generalises saṅkhyā beyond powers of two or the Meru beyond a two-symbol alphabet.
4. State the claim this book makes about Piṅgala in one sentence.
He chose a representation, the two-valued syllable, in which the questions of his subject became decidable by arithmetic, and then stated that arithmetic as a set of effective procedures.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.