Register machines with counters
- Authors: Savitskii I.V.1
-
Affiliations:
- Faculty of Computational Mathematics and Cybernetics
- Issue: Vol 96, No 2 (2017)
- Pages: 486-487
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225390
- DOI: https://doi.org/10.1134/S1064562417050222
- ID: 225390
Cite item
Abstract
Register machines with counters (RC machines) are studied. It is shown that any computable function can be strictly computed on RC machines with a bounded number of counters and programs. The place in the Kleene–Mostowski hierarchy of certain algorithmic problems related to RC machines is determined.
About the authors
I. V. Savitskii
Faculty of Computational Mathematics and Cybernetics
Author for correspondence.
Email: savvig@gmail.com
Russian Federation, Moscow, 119991