de Bruijn diagrams

A third feature of the second series was the incorporation of the de Bruijn diagrams within the main program, together with a visual representation in terms of chords of a circle. It was still not possible to transfer the cycles obtained back to the main program without copying them on paper and editing the initial line with the option l.

Limitations of space and time severely restrict the lengths of periods which can be analyzed. Although interesting gliders and cycles are found within the accessible range of the program, there are many others of longer periods which manifest themselves experimentally when the evolutions are run. It would be nice if the exhaustive analysis afforded by the de Bruijn diagrams were feasible for the longer periods that show up on the screen, but they would really require a faster computer, more memory, and probably programs incorporating finer details of the algorithms used.

The programs contained a bare minimum of help facilities, in the sense that menus of one type or another were presented at various stages in the evolution of the programs, and others are sometimes available by typing a question mark, just as a slash often cleared portions of the screen.

A manual consisting of the lecture notes for Fortran III is in preparation, for which chapters are planned describing by accompanying programs. As is well known, the preparation of manuals always lags the evolution of the programs which they are supposed to describe.

There are still some interesting problems of presentation --- recall that Fortran III is supposed to be dedicated to graphical techniques. Presentation of simple evolution is easily solved, since the resolution and velocity of the graphics controllers included as standard equipment in IBM PC's and their clones is adequate. Unfortunately color monitors and their controllers are sometimes seen as premium equipment which was not included in a given installation, so that a monochromatic rendering of the color displays must be endured.

Even so, the speed and screen resolution which is available in the present generation of equipment is only marginally satisfactory, having only a fraction of the resolution of pen and ink plotters which have been commonly available. Once statistics pertaining to the evolution of automata are to be presented, it is found that there are many more parameters than are comfortable, which leads to the use of shading, complex surface representations, even stereographic view. It is in this area that some interesting results can be obtained, but mostly ones which whet one's appetite for the next generation of equipment.

Likewise the use of the de Bruijn diagram and the reduced evolution diagram, even without their probabilistic versions,requires line drawings of a complexity which quickly surpasses the capability of the present generation of graphical displays. Although the complexity of these diagrams increases exponentially --- making even modest values of parameters permanently inaccessible; still, even moderately better graphics equipment will permit an instructive display of the simplest cases.

Although the menus vary slightly from program to program, they generally conform to a uniform pattern, whose constituents are described below.

Harold V. McIntosh