Skip to main content
SpringerLink
Log in

The Ackermann function. a theoretical, computational, and formula manipulative study

  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

Ackermann's function is of highly recursive nature and of two arguments. It is here treated as a class of functions of one argument, where the other argument defines the member of the class. The first members are expressed with elementary functions, the higher members with a hierarchy of primitive recursive functions. The number of calls of the function needed in a straightforward recursive computation is given for the first members. The maximum depth in the recursion during the evaluation is investigated.

Results from tests with the Ackermann function of recursive procedure implementations in ALGOL-60, ALGOL W, PL/I and SIMULA-67 on IBM 360/75 and CD 6600 are given.

A SYMBAL formula manipulating program, that automatically solves recurrence relations for the first members of the function class and for the number of calls needed in their straightforward computation, is given.

The Ackermann rating of programming languages is discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Singapore)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. W. Ackermann,Zum Hilbertschen Aufbau der reellen Zahlen, Math. Annalen 99 (1928), pp. 118–133.

    Article  Google Scholar 

  2. J. A. Brown,Using the Ackermann Function to Rate Programming Languages, APL QUOTE-QUAD, vol. 2, no. 1, April 1970, ed. G. Foster, Syracuse University, N.Y.

    Google Scholar 

  3. M. E. Engeli,User's Manual for the Formula Manipulation Language SYMBAL, Univ. of Texas Computation Center, Austin 1968.

    Google Scholar 

  4. M. E. Engeli,Formula Manipulation—The User's Point of View, Advances in Information Systems Science (ed. J. Tou), Volume 1, N.Y. 1969, pp. 117–171.

    Google Scholar 

  5. K. E. Iverson,A Programming Language, Wiley, N.Y. 1968.

    Google Scholar 

  6. E. Satterthwaite,Comparison of Recursive Procedure Implementation, Working Paper, Stanford Univ., June 27, 1970.

  7. Y. Sundblad,A Study of the Highly Recursive Ackermann Function Theoretically and as a Test of Recursive Procedures in ALGOL, PL/I and SYMBAL and of Formula Manipulation in SYMBAL, Report NA70.18, The Royal Institute of Technology, Stockholm, April 1970.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Processing, Royal Institute of Technology, S-100 44, Stockholm, Sweden

    Yngve Sundblad

Authors
  1. Yngve Sundblad
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sundblad, Y. The Ackermann function. a theoretical, computational, and formula manipulative study. BIT 11, 107–119 (1971). https://doi.org/10.1007/BF01935330

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01935330

Keywords

CR categories

Search

Navigation