×

Characterization of the relations in Grzegorczyk’s hierarchy revisited. (English) Zbl 0867.03013

This paper concerns the Grzegorczyk classes \({\mathcal E}^n\) of computable functions. To each class, one can naturally associate a class of recursive relations (denoted by \({\mathcal {RE}}^n)\): to each function in \({\mathcal E}^n\), one associates the set of points (with positive integer coordinates) where it vanishes. At first sight, the definition of the classes \({\mathcal {RE}}^n\) is not inductive, i.e. \({\mathcal {RE}}^n\) is not defined as the closure under certain operations of a class of given relations. In this note a simplification of the original presentation of Grzegorczyk’s theorem stating an inductive characterization of the classes \({\mathcal {RE}}^n\) for \(n\geq 3\) is given. This simplification is inspired by the one given by H. E. Rose in his book [Subrecursion. Functions and hierarchies (1984; Zbl 0539.03018)] for the classes \({\mathcal E}^n\). The proof is performed by induction on the complexity of the graph of the functions contained in \({\mathcal E}^n\). The author remarks that this new inductive characterization of the Grzegorczyk classes \({\mathcal {RE}}^n\) does not allow to simplify the results by A. Grzegorczyk [Rozprawy Mat. 4, 46 p. (1953; Zbl 0052.24902)] and R. W. Ritchie [Trans. Am. Math. Soc. 106, 139-173 (1963; Zbl 0107.01001)] showing that the hierarchy of the classes \({\mathcal {RE}}^n\) is strict for \(n\geq 2\).
Reviewer: Ch.Michaux (Mons)

MSC:

03D20 Recursive functions and relations, subrecursive hierarchies
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] La Hiérarchie de Grzegorczyk. Univ. Mons-Hainaut, Mémoire de licence en mathématiques, juin 1993.
[2] Some classes of recursive functions. Rozprawy Matematiczne IV, Warszawa 1953. · Zbl 0052.24902
[3] Kutylowski, J. London Math. Soc. (2) 36 pp 193– (1987)
[4] Ritchie, Trans. Amer. Math. Soc. 106 pp 139– (1963)
[5] Subrecursion, Functions and Hierarchies. Clarendon Press, Oxford 1984. · Zbl 0539.03018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.