next up previous
Next: THE PEREIRA-PORTO LOGIC PROGRAM Up: COLORING MAPS AND Previous: COLORING MAPS AND

ALGORITHM = LOGIC + CONTROL

The formula isn't precise, and it won't be precise until someone proposes a precise and generally accepted notion of how control is to be added to an expression of the logic of a program. Nevertheless, the idea is attractive, and I believe it can be made to work for some interesting class of programs. It is analogous to my comparison of epistemology and heuristics or Chomsky's competence and performance.

Pereira and Porto (1980) give a logic program for coloring planar maps with four colors and discuss how ``selective backtracking'' can reduce the search involved in coloring a map from that done by a straightforward PROLOG execution of the same program.

The discussion by Pereira and Porto treats coloring maps purely as an example of logic programming, and the improvements they discuss apply to all logic program systems. We shall consider two mathematical ideas about map coloring that go back to Kempe (1879), the paper containing the original false proof of the four color theorem. While Kempe's proof was false, the ideas are good and were used in almost all subsequent work including the recent successful proof.

The question is whether an algorithm involving these ideas can be regarded as a form of control adjoined to the basic logic program or whether they necessarily involve a new program. If they are to be regarded as control structures, it is not yet clear how they are best expressed. Of course, it is not hard to write a completely new program in PROLOG or any other language expressing the algorithms, and this has been done. The interpreted programs color a map of the United States. However, it is also interesting to try to regard the algorithms as control attached to the Pereira-Porto logic program for coloring a specific map.



John McCarthy
Sat Feb 22 18:04:49 PDT 1997