Университет XXI века: научное измерение

Университет XXI века: научное измерение – 2022 189 ОБ УТОЧНЕНИИ ПОНЯТИЯ АЛГОРИТМА Б. П. Ваньков Тульский государственный педагогический университет им. Л. Н. Толстого Аннотация. В статье рассматриваются уточнения понятия алгоритма при помощи машины Тьюринга, нормального алгоритма Маркова и рекурсивных функций Чёрча. Ключевые слова: алгоритм, машина Тьюринга, нормальный алгоритм, час- тично-рекурсивные функции. Понятие алгоритма формировалось с древних времён. Например, известен алгоритм Евклида последовательного деления двух целых чисел для нахожде- ния их наибольшего общего делителя и множество других. При этом практиче- ски вплоть до 40-х годов ХХ века использовалось интуитивное понятие алго- ритма, то есть решение задачи сопровождалось соответствующим описанием. Для примера рассмотрим алгоритм извлечения корня квадратного из дей- ствительного числа: 1. Разбиваем на грани по две цифры в каждой целую часть числа справа налево, а дробную – слева направо. Для получения первой цифры искомого корня извлекаем корень квадратный из крайней левой грани. 2. К полученному остатку сносим следующую грань и слева от преобразо- ванного остатка записываем удвоенное значение полученного корня, оставив место для цифры претендента, которую записываем, подписываем так, чтобы произведение полученных чисел вместилось в преобразованный остаток. В этом случае цифру-претендент записываем следующей цифрой искомого корня. 3. Переходим к пункту 2. Таким образом имеют место основные моменты интуитивного алгоритма: дискретность, детерминированность последовательности действий, приводящей к результату (получение верных цифр корня), которая может быть конечной или продолжаться сколь угодно долго или приводить в тупик (для отрицатель- ных чисел). Появление с начала прошлого века парадоксов, неразрешимых массовых проблем, необходимость строгости выводимости и эффективной вычислимости в преддверии появления ЭВМ, сподвигло научный мир к уточнению понятия алгоритма [1–3]. Одним из первых шагов в этом направлении стало появление машины Тьюринга (1936 г.), представляющей абстрактную модель умственной деятель- ности человека. Для примера рассмотрим машину, заданную программой, со- стоящей из множества команд: Т={q 1 1q 2 1R, q 2 0q 3 0R, q 3 0q 0 1}. Посмотрим, как работает машина Тьюринга, преобразуя слово 101. Имеем алфавит символов А={0, 1}, при этом первый символ (в данном случае 0) счита- ется пустым, и алфавит внутренних состояний Q={q 0 , q 1 , q 2 , q 3 } с начальным q 1 и заключительным q 0. . Иллюстрируя преобразование при помощи ленты