Loops & Recursive Functions

Using the loop based taxonomy of digital systems to evaluate how Kleene's Partial Recursive Function model can be implemented efficiently using digital circuits results in the following correspondences:

basic functions &harr 0OS, no-loop circuits
composition rule &harr 1OS, one-loop circuits
primitive recursion rule &harr 2OS, two-loop circuits
minimalization rule &harr 3OS, three-loop circuits.

Therefore: any computation can be done efficiently using digital systems having at least 3 embedded loops.

References

[Stefan '91] Gh. Stefan,: Functie si structura in sistemele digitale (Function and Structure in Digital Systems), Ed. Academiei Romane, Bucuresti, 1991.
[Stefan '97] Gh. Stefan: Circuit Complexity, Recursion, Grammars and Information. Multiple Morphisms, Ed. Transilvania University of Brasov, 1997.
[Stefan work in endless progress] Gh. Stefan: Loops & Complexity in Digital Systems. Lecture Notes on Digital Design in the Giga-Gate/Chip Era