Upper mutual bounds of size and time for a turing machine and a Markov-Post algorithm for mutual simulations

Authors

  • Nikolay K. Kosovskii St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;
  • Tatiana M. Kosovskaya St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;
  • Nikolay N. Kosovskii St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;

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

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

Most read articles by the same author(s)