Turing Computations with A Standard Head Trajectory
Article Sidebar
Main Article Content
Abstract
This paper is devoted to establishing lower bounds on the computational complexity of Turing machines. The study focuses on a single-tape, single-head Turing machine. The analysis is carried out using a method based on a specific graphical representation of the head movement trajectory. It is proven that if the space complexity of the machine is given by a polynomial function of degree k (k ≥ 2), and the head trajectory is standard, then the lower bound of the time complexity of the machine is a polynomial function of degree k + 1.
Article Details
References
1. Барздинь, Я. М. Сложность распознавания симметрии на машинах Тьюринга / Я. М. Барздинь // Проблемы кибернетики. – 1965. – Вып. 15. – С. 245–248.
2. Фрейвалд, Р. В. Сложность распознавания симметрии па машинах Тьюринга со входом / Р. В. Фрейвалд // Алгебра и логика. Семинар. – 1965. – № 1. – С. 47–58.
3. Трахтенброт, Б. А. Сложность алгоритмов и вычислений / Б. А. Трахтенброт. – Новосибирск : НГУ, 1967. – 198 с.
4. Hartmanis, J. Computational complexity of one tape Turing machine computations / J. Hartmanis // Assoc. Comput. Mach. – 1968. – Nr 2. – Р. 325–339.
5. Мощенский, В. А. К вопросу о сложности тьюринговых вычислений / В. А. Мощенский // Доклады АН БССР. – 1969. – № 10. – С. 871–878.
6. Мощенский, В. А. Об оценке некоторых функций, характеризующих работу машин Тьюринга / В. А. Мощенский // Кибернетика. – 1971. – № 1. – С. 34–40.
7. Мощенский, В. А. Обобщенный метод нитей и некоторые его применения / В. А. Мощенский. – Мн. : БГУ, 2000. – 69 с.
8. Будько, А. Е. Об одной технике исследования тьюринговых вычислений / А. Е. Будько // Веснік ВДУ. – 2024. – № 1 (122). – С. 14–22.