Алг. – фундаментальное математическое понятие, объект исследования теории алгоритмов; другое понятие известно всем – это задание, раскладываемое на последовательность действий. По сути, метематика изучает алгоритмы и их составление.
Понятие «алгоритм» появилось от искаженного имени аравийского (?) математика Арь-Харизме, который разработал правило выполнения основных арифметических действий в десятеричной системе исчисления. Они изучаются сейчас в начальном разделе математики.
До 9-го века использовали римские цифры, но крестоносцы прихватизировали 10-ую.
Сегодня «алгоритм» изменился и приобрел строгие математические определения. Особенно распространенное понятие начали использовать с приходом ЭВМ, основой которой стала автоматизация поведения исполнителя.
Машины Тьюринга.
При выполнении алгоритма в интуитивном смысле мы можем пользоваться потен-циально неограниченной памятью, запоминая в процессе выполнения алгоритма по мере необходимости нужную информацию, например, на листочке бумаги. И если для решения проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение шагов алгоритма. Таким образом, по своей сути, алгоритм есть механический процесс обработки информации.
Впервые английский математик Алан Тьюринг определил понятие алгоритма исходя из понятия автоматически работающей машины; более того, он предложил формальную модель такого устройства, которое интуитивно моделирует действия человека, решающего задачу, руководствуясь некоторым алгоритмом. Это устройство было названо машиной Тьюринга.
Рассмотрим один из вариантов указанной машины.
Устройство машины Тьюринга включает в себя:
1. Внешний алфавит, т.е. конечное множество символов А =
