Open Access
Fall 1994 Elementary Functions and LOOP Programs
Zlatan Damnjanovic
Notre Dame J. Formal Logic 35(4): 496-522 (Fall 1994). DOI: 10.1305/ndjfl/1040408609

Abstract

We study a hierarchy $\{\mathcal{L}_2^k \}$ of Kalmàr elementary functions on integers based on a classification of LOOP programs of limited complexity, namely those in which the depth of nestings of LOOP commands does not exceed two. It is proved that $n$-place functions in $\mathcal{L}_2^k$ can be enumerated by a single function in $\mathcal{L}_2^{k+2}$, and that the resulting hierarchy of elementary predicates (i.e., functions with 0,1-values) is proper in that there are $\mathcal{L}_2^{k+2}$ predicates that are not in $\mathcal{L}_2^{k}$. Along the way the rudimentary predicates of Smullyan are classified as $\mathcal{L}_2^{2}$.

Citation

Download Citation

Zlatan Damnjanovic. "Elementary Functions and LOOP Programs." Notre Dame J. Formal Logic 35 (4) 496 - 522, Fall 1994. https://doi.org/10.1305/ndjfl/1040408609

Information

Published: Fall 1994
First available in Project Euclid: 20 December 2002

zbMATH: 0831.03021
MathSciNet: MR1334287
Digital Object Identifier: 10.1305/ndjfl/1040408609

Subjects:
Primary: 03D20
Secondary: 68Q15

Rights: Copyright © 1994 University of Notre Dame

Vol.35 • No. 4 • Fall 1994
Back to Top