APL and the Grzegorczyk hierarchy
Pages 271 - 273
Abstract
We show in this paper that the set of “traditional” APL l-liners (using arithmetic functions only) compute precisely the set of functions in the class E4 of the Grzegorczyk hierarchy (the class immediately above the elementary functions). We also show that if we extend the set of 1-liners to include either the “execute” operator, or 1 line programs with gotos, then any partial recursive function can be computed.
References
[1]
J. A. Brown. Using the Ackermann Function to Rate Programming Languages, APL Quote-Quad, II (1970), pp. 35-36.
[2]
A. Grzegorczyk. Some classes of recursive functions, Rozprawy Mathematyczne, Polish National Academy, 1953.
[3]
K. Iverson. A Programming Language, Wiley, 1962.
[4]
T. A. Linden. The Ackermann Function in APL, APL Quote-Quad, II (1971), pp. 130-131.
[5]
R. J. Lipton and L. Snyder. On the power of applicative languages, in Formal Descriptions of Programming Concepts, E.J. Neuhold (ed.) North-Holland publishing Company, 1978.
[6]
A. R. Meyer and D. M. Ritchie. The Complexity of Loop Programs, in Proceedings of the 22nd National Conference, Association for Computing Machinery, 1967.
[7]
H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill 1967.
Index Terms
- APL and the Grzegorczyk hierarchy
Recommendations
APL and the Grzegorczyk hierarchy
Part 1We show in this paper that the set of “traditional” APL l-liners (using arithmetic functions only) compute precisely the set of functions in the class E4 of the Grzegorczyk hierarchy (the class immediately above the elementary functions). We also show ...
An analog characterization of the Grzegorczyk hierarchy
We study a restricted version of Shannon's general purpose analog computer in which we only allow the machine to solve linear differential equations. We show that if this computer is allowed to sense inequalities in a differentiable way, then it can ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1979 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 May 1979
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 315Total Downloads
- Downloads (Last 12 months)48
- Downloads (Last 6 weeks)4
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in