The Prastāra Rule Read as an Algorithm
Chapter Seventeen
Syllabus topic Module 1, "Prastāra (systematic enumeration of patterns)", "Algorithmic generation"
Pages 51 to 54 of 378
In one line
Halāyudha's prastāra rule is an algorithm and not just a description, and this chapter proves it by checking the five properties an algorithm has to have.
In the wording you can write in an examination: an algorithm is a finite sequence of unambiguous instructions which, for every admissible input, terminates after finitely many steps and produces the intended output, each step being effective, that is, executable by a person or machine with no further interpretation. The prastāra rule satisfies all five conditions, and the syllabus's label "algorithmic generation" is earned rather than asserted.
Why this test is worth running
It is easy to say an old text "contains an algorithm" and hard to mean anything by it. The five properties below are the standard ones, they are checkable, and running them against a specific classical rule is exactly what MU's course objectives ask for when they say analyse.
It also tells you something when a rule fails one of them. Several of the classical rules in this paper come close and fail a condition, and saying which condition is a better answer than a general enthusiasm.
The five properties, and the rule against each
The rule under test is the one from [Prastāra: The Table of Every Pattern]: first row all heavy; then find the first heavy syllable from the left, make it light, make everything to its left heavy, leave everything to its right alone; stop when no heavy syllable remains.
Input
The property. The algorithm takes zero or more inputs from a stated set.
The rule. It takes one input, n, the number of syllables. Halāyudha's own usage supplies the admissible set: he applies the rule to one, two, three, four, five and six syllables in turn, and the general rule 8.22 is stated for any number. So the input is a positive integer.
Verdict: satisfied. With one honest note: the text nowhere says what happens for n equal to zero, and no classical author asked.
Definiteness
The property. Every step is unambiguous. A reader cannot have to choose.
The rule. Step by step: "find the first heavy syllable from the left" has one answer for any row. "Make it light" has one result. "Make everything to its left heavy" has one result. "Leave everything to its right alone" has one result. Nothing in the rule asks the reader to decide anything.
Verdict: satisfied, and this is the property the classical formulation is strongest on. Compare it with a rule like "choose a convenient starting point", which is a description and not an instruction.
Finiteness
The property. The algorithm terminates after finitely many steps for every admissible input.
Worked. This one needs an argument, not an inspection, and the argument is the interesting part of the chapter.
The Prastāra Rule Read as an Algorithm
Read each row as a number with light counting one and heavy counting zero, the leftmost syllable being the units place. Then one step of the rule does this: the first heavy syllable, at position k, becomes light, adding 2 to the power k minus 1; and every light syllable to its left becomes heavy, subtracting 1 plus 2 plus 4 and so on up to 2 to the power k minus 2, which totals 2 to the power k minus 1 minus 1.
So the net change is exactly plus one. Each step increases the row's value by one, the value starts at 0 and can never exceed 2 to the power n minus 1, so the rule stops after exactly 2 to the power n minus 1 steps.
Verdict: satisfied, and provably. Notice what this argument gives you beyond termination: it gives the exact number of steps, and it is the reason the order is the order of counting.
Effectiveness
The property. Every step is basic enough to be carried out exactly, in finite time, with the means available.
The rule. The operations are: scan a row left to right; overwrite one symbol; overwrite a prefix. A scribe with a palm leaf can do all three. No step requires arithmetic, and none requires knowing anything about metre.
Verdict: satisfied. And worth noticing: the rule is effective for a human executor with no mathematics, which is exactly what it was designed for.
Output
The property. It produces the intended result.
The rule. It produces every pattern of n syllables, once each, in a fixed order. That is a claim about correctness and it is not obvious from the rule.
The finiteness argument above supplies the proof. If each step adds exactly one to the row's value, and the first row is 0, then the rows take the values 0, 1, 2 and so on up to 2 to the power n minus 1, each exactly once. Since the mapping between patterns and values is one to one, every pattern appears exactly once.
Verdict: satisfied, and proved by the same argument as finiteness. The program in [Prastāra in Code] also checks it by brute force up to fourteen syllables, which is a different kind of assurance.
The five properties as a table
| Property | What it requires | The prastāra rule | Evidence |
|---|---|---|---|
| Input | a stated admissible set | one positive integer, the syllable count | 8.22 stated for any number, applied to 1 up to 6 |
| Definiteness | no step needs a choice | every step has exactly one result | the wording of the rule itself |
| Finiteness | terminates for every input | stops after 2 to the power n minus 1 steps | each step adds one to the row's value |
| Effectiveness | each step is basic | scan, overwrite one symbol, overwrite a prefix | a scribe can perform all three |
| Output | produces the intended result | all patterns, once each, in order | the same increment argument, plus a brute-force check |
The Prastāra Rule Read as an Algorithm
What this does NOT establish
It does not make the Chandaḥśāstra a program. An algorithm is a procedure; a program is an algorithm expressed for a machine. There is no machine, and saying so is part of the answer.
It does not mean Piṅgala thought in these terms. The five properties are a modern test. What has been shown is that his rule passes it, which is a fact about the rule.
It does not mean every rule in the text passes. [Lagakriyā and Adhvayoga: The Rest of the Pratyayas] discusses one that is stated so briefly that its definiteness depends on the commentary, and the honest verdict there is different.
Limits
One limit is worth naming because it recurs. The rule has no stated complexity. Nothing in the text says how long producing the table takes, or notices that it takes time proportional to n times 2 to the power n. The saṅkhyā rule shows that Piṅgala cared about avoiding work, so the absence is interesting rather than damning, but it is an absence. [Algorithmic Generation: What Piṅgala Actually Achieved] gives the costs.
Quick revision
- The five properties: input, definiteness, finiteness, effectiveness, output.
- Definiteness is the classical rule's strongest property: no step requires a choice.
- Finiteness is proved, not observed: each step raises the row's value by exactly one, so the rule halts after 2 to the power n minus 1 steps.
- The same argument proves correctness: the rows take every value from 0 upward exactly once.
- Effectiveness: scan, overwrite one symbol, overwrite a prefix. A scribe can do all three with no arithmetic.
- What is missing from the text: any statement of cost.
Test yourself
1. Name the five properties of an algorithm.
Input, definiteness, finiteness, effectiveness, output.
2. Prove that the prastāra rule terminates, and say how many steps it takes.
Read a row as a number with light as one and the leftmost syllable as the units place. One step turns the first heavy syllable light, adding 2 to the power k minus 1, and resets the lighter syllables to its left, subtracting 2 to the power k minus 1 minus 1. The net change is plus one. Starting from 0 and bounded by 2 to the power n minus 1, the rule halts after exactly 2 to the power n minus 1 steps.
3. How does the same argument prove the table is complete and has no repeats?
The Prastāra Rule Read as an Algorithm
Because the rows take the values 0, 1, 2 and so on consecutively, and patterns correspond one to one with values, every pattern appears exactly once.
4. Which property is a rule like "begin at a convenient point" failing, and why does it matter?
Definiteness. A reader has to make a choice, so two readers can produce different results, and the procedure is a description rather than an algorithm.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.