An inherently iterative computation of Ackermann's function (Q1106200)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An inherently iterative computation of Ackermann's function |
scientific article |
Statements
An inherently iterative computation of Ackermann's function (English)
0 references
1988
0 references
The note offers an iterative algorithm for the computation of Ackermann- Peter's function A(i,n). This algorithm requires \({\mathcal O}(i)\) space and \({\mathcal O}(iA(i,n))\) time to compute A(i,n), showing that the main difficulty in the computation of Ackermann-Peter's function is rooted in the huge time-complexity (and not in the space-complexity); the last assertion is valid for the computation of every p.r. function [cf. the reviewer and \textit{V. Vieru}, Found. Control Eng. 6, 133-144 (1981; Zbl 0503.68034)]. It will be interesting to compare other iterative procedures for the computation of Ackermann-Peter's function [see, especially, \textit{H. G. Rice}, Commun. ACM 8, 114-115 (1965; Zbl 0129.103) and \textit{J. Arsac}, RAIRO Inf. Théor. 20, 149-156 (1986; Zbl 0602.03008)] with the present one. The paper also includes an interesting historical discussion concerning Ackermann-Peter's function (more details can be find in the paper by the reviewer, \textit{S. Marcus} and \textit{I. Tevy} [Hist. Math. 6, 380-384 (1979; Zbl 0426.03042)].
0 references
Ackermann's function
0 references
iterative procedure
0 references
iterative algorithm
0 references
Ackermann-Peter's function
0 references
time-complexity
0 references
space-complexity
0 references