Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
An inherently iterative algorithm for the Grzegorczyk hierarchy
Matthews R. Theoretical Computer Science125 (2):355-360,1994.Type:Article
Date Reviewed: Aug 1 1995

Extending results of Grossman and Zeitman [1] on an inherently iterative algorithm for the classical Ackermann’s function, the author develops an analogous algorithm for the more logically interesting Grzegorczyk hierarchy [2]. Recall that the diagonal function for the Grzegorczyk hierarchy is yet another deep example of an effectively calculable function that is not primitive recursive. As a bonus, the author’s iterative algorithm results in a space-complexity function and a time-complexity function whose orders of growth improve upon those for the (more obvious) directly implemented algorithm. This note is another interesting contribution to the theory of general recursive functions with super-rapid growth.

Reviewer:  A. A. Mullin Review #: CR118754 (9508-0615)
1) Grossman, J. W. and Zeitman, R. S. An inherently iterative computation of Ackermann’s function. Theor. Comput. Sci. 57, 2/3 (May 1988), 327–330.
2) Grzegorczyk, A. Some classes of recursive functions. Rozprawy Matematyczne 4 (1953), 1–45.
Bookmark and Share
 
Recursive Function Theory (F.4.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Recursive Function Theory": Date
Higher recursion theory
Sacks G., Springer-Verlag New York, Inc., New York, NY, 1990. Type: Book (9780387193052)
Feb 1 1992
Recursively enumerable sets and degrees
Soare R., Springer-Verlag New York, Inc., New York, NY, 1987. Type: Book (9789780387152998)
Mar 1 1988
Reflexive structures: an introduction to computability theory
Sanchis L., Springer-Verlag New York, Inc., New York, NY, 1988. Type: Book (9789780387967288)
Jul 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy