Хотелось немного просвещать вопросы, связанные с вычислениями, машинами Тьюринга и т.п. На абсолютную корректность того, что излагаю, не претендую, это просто различные выдержки из книг, журналов и других источников, прошедшие через мою голову. За правки и комментарии буду очень благодарен.
При изучении вопроса о вычислениях одним из первых всплывает понятие алгоритма. Алгоритм (или эффективная процедура) как говорит Википедия - набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Если какую-либо процедуру мы можем вычислить механически (т.е. на какой-то машине, или просто вручную), то такую процедуру будем называть эффективной. И обратно, если процедуру мы называем эффективной, то её можно реализовать механически. А каким требованиям отвечает “эффективная процедура”?
Если говорить о задании эффективной процедуры как о составлении набора инструкция, то возникнет проблема в интерпретации её (инструкции) положений. Одним из способов избежать неопределённости является создание специальной интерпретирующей машины. Желательно чтобы она была достаточно универсальна. Т.е. на ней можно было бы реализовывать практически все эффективные процедуры. Иначе для каждой задачи пришлось бы составлять свою машину. Для создания интерпретирующей машины нам понадобится язык, для формирования правил, и машина, которая будет выполнять правила на указанном выше языке.
Как было показано в различной литературе можно составить универсальную машину и язык, на котором можно реализовать любую процедуру, являющуюся эффективной.
С другой стороны могут существовать такие задачи, которые невозможно представить в виде эффективной процедуры, т.е. реализовать на каком-то языке и запустить на машине. Они в первую очередь связаны со способностями мозга человека: мышление, интуиция и т.п.
Одним из примеров машины, на которой можно реализовать вычислительную процедуру является машина Тьюринга (далее МТ). “Машина Тьюринга - это машина с конечным числом состояний, соединенная с устройством особого рода - его лентой, на которой она может записывать (а потом и воспроизводить) последовательности символов”, - так пишет о МТ Марвин Минский.
В связи с данной машиной выдвигается следующее утверждение, называемое Тезис Тьюринга: “Любой процесс, который было бы естественно назвать эффективной процедурой, может быть реализован машиной Тьюринга”.
На самом деле МТ не единственный способ дать понятие эффективной процедуры. Есть например Машина Поста, общерекурсивные функции Клини и т.п. Все эти вещи эквивалентны между собой и определяю эффективную процедуру.Продолжение следует....
Комментариев нет:
Отправить комментарий