# 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