ГДЗ по информатике, 11 класс, Босова, номер 5.6: Основные сведения об алгоритмах

План доказательства:

Для доказательства утверждения воспользуемся методом от противного. Нам нужно показать, что не существует исполнителя с бесконечным (или полным) набором допустимых действий. Предположим обратное: пусть существует некоторый исполнитель I, для которого любое мыслимое действие является допустимым.

Ход рассуждения:

1. По определению, алгоритм — это конечная последовательность команд, каждая из которых должна быть допустимой для данного исполнителя. 2. Если предположить, что для исполнителя I допустимо любое действие, то множество его команд становится неограниченным и включает в себя все возможные операции над любыми объектами. 3. Однако понятие «исполнитель» неразрывно связано с наличием конкретной среды и ограниченного набора средств воздействия на эту среду (системы команд). Исполнитель должен уметь распознавать команды и выполнять их физически или логически. 4. Рассмотрим абстрактное действие, которое противоречит законам логики или физики самой среды исполнения (например, «вычислить значение выражения, которое не имеет смысла», или «переместить объект в точку, где нет пространства»). Даже если мы формально объявим такие действия допустимыми, они не могут быть реализованы как шаги алгоритма, так как алгоритм требует однозначности и выполнимости каждого шага. 5. Более того, если набор действий не ограничен, то невозможно составить конечный список инструкций, который описывал бы поведение исполнителя. Без конечного описания системы команд исполнитель теряет свою идентичность и превращается в универсальный механизм без спецификации, что противоречит самому понятию конкретного исполнителя в информатике.

Вывод и проверка:

Предположение о существовании исполнителя, для которого допустимо любое действие, приводит к нарушению принципа дискретности и конечности описания алгоритмов. Любой реальный или теоретический исполнитель в рамках теории алгоритмов определяется через свою систему команд, которая по определению является конечным множеством. Следовательно, исходное предположение ложно, а утверждение верно: набор допустимых действий любого исполнителя ограничен.