ТЬЮРИНГОВЫЕ ВЫЧИСЛЕНИЯ СО СТАНДАРТНОЙ ТРАЕКТОРИЕЙ ДВИЖЕНИЯ ГОЛОВКИ
Боковая панель статьи
Основное содержимое статьи
Аннотация
Работа посвящена получению нижних оценок сложности вычислений на машинах Тьюринга. Исследуется машина Тьюринга с одной лентой и одной головкой. Исследование проводится с помощью метода, основанного на специальном графическом представлении траектории движения головки. Доказано, что если емкостной характеристикой работы машины является полиномиальная функция степени k (k ≥ 2), а траектория движения головки – стандартной, то нижняя оценка временной характеристики работы машины является полиномиальной функцией степени k + 1.
Информация о статье
Библиографические ссылки
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.