This article is cited in 7 papers

An example of a simple quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy

S. A. Volkov


Abstract: We give an example of a quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy. This function is of very simple structure and does not contain an explicit enumeration of any Turing machine. As a corollary we obtain a simple basis over superposition in the class $\mathcal E^2$.

UDC: 519.7

Received: 21.04.2005

DOI: 10.4213/dm71

 English version: Discrete Mathematics and Applications, 2006, 16:5, 513–526

Bibliographic databases:

• 
• 
• 
•