Any directed graph (including a directed cyclic graph or DCG) has a complexity measure. We know that NOR is a universal logic gate, in the sense that a DCG whose nodes are n-input NOR gates can represent any computable number. We also know that Pi is computable. Hence there are an infinite number of NOR DCGs that compute Pi.

What is the current record holder for the simplest (lowest complexity measure) of such DCGs?


Finite graphs don't compute pi; circuits do.

No single circuit computes pi. Rather, when we say that pi is computable, this means that there exists an infinite family of circuits $C_1,C_2,\dots$ such that $C_i$ outputs the first $i$ digits of pi.

A standard measure of complexity for a circuit is its size: specifically, let $f(i)$ denote the size of $C_i$, then its complexity is given by the function $f$ (we often care only about the asymptotic behavior of $f$). This is related to the running time of an algorithm for computing pi. You could take any standard algorithm for computing pi, convert it to a circuit and evaluate its size.

  • $\begingroup$ Thanks. So I suppose I should have asked a different question, starting with a request for the smallest memory requirement to output a given number of digits of pi where the amount of memory required is the length of the program binary plus the length of the data memory. That program plus its data memory (flipflops I suppose) could then be converted to a circuit to measure its complexity. $\endgroup$ Jun 7 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.