Does the Distributive Law Work?
A novel proof of termination
Larry Snyder is a professor of Computer Science and Engineering at the University of Washington in Seattle. His main interest has always been and still is in the area of parallel computing. I first began to work with Larry
when we both arrived at Yale University. While we have not worked together for years, it was always a great pleasure to work with him. He has a terrific sense of humor that makes working together pure pleasure.
We joined the Yale University Computer Science department in 1973–yes 1973–that is not a typo for 1993. He was an assistant professor and I was a “Gibbs Instructor”. I do not think they still have this type of position but it had the advantage of less teaching and a small travel budget, and the disadvantage of only being for two years.
As new faculty we were interested in the graduate student examination process. One day at lunch we asked our colleagues how it worked. We were told the general structure and then told that Alan Perlis had made up one of the exam questions. His question was so “hard” that not a single graduate student got even partial credit. I was immediately interested after we were told the question. I would like to say that we immediately solved it, after all we were now faculty not graduate students. But it took us a couple of hours before we got the problem solved. I think the problem and our solution is pretty neat and thought I would share it with you.
Imagine that you have a binary tree that has variables at the leaves and the operators and at the internal nodes. Clearly, such an expression represents an arithmetic expression. For example, is the tree in the figure below: (Yes I skipped –just to keep you on your toes.)
The question is suppose we expand out the tree using the distributive law. That is we can replace by for any subtrees . We think of this as the rule:
and the corresponding rule:
Of course these are just the famous distributive laws of arithmetic. Note, we can apply these rules any where in the tree and we keep applying the rules until there is no further place left to apply them. Perlis’s question was: Prove that for any tree the rule applications eventually stop. Clearly, this must be true: if we start expanding out an arithmetic tree it must eventually become “all expanded”. We have known this since grade school: every time we expanded some expression it eventually became one that could not be expanded any further. Clearly. The rub is proving this.
The reason it not obvious is that the usual way to prove that such a process halts is to show that some measure is decreasing and thus eventually the process must stop. More precisely, we would define a measure of “complexity” of an arithmetic tree. The measure should have two properties: First, it should be a natural number, i.e. a number . Second, each time we apply the distributive law the measure must decrease by at least one. If we can find such a measure, then the process must stop.
The difficulty with this process is that lots (most?) natural measures do not work. The main issue with suggested measures is that
when we apply the distributive law, say,
we create two copies of the subtree . This rules out lots of simple but natural measures. For example the number of symbols will not decrease but can increase. Indeed most natural measures fail to work.
If you wish to solve this on your own, then stop reading here and try to prove that this process does indeed halt.
Our solution is a general method that took advantage of one key property of the distributive law that you may have missed. What struck me immediately about the distributive law is this: it is not an arbitrary tree re-writing rule. It is a rule that preserves the value of the tree when viewed as an expression. It took Larry and I a while to figure out a proof that exploited this insight. Here is the proof:
Suppose that is some arithmetic tree. Make two observations about applying the distributive law: The first is that every application of the law preserves the value of the tree. Second, each application strictly increases the size of the tree: size of a tree is just the number of vertices in the tree. Now replace each leaf of the tree with the number . This is equivalent to replacing all the variables with the value . Now assume that the distributive law can be applied to the tree forever, then there is an infinite sequence of trees where is the result of some application of the distributive law to . We will show that this contradicts the two observations.
At the start the tree has some value, call that value . Since the value of the tree stays the same, after every application of the distributive law the value of all the trees is . However, we claim that this is impossible. Since the trees increase in size eventually there be an index large enough so that the tree has a path of at least long. It is easy to see, by the choice of the value on the leaves, that the value of this tree is at least . This is a contradiction that shows that the distributive law applications must eventually stop.
The method that we used to show that the distributive law always stops can be generalized to many other tree re-writing rules. The key insight is that the rules must preserve some value. We did some work on this many years ago, but I believe that the method could be used for a much wider range of problems. Perhaps our technique could help solve some “halting problems” that arise in modern computation questions.