Any bit-string {0,1}* can be produced by a finite directed cyclic graph, the nodes of which are n-input NOR functions, with at least two arcs directed away from the graph without a terminal connection (ie: the output and clock indicating a value is present on the output), and with a starting state on all edges of 0. The minimum complexity such DCG for a given bit-string is an interesting mathematical object that it is similar to the Kolmogorov Cmoplexity program for that bit-string. (Note that Circuit Complexity is defined in terms of Directed Acyclic Graphs. There is very little work on cyclic circuit complexity despite the ubiquity of DCGs in practice.)
Contrast this with the notion of algorithmic information, which is quantified as the number of bits in the smallest program that outputs a given bit-string on a given Universal Turing Machine.
The DCG of NORs has the virtue of requiring no open parameters -- not even in order to support time complexity measures such as Levin Search. This contrasts to the UTM which must specify the instruction set of the UTM, the execution time of each instruction and the the amount of memory required during execution of the given program.
However, it is not at all obvious how one quantifies the number of bits required to represent a given DCG. This, despite the fact that it can be proven that the set of all finite DCGs is countabe. Ideally, one would have, for each natural number, an isomorphism class of such DCGs, and the number of bits in the natural number would therefore be the information content of the bit-string output by that DCG. However, even though it can be proven that finite DCGs are countable, it is much more difficult to construct a function mapping from a natural number to a unique isomorphism class of DCGs.
