hierarchy of functions
hierarchy of functions A sequence of sets of functions F0, F1, F2,… with the property that F0 ⊆ F1 ⊆ F2 ⊆ …
(see subset). Typically the functions in F0 will include certain initial functions; the sets of functions F1, F2,… are normally defined by combining initial functions in some way.
Hierarchies of primitive recursive functions can be defined by letting Fi represent those functions that can be computed by programs containing at most i loops nested one within the other. Then Fi ⊆ Fi+1
for all integers i > 0. The union of all these sets includes all the primitive recursive functions and only those functions. Consequently the hierarchy is often called a subrecursive hierarchy. This same hierarchy can be expressed in a slightly different form, so resulting in the Grzegorczyk hierarchy.
In an attempt to circumvent problems caused by recursion, Bertrand Russell invented a theory of types, which essentially imposed a hierarchy on the set of functions; functions at one level could be defined only in terms of functions at lower levels.
The study of hierarchies of functions dates from work of David Hilbert around 1926 on the foundations of mathematics. More recent interest stems from their applicability to computational complexity.
(see subset). Typically the functions in F0 will include certain initial functions; the sets of functions F1, F2,… are normally defined by combining initial functions in some way.
Hierarchies of primitive recursive functions can be defined by letting Fi represent those functions that can be computed by programs containing at most i loops nested one within the other. Then Fi ⊆ Fi+1
for all integers i > 0. The union of all these sets includes all the primitive recursive functions and only those functions. Consequently the hierarchy is often called a subrecursive hierarchy. This same hierarchy can be expressed in a slightly different form, so resulting in the Grzegorczyk hierarchy.
In an attempt to circumvent problems caused by recursion, Bertrand Russell invented a theory of types, which essentially imposed a hierarchy on the set of functions; functions at one level could be defined only in terms of functions at lower levels.
The study of hierarchies of functions dates from work of David Hilbert around 1926 on the foundations of mathematics. More recent interest stems from their applicability to computational complexity.
More From encyclopedia.com
Primitive Recursion , primitive recursive function A function that can be obtained from certain initial functions by a finite number of applications of composition and pri… Function , A function is a mathematical relationship between two sets of real numbers. These sets of numbers are related to each other by a rule that assigns ea… Teleology , The term teleology locates a series of connected philosophical questions. If we grant that there is such a thing as purposive or goal-directed activi… functional , functional •annal, channel, flannel, impanel, multichannel, panel •cracknel •grapnel, shrapnel •carnal •antennal, crenel, fennel, kennel •regnal •ana… GKS Abbrev. for graphical kernel system. , GKS Abbrev. for graphical kernel system. A set of graphical functions used by applications programmers with the names and functions defined in ISO 79… Functional Analysis , Few concepts in modern social science history have generated as much discussion as those of structure and function and the type of analysis associate…
You Might Also Like
NEARBY TERMS
hierarchy of functions