Grzegorczyk hierarchy

Grzegorczyk hierarchy

The Grzegorczyk hierarchy, named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of sets of functions used in recursive function theory. Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level. See also recursive language. The hierarchy deals with the rate at which functions may grow: intuitively, functions in the low level of the hierarchy grow very slowly (for example, linearly), while functions higher up in the hierarchy grow very rapidly.

Definition

First we introduce an infinite set of functions, denoted "Ei" for some natural number "i". We define E_0(x,y)=x+y and E_1(x)=x^2+2. I.e., "E0" is the addition function, and "E1" is a unary function which squares its argument and adds two. Then, for each "n" greater than 1, we define E_n(x)=E^{x}_{n-1}(2).

From these functions we define the Grzegorczyk hierarchy. mathcal{E}^0, the first set in the hierarchy, contains the following functions:
# the zero function (e.g., "f"("x") = 0);
# the successor function (e.g., "s"("x") = "x" + 1);
# the projection functions (e.g., "p"("x", "y", "z") = "x");
# the compositions of functions in the set, for example, if "g" and "h" are in mathcal{E}^0, then "f"("x") = "h"("g"("x")) is as well; and
# the results of limited recursion applied to functions in the set, for example, if "g", "h" and "j" are in mathcal{E}^0 and f(y, x)leq j(y, x) for all "x" and "y", and further f(0, x)=g(x) and f(y+1,x)=h(y,x,f(y,x)), then "f" is in mathcal{E}^0 as well.

For each "n" greater than 0, we define mathcal{E}^n to be set of functions that results from repeatedly applying composition (of functions in mathcal{E}^n) and limited recursion (ibid) to the functions "E"0 and "En" together with the zero function, the successor function, and the projection functions.

Note that mathcal{E}^1 provides all addition functions, mathcal{E}^2 provides all multiplication functions, mathcal{E}^3 provides all exponentiation functions, mathcal{E}^4 provides all tetration functions, and so on.

Relationships to other function classes

The fourth level in the hierarchy, mathcal{E}^3, is exactly the elementary recursive functions.

References

* Brainerd, W.S., Landweber, L.H. (1974), "Theory of Computation", Wiley, ISBN 0-471-09585-0
* Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Hiérarchie de croissance rapide — En théorie de la calculabilité et en théorie de la démonstration, une hiérarchie de croissance rapide (parfois appelée une hiérarchie de Grzegorczyk (en) étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes …   Wikipédia en Français

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… …   Wikipedia

  • NC (complexity) — Unsolved problems in computer science Is NC = P ? In complexity theory, the class NC (for Nick s Class ) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In… …   Wikipedia

  • P versus NP problem — Unsolved problems in computer science Is P = NP ? …   Wikipedia

  • DSPACE — For digital repositories, see DSpace. In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space… …   Wikipedia

  • PSPACE — Unsolved problems in computer science Is P = PSPACE ? PSPACE …   Wikipedia

  • DTIME — In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a normal physical computer would take …   Wikipedia

  • Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… …   Wikipedia

  • Arthur–Merlin protocol — In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier s coin tosses are constrained to be public (i.e. known to the prover too). This notion was introduced by Babai (1985). Goldwasser… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”