О вычислениях, машинах Тьюринга и других интересных вещах. Part 2

По материалам Марвина Мински “Вычисления и автоматы”.

Как было указано в предыдущей части, для любой эффективной процедуры мы можем составить машину Тьюринга (МТ). Т.е. если у нас есть какой-то алгоритм, например алгоритм нахождения простых чисел, то одним из способов его реализации может быть МТ  (пока не будем вдаваться в тонкости работы МТ, этот вопрос мы обсудим позже на нескольких примерах).

Пойдём дальше. Наверное, не очень удобно собирать для каждой задачи свою МТ. А можно ли составить такую МТ, которая в качестве входных данных получает описание другой МТ и данные для неё?

Ответ: да, можно! Такая машина называется универсальная машина Тьюринга (УМТ), и её возможности становятся поистине колоссальными! Всё что можно представить в виде эффективной процедуры, другими словами любую задачу, которую можно сформировать в виде алгоритма, мы может решить на УМТ, подав её на вход описание нужной МТ (алгоритм) и входные данные.

Но возможности такой машины все-таки не безграничны. Существуют такие задачи, которые невозможно решить с помощью МТ. Например: проблема останова. Как мы знаем, к любому алгоритму предъявляется ряд требований, такие как:

дискретность – решение задачи представляет собой набор определённых шагов;

детерминированность – в каждый момент времени, следующий шаг определяется текущим состоянием системы;

понятность – все команды могут быть правильно интерпретированы;

массовость – алгоритм можно использовать для различных входных данных;

конечность – алгоритм должен завершиться и выдать результат.

Всем этим требованиям удовлетворяет МТ, если она им не удовлетворяет, то это не является МТ. 
Но есть задачи, которые МТ решить не может. Если на вход определенным образом сконструированной МТ подать описание другой МТ и данные для неё, то сможет ли первая МТ определить: остановится ли переданная ей МТ когда-нибудь или будет работать бесконечно. Ответ: нет, не сможет, невозможно создать такую МТ, которая получив описание другой МТ определила остановиться ли последняя.

Следствием такого положения является то, что не существует эффективной процедуру для решения данной задачи. Другими словами мы не сможем составить такую программу, которая получив на входе другую программу, ответила, завершится она или нет (в общем виде). При этом необходимо отметить, что мы рассматриваем вариант с «бесконечной» памятью. Т.к. если память будет ограниченна, без возможности расширения, то такая программа будет конечным автоматом (или конечной машиной), для которой, в отличие от МТ (бесконечной машины), мы можем ответить на этот вопрос.

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

Продолжение следует.