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

«Университет XXI века: научное измерение» – 2024 14 Для использования возможности расширения алфавита символов машины Тьюринга удобно рассмотреть задачу сравнения чисел (последовательностей единиц) путем добавления дополнительного символа для отмечания просматри- ваемых единиц числа поочерёдно слева и справа, с последующим восстановле- нием нужного числа и удалением при необходимости другого. Для программного решения задачи важны два аспекта: придумывание алго- ритма решения и его реализация. Так, в примере вычисления функции деления на 2 натурального числа, записанного последовательностью единиц, и имея в ка- честве пустого 0, сначала, как правило, появляется желание удаления (замена на пустой), например, каждой второй единицы. Тогда для получения частного при- дётся убирать промежуточные пустые символы, что сильно удлиняет программу. Более изящным получается алгоритм, если заменять временно, например, край- нюю правую единицу на пустой символ ( назовём его «виртуальным»), сдви- нуться к левому краю и в случае наличия единицы, заменить ее на пустой. Сдви- нувшись на правый край, заменить «виртуальный» ноль на единицу, то есть на первый элемент частного, которое строится, таким образом, сразу. Если слева ответной единицы нет, то число является нечётным и можно сдвигать ленту влево бесконечно. Дробление вычислительного процесса до простейших действий (что также подтверждает тезис Тьюринга о вычислимости по Тьюрингу всех вычислимых функций) проявляется в возможности исследования его логической структуры, что закладывает основу алгоритмического мышления. При этом наличие у машины Тьюринга потенциально бесконечной ленты побуждает человечество к бесконечному прогрессу. Основой языков преобразования символьной информации являются нор- мальные алгоритмы Маркова (конец 40-х – начало 50-х гг. ХХ века), представ- ляющие упорядоченные последовательности марковских подстановок (формул), то есть замены одного подслова (самое первое левое вхождение) преобразуемого слова на другое слово. При этом пустой символ находится перед каждым симво- лом слова. Таким образом, чтобы использовать дополнительные символы, фор- мулу, заменяющую пустой символ на дополнительный, следует располагать по- следней в алгоритме. Например, для обращения слова в некотором алфавите новый символ вво- дится для перебрасывания следующего за ним символа поочерёдно через другие до тех пор, пока слово не обратится. Затем появляется возможность замены двух одинаковых дополнительных символов на новый, который будет очищать обра- щённое слово. Таким образом закладывается эффективное использование цик- лов в вычислительных процессах. При построении нормального алгоритма Маркова для удвоения слова в не- котором алфавите на этапе создания алгоритма решения задачи следует проду- мывать строение формулы, которая будет не только дублировать символы, но иметь возможность располагать их в нужном порядке. Уточнение понятия алгоритма при помощи рекурсивных функций приводит к основам алгоритмизации и программирования, так как позволяет практически в явном виде воспринимать вычислительный процесс как вывод из аксиом