Arithmetization of register machines with counters. (English. Russian original) Zbl 1477.03160
Mosc. Univ. Comput. Math. Cybern. 44, No. 3, 133-145 (2020); translation from Vestn. Mosk. Univ., Ser. XV 2020, No. 3, 30-42 (2020).
Summary: Register machines with counters are arithmetized in class \(\mathcal{E}^0\) of the Grzegorczyk hierarchy. As a sequence, we construct a new simple basis via superpositioning in Grzegorczyk class \(\mathcal{E}^2 \).
MSC:
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 03D20 | Recursive functions and relations, subrecursive hierarchies |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | Clote, P., Computation Models and Function Algebras, Handbook of Computability Theory (1999), Amsterdam: Elsevier, Amsterdam · Zbl 0942.68049 |
| [2] | Marchenkov, S. S., Superpositions of elementary arithmetic functions, J. Appl. Ind. Math., 1, 351-360 (2006) · Zbl 1249.03079 · doi:10.1134/S1990478907030106 |
| [3] | Mazzanti, S., Plain bases for classes of primitive recursive functions, Math. Log. Quart., 48, 93-104 (2002) · Zbl 1017.03018 · doi:10.1002/1521-3870(200201)48:1<93::AID-MALQ93>3.0.CO;2-8 |
| [4] | Volkov, S. A., Generating some classes of recursive functions by superpositions of simple arithmetic functions, Dokl. Math., 76, 566-567 (2007) · Zbl 1154.03022 · doi:10.1134/S1064562407040217 |
| [5] | Mazzanti, S., CRN elimination and substitution bases for complexity classes, Fundam. Inf., 120, 29-58 (2012) · Zbl 1260.03076 · doi:10.3233/FI-2012-748 |
| [6] | Volkov, S. A., An example of a simple quasi-universal function in the class \(\mathcal{E}^2 \), Discrete Math. Appl., 16, 513-526 (2006) · Zbl 1121.03049 · doi:10.1163/156939206779238436 |
| [7] | Mazzanti, S., Bases for \(AC^0\), Fundam. Inf., 136, 433-460 (2015) · Zbl 1348.68058 · doi:10.3233/FI-2015-1165 |
| [8] | M. L. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, N.J., 1967; Mir, Moscow, 1971). · Zbl 0195.02402 |
| [9] | Beltiukov, A. P., A machine description and a hierarchy of initial Grzegorczyk’s classes, J. Soviet Math., 20, 2280-2289 (1982) · Zbl 0493.03012 · doi:10.1007/BF01629435 |
| [10] | Clote, P., Nondeterministic stack register machines, Theoret. Comput. Sci., 178, 37-76 (1997) · Zbl 0901.68052 · doi:10.1016/S0304-3975(96)00051-5 |
| [11] | Marchenkov, S. S., Classes of Elementary Recursive Functions (2017), Moscow: Fizmatlit, Moscow |
| [12] | Savitskii, I. V., Computations on register machines with counters, Discrete Math. Appl., 28, 97-111 (2018) · Zbl 1390.68417 · doi:10.1515/dma-2018-0010 |
| [13] | Marchenkov, S. S.; Savitskii, I. V., Machines in the Theory of Computable Functions (2018), Moscow: MAKS Press, Moscow · Zbl 1397.68077 |
| [14] | Savitskii, I. V., Eliminating Inequalities in Register Machines with Counters, Moscow Univ. Comput. Math. Cybern., 43, 126-132 (2019) · Zbl 1448.68237 · doi:10.3103/S0278641919030051 |
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.
