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:
Therefore: any computation can be done efficiently
using digital systems having at least 3 embedded loops.
- 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.
[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