Уроки 58 - 60
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Зачем нужно определение алгоритма?
Универсальные исполнители
Универсальные исполнители
Как мы уже видели, понятие алгоритма оказывается «привязанным» к его исполнителю и некоторому языку программирования. Это не позволяет определить алгоритм как математический объект. Поэтому возникла идея попытаться построить универсальный исполнитель.
Универсальный исполнитель — это исполнитель, который может моделировать работу любого другого исполнителя.
Это значит, что для любого алгоритма, написанного для любого исполнителя, существует эквивалентный алгоритм для универсального исполнителя.
Такой исполнитель можно было бы использовать для доказательства разрешимости или неразрешимости задач. Если удаётся построить алгоритм решения задачи для универсального исполнителя, то задача разрешима. Если доказано, что алгоритм не существует, то задача неразрешима. Система команд такого исполнителя должна быть как можно проще — так его будет легче использовать в доказательствах.
В середине XX века разными учёными независимо друг от друга были предложены несколько исполнителей, претендующих на роль универсальных (они будут рассмотрены далее), причём в теории алгоритмов доказано, что все они эквивалентны друг другу. Это означает, что для любого алгоритма для одного универсального исполнителя можно построить эквивалентный алгоритм для другого универсального исполнителя.
Как же связан универсальный исполнитель с проблемой строгого определения алгоритма?
Любой алгоритм может быть представлен как программа для универсального исполнителя.
Это основная идея теории алгоритмов. Строго доказать это утверждение невозможно, потому что здесь используется интуитивное понятие «алгоритм».
Как мы увидим, каждый универсальный исполнитель описывается с помощью математических терминов, поэтому на его основе можно дать строгое определение алгоритма:
Алгоритм — это программа для универсального исполнителя.
Универсальный исполнитель — это некоторая модель вычислений, которая задаёт способ описания алгоритмов и их выполнения.
Модель вычислений должна содержать:
• «процессор», задающий систему команд и способ их выполнения;
• «память», определяющую способ хранения данных;
• язык программирования (способ записи программ);
• способ ввода данных (чтения входного слова);
• способ вывода слова-результата.
Все универсальные исполнители эквивалентны, поэтому последнее приведённое определение алгоритма не зависит от конкретного исполнителя.
Следующая страница 
Машина Тьюринга
Cкачать материалы урока
