Upper mutual bounds of size and time for a turing machine and a Markov-Post algorithm for mutual simulations
Abstract
It is proved that the use of a Turing machine and a Markov-Post algorithm having mutual upper bounds upon the time and space are interchangeable up to a linear function of the space and a polynomial under the time of the Turing machine. Not more than two-letters extension of the exterior alphabet is used. Refs 4.Keywords:
Turing machine, Markov-Post algorithm, time and space algorithm complexity, mutual upper bounds of complexity
Downloads
Downloads
Published
2015-05-01
How to Cite
Kosovskii, N. K., Kosovskaya, T. M., & Kosovskii, N. N. (2015). Upper mutual bounds of size and time for a turing machine and a Markov-Post algorithm for mutual simulations. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 2(2), 190–193. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/11148
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.