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