§ 4.6. Обобщение проблемы алгоритмической неразрешимости

Доказанные ранее теоремы об алгоритмической неразрешимости имеют общие черты. Для обобщения введем новые определения.

Две ма­ши­ны Тью­рин­га, име­ющие один и тот же внешний ал­фа­вит, бу­дем на­зы­вать взаимозаменяемыми, если, ка­ко­во бы ни бы­ло сло­во в их об­щем ал­фа­ви­те, не содер­жа­щее пус­то­го сим­во­ла, они ли­бо пе­ре­ра­ба­ты­ва­ют его в од­но и то же сло­во, ли­бо обе к не­му не­при­ме­ни­мы.

Свойст­во ма­шин Тью­рин­га на­зы­ва­ет­ся инвариантным, ес­ли лю­бые две взаимозаменяемые ма­ши­ны ли­бо обе об­ла­да­ют этим свой­ст­вом, ли­бо обе не об­ла­да­ют.

Свой­ст­во ма­шин Тью­рин­га на­зы­ва­ет­ся нетривиальным, ес­ли су­ще­ст­ву­ют как ма­ши­ны, обладающие этим свой­ст­вом, так и не об­ла­дающие им.

Т.1.5.(7) Теорема Райса (без доказательства)

Ни для ка­ко­го не­три­ви­аль­но­го ин­ва­ри­ант­но­го свой­ст­ва ма­шин Тью­рин­га не су­ще­ст­ву­ет алгоритма, по­зво­ля­юще­го для лю­бой ма­ши­ны Тьюрин­га уз­нать, об­ла­да­ет ли она этим свой­ст­вом.

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

Требуется составить программу U, которая бы по любому подаваемому ей на вход файлу X, содержащему текст программы (например, на каком-нибудь языке программирования), определяла бы, остановится ли когда-нибудь программа из файла Х в процессе своей работы, получив на вход известные данные, или "зациклится". Если программа Х зациклится, то программа U должна показать на экране фотографию юноши, иначе — девушки, после чего закончить свою работу. Кстати, такого рода "проверяющая на зацикливаемость" программа U была бы, очевидно, довольно полезна для проверки создаваемых компьютерных программ. Оказывается, написать эту "проверяющую программу" U невозможно в принципе, даже если допустить, что компьютер, на котором выполняется U, имеет сколь угодно большую память и может работать неограниченно долгое время. Если бы такая программа U была написана, то ее можно было бы легко переделать так, чтобы вместо команды вывода изображения девушки на экран она бы зацикливалась (вставить для этого, скажем, "вечный цикл"). Пусть эта переделанная программа называется U2. Что будет делать программа U2, если ей на вход подать текст программы U2 (текст себя самой)? Если она зацикливается, то она должна показать фотографию юноши и остановиться, т.е. не зациклиться. Но если она не зацикливается, это значит, что она должна зациклиться (поскольку вывод девушки в программе U был заменен на "вечный цикл"). Тем самым программа U2 оказывается в безвыходном положении, несовместимом с допущением возможности ее существования.

Задача об остановке конкретной машины на конкретной ленте

Продолжая уменьшать неопределенность при решении проблемы останова, сформулируем проблему еще более конкретно. Является ли задача останова конкретной машины Т₀ при конкретном входном слове t₀ алгоритмически разрешимой?

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

Т.1.5.(8) Теорема

Невозможно доказать алгоритмическую неразрешимость задачи об остановке конкретной машины Т₀ на конкретном входящем слове t₀.

Доказательство

Предположим противное. Пусть доказано, что не существует способа определить, остановится машина Т₀ на ленте t₀ или нет. Пусть тем или иным образом построили реальный прототип или обычный программный эмулятор данной машины. Если это прототип, то у нас есть достаточный запас ленты для медленной, но по существу, неограниченной ее подачи (например, небольшая бумажная фабрика). Тогда возможны лишь два случая: либо машина Т₀ остановится, либо нет. В первом случае проводимый эксперимент закончится однозначным выводом об остановке машины, что явно противоречило бы предположению о том, что доказана неразрешимость данной проблемы. Значит остается единственная возможность сохранить непротиворечивость утверждения – а именно признать, что машина Т₀ никогда не остановится. Т.о. доказательство того, что не существует способа определить, остановится машина Т₀ на ленте t₀ или нет, автоматом означает доказательство того, что этой остановки никогда не произойдет. Следовательно, ответ на вопрос все-таки существует, что есть явное противоречие с принятым предположением, Q.E.D.

Итак, появился принципиально другой тип проблемы. С одной стороны доказать неразрешимость этой проблемы нельзя, при всем при том, что дать эффективный алгоритм решения тоже не представляется невозможным.

Глоссарий учебного элемента

• Т.1.5.(1) Теорема Задача об остановке произвольной машины Тьюринга на произвольном входном слове алгоритмически неразрешима.

• Т.1.5.(2) Теорема Задача об остановке произвольной машины Тьюринга на пустой ленте алгоритмически неразрешима.

• Т.1.5.(3) Теорема (без доказательства) Задача об остановке конкретной универсальной машины на произвольной ленте специального типа алгоритмически неразрешима.

• Т.1.5.(4) Теорема Задача о печатании данного символа на чистой ленте точно один раз алгоритмически неразрешима.

• Т.1.5.(5)Теорема Задача о печатании данного символа на чистой ленте бесконечно много раз алгоритмически неразрешима.

• Т.1.5.(6) Теорема Задача о печатании данного символа на чистой ленте хотя бы один раз алгоритмически неразрешима.

• Две ма­ши­ны Тью­рин­га, име­ющие один и тот же внешний ал­фа­вит, бу­дем на­зы­вать взаимозаменяемыми, если, ка­ко­во бы ни бы­ло сло­во в их об­щем ал­фа­ви­те, не содер­жа­щее пус­то­го сим­во­ла, они ли­бо пе­ре­ра­ба­ты­ва­ют его в од­но и то же сло­во, ли­бо обе к не­му не­при­ме­ни­мы.

• Свойст­во ма­шин Тью­рин­га на­зы­ва­ет­ся инвариантным, ес­ли лю­бые две взаимозаменяемые ма­ши­ны ли­бо обе об­ла­да­ют этим свой­ст­вом, ли­бо обе не об­ла­да­ют.

• Свой­ст­во ма­шин Тью­рин­га на­зы­ва­ет­ся нетривиальным, ес­ли су­ще­ст­ву­ют как ма­ши­ны, обладающие этим свой­ст­вом, так и не об­ла­дающие им.

• Т.1.5.(7) Теорема Райса (без доказательства) Ни для ка­ко­го не­три­ви­аль­но­го ин­ва­ри­ант­но­го свой­ст­ва ма­шин Тью­рин­га не су­ще­ст­ву­ет алгоритма, по­зво­ля­юще­го для лю­бой ма­ши­ны Тьюрин­га уз­нать, об­ла­да­ет ли она этим свой­ст­вом.

• Т.1.5.(8) Теорема Невозможно доказать алгоритмическую неразрешимость задачи об остановке конкретной машины Т₀ на конкретном входящем слове t₀.