Просмотр исходного текста страницы Проблемы остановки и тождественности

{| width="100%"  
 | width="40%"|[[Немного программирования]] << 
 ! width="20%"|[[Истинность и доказуемость|Оглавление]] 
 | width="40%" align="right"| >> [[Перечислимые и разрешимые множества]]
|}
----
Мы видели, что программы бывают "хорошие" и "плохие". Плохие приводят к неопределённым или т.н. ''частичным функциям''. Их вызов, при некоторых входных значениях, не оканчивается получением результата. Поэтому Тьюринг поставил вопрос, &mdash; существует ли универсальный алгоритм, проверяющий достигнет ли данная функция инструкции '''return''' при конкретном значении её входа. Конечно, проще всего запустить программу (протестировать ее). Если она остановилась, то все нормально. Однако, если она не останавливается, то не известно &mdash; остановится ли она когда-нибудь или будет работать бесконечно долго. Для некоторых программ (например, получения предыдущего числа <math>\textstyle \mathbf{p}(x)</math> при <math>\textstyle x=0</math>) легко понять, что они никогда не остановятся, даже не запуская их. Однако мы пытаемся выяснить существует ли ''универсальный'' алгоритм, который способен решить проблему остановки для любой программы. Тьюринг показал, что такой алгоритм ''невозможен''. Это утверждение носит название "''Теорема об остановке''".

Так как алгоритмы (функции) оперируют только с целыми числами, необходимо разобраться как они будут рассматривать тексты программ. Ранее мы договорились, что программа &mdash; это некоторая конечная строка символов из конечного алфавита. Поэтому, все возможные программы можно отсортировать сначала по длине, а при одинаковой длине &mdash; по алфавиту (лексографический порядок). Каждая получит порядковый номер. Выше это и предполагалось, так как имя каждой функции имело вид <math>\textstyle f_i</math>, где <math>\textstyle i</math> &mdash; некоторое натуральное число.

Соответствие "текст функции" <math>\textstyle \to</math> "целое число" можно проделать и более удобным образом. Если все символы (буквы) алфавита пронумеровать, то каждый символ текста программы можно считать некоторым целым положительным числом. Поэтому программа может быть описана конечной последовательностью чисел: <math>\textstyle x_1,\;x_2,...,x_n</math>, являющимися номерами каждого символа. При желании, эти <math>\textstyle n</math> чисел можно свернуть в одно при помощи последовательности простых чисел: <math>\textstyle x=2^{x_1}\cdot 3^{x_2}\cdot ...\cdot p_{n}^{x_n}</math>. Это и будет уникальный номер нашей программы.

Такое представление удобно тем, что легко провести обратную операцию и, разложив номер программы на простые множители, получить её текст в виде последовательности <math>\textstyle x_1,\;x_2,...,x_n</math>. Естественно, подобные действия являются алгоритмическими, и существует функция <math>\textstyle \mathbf{g}(x, i)</math>, дающая <math>\textstyle i</math>-й "символ" программы под номером <math>\textstyle x</math>. Буква <math>\textstyle \mathbf{g}</math> дана программе в честь Гёделя, который подобным образом предложил нумеровать формулы.

<math>\textstyle \bullet</math> Вернёмся к Проблеме Остановки и рассмотрим сначала простое рассуждение, отличное от того, которое сделал сам Тьюринг. Будем большими буквами обозначать имена программ (алгоритмов), подразумевая, что за этим именем скрывается строка символов, которая его задаёт. Маленькими буквами обозначим целочисленный номер этого алгоритма. Так, <math>\textstyle q</math> &mdash; это номер алгоритма (строки) <math>\textstyle Q</math>.

Пусть существует функция <math>\textstyle T(p,i)</math>, которая по номерам <math>\textstyle p</math>-той программы и её <math>\textstyle i</math>-тых входных данных возвращает 1, если эта программа завершается, выдав результат, и ноль в противном случае:

:<center><math>T(p, i):\; \left\{ \begin{array}{l} 1,\;\;\;если\;P(i)\;возвращает\;значение\\ 0,\;\;\;если\;P(i)\;не\;возвращает\\ \end{array} \right.</math></center>

Докажем теорему: <blockquote> ''Функция <math>\textstyle T(p,i)</math> не существует''. </blockquote> Пусть это не так, и <math>\textstyle T(p,i)</math> существует. Определим ещё одну функцию:

:<center><math>Q(x):\; \left\{ \begin{array}{ll} 1,\;\;\;&если\;T(x,x)=0\\ \infty,\;\;&если\;T(x,x)=1.\\ \end{array} \right.\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;</math></center>

Символ <math>\textstyle \infty</math> означает, что если <math>\textstyle T(x,x)=1</math>, то мы зациклим программу <math>\textstyle Q</math>, не дав ей остановиться. Например, в этом случае будет запускаться строка "'''while'''(1=1)<math>\textstyle \{\}</math>". Вычислим теперь значение <math>\textstyle Q(q)</math>, передав ей её ''собственный номер'':

:<center><math>\left\{ \begin{array}{ll} 1, &если\;T(q,q)=0\;\;:если\;Q\;не\;завершается,\;то\;Q\;завершается = 1\\ \infty, &если\;T(q,q)=1\;\;:если\;Q\;завершается,\;то\;Q\;не\;завершается \,(\infty)\\ \end{array} \right.</math></center>

Мы пришли к противоречию, значит теорема верна <math>\textstyle \square</math>.

В доказательстве обсуждается два объекта: "неконструктивная" функция <math>\textstyle T(p,i)</math> (текста которой мы не предъявляем) и "конструктивная" <math>\textstyle Q(x)</math>. Поэтому противоречие должно свидетельствовать в пользу теоремы.

Однако, на самом деле мы доказали несколько более слабое утверждение: <blockquote> ''Не существует функции способной проанализировать свой текст и выяснить, остановится она или нет.'' </blockquote> При этом не существенно, анализируется ли собственный текст на прямую или через несколько вызовов других функций. Действительно, противоречие получено при применении алгоритма к функции <math>\textstyle Q</math>, которая его же и использует. Поэтому для ''таких'' случаев алгоритма решающего проблему остановки нет!

<math>\textstyle \bullet</math> Исходные рассуждения Тьюринга выглядели несколько по-другому. Рассмотрим все программы, вычисляющие функции от одного аргумента. Их бесконечно много, но они ''счётны'': <math>\textstyle F_k(x):\{F_0(x),\;F_1(x),\;....\}</math>, т.е. пронумерованы (нумерацию ведём с нуля). Пусть существует функция <math>\textstyle T(p,i)</math> определённая выше. Тогда рассмотрим функцию:

:<center><math>F(x):\; \left\{ \begin{array}{ll} F_x(x)+1,\;\;\;&если\;T(x,x)=1,\;т.е.\;F_x\;при\;x\;определена\\ 0, \;\;\;&если\;T(x,x)=0,\;т.е.\;F_x\;при\;x\;не\;определена.\\ \end{array} \right.</math></center>

Она отлична от всех функций <math>\textstyle F_k(x)</math>. Действительно, если значение функции <math>\textstyle F_0(0)</math> определено, то <math>\textstyle F(0)=F_0(0)+1</math> и не равно <math>\textstyle F_0(0)</math>. Если же значение <math>\textstyle F_0(0)</math> не определено (она не останавливается), то <math>\textstyle F(0)</math> определено и равно 0. Поэтому <math>\textstyle F(x)</math> отлична от <math>\textstyle F_0(x)</math> при <math>\textstyle x=0</math>. Аналогично <math>\textstyle F(x)</math> отлична от <math>\textstyle F_1(x)</math> при <math>\textstyle x=1</math>, и т.д. Но это противоречит тому, что ''все'' функции были пронумерованы. Поэтому объект <math>\textstyle T(p,i)</math> использовавшийся при построении <math>\textstyle F(x)</math> невозможен, и теорема доказана <math>\textstyle \square</math>.

Мы уже видели, что заканчивать доказательство от противного, такой жизнеутверждающей фразой, необходимо предельно осторожно. В сделанных рассуждениях предполагается, что алгоритм <math>\textstyle T(p,i)</math> ''применим'' ко ''всем'' функциям, включая такие, которые вызывают и его (например к <math>\textstyle Q(x)</math> описанной на предыдущей странице). Однако, это не так, и к таким функциям <math>\textstyle T(p,i)</math> не применим. Поэтому, фактически противоречия не возникает, так как отличить <math>\textstyle F(x)</math> от некоторых функций нельзя.

<math>\textstyle \bullet</math> Так как алгоритма решающего проблему остановки и применимого к самому себе не существует, то естественно не существует и ''универсальных'' алгоритмов, применимых ко ''всем'' программам. А это, собственно, и составляло теорему Тьюринга.

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

Таким образом, мы получили чёткий критерий области неприменимости алгоритма <math>\textstyle T(p,i)</math>. Все программы которые в него ''не'' попадают вообще говоря ''могут'' быть проанализированы <math>\textstyle T(p,i)</math>, и в этом случае он ''может'' и решать проблему остановки. Мы видим, что в таких психологических доказательствах от противного, необходимо очень осторожно выявлять объекты и утверждения приведшие к противоречию.

Рассмотрим теперь как можно выяснить используется данный алгоритм некоторой функцией или нет.

<math>\textstyle \bullet</math> Каждой функции можно поставить в соответствие множество имён (или номеров) других функций, которые она использует при своей работе ("''множество зависимостей''"). Для этого необходимо использовать алгоритм "поиска в ширину": <blockquote> Возьмём пустой список целых чисел. Поместим в него номера всех функций которые явным образом присутствуют в тексте программы. Затем просмотрим текст каждой из них и добавим в список ''только'' те функции, которых там ещё нет. Для всех ''добавленных'' операцию повторяем, пока добавления не прекратятся. </blockquote> Понятно, что для многих функций множества зависимостей будут или пустые или конечные. Например, если:

:<center><math>f_1()\{\;\mathbf{return}\;f_2();\;\}\;\;\;\;f_2()\{\;\mathbf{return}\;f_3();\;\}\;\;\;\;f_3()\{\;\mathbf{return}\;f_1();\;\},</math></center>

то функции <math>\textstyle f_1</math> соответствует множество зависимостей <math>\textstyle \{2, 3, 1\}</math>, т.е. вызовы второй, третьей и исходной функций. Однако, не сложно представить и бесконечную цепочку таких зависимостей. В этом случае алгоритм не остановится, добавляя в множество зависимостей всё новые номера. К слову, понятно, что не может быть и универсального алгоритма, за конечное число шагов выясняющего вычислимость подобной функции.

Тем не менее, алгоритм поиска в ширину может быть остановлен на любой заданной глубине вложенности вызовов функций. В этом случае он позволяет для данной функции всегда установить, имеет ли она конечное множество зависимостей размера не более некоторого <math>\textstyle n</math>. Рассматривая только такие функции, мы сильно сузим класс возможных алгоритмов. Однако, для деятельности человеческих существ с ограниченной памятью этот класс важен, так как именно с такими алгоритмами мы обычно и "имеем дело". В конечном счёте, ведь мы определили, что алгоритм &mdash; это ''конечная'' последовательность инструкций. Поэтому можно сформулировать следующую задачу: <blockquote>''Существует ли алгоритм решающий, проблему остановки для функций имеющих множество зависимостей не длиннее некоторого <math>\textstyle n</math>, и не использующих этого алгоритма?'' </blockquote>

Решение даже такой ограниченной задачи сталкивается с другой неприятностью. Любую функцию можно вызвать не напрямую, а просто повторить её код в текущей функции. В этом случае алгоритм построения множества связей сможет работать только если есть решение другой проблемы, которую мы сформулируем в таком виде: <blockquote>''Существует ли универсальный алгоритм, который выясняет тождественность двух функций?'' </blockquote>

<math>\textstyle \bullet</math> Понятно, что одна и та же функция (т.е. отображение <math>\textstyle x\mapsto y</math>) может быть задана при помощи различных алгоритмов. Например, существующий алгоритм можно изменить, добавив к результату единицу, а после этого вычитая её. Это будет другой алгоритм этой же функции.

Алгоритм, проверяющий равенство двух функций на данном входе, ''эквивалентен'' алгоритму решающему проблему остановки. Если мы знаем при помощи <math>\textstyle T(p,i)</math>, что две программы <math>\textstyle p_1</math> и <math>\textstyle p_2</math> останавливаются, мы просто их запускаем на входе <math>\textstyle i</math> и сравниваем результаты. Если обе не останавливаются, то они на <math>\textstyle i</math> тождественны. Возможно и обратное использование. Если есть алгоритм тождественности <math>\textstyle E(p_1,p_2, i)</math>, то программу <math>\textstyle p_1</math> можно сравнить, например с функцией <math>\textstyle \mathbf{f}(i)\{\;\mathbf{while}(1=1)\{\}\;\}</math>, и если они тождественны, то <math>\textstyle p_1</math> не останавливается. Таким образом, мы должны признать, что существование алгоритма решающего как проблему остановки, так и проблему тождественности, даже для ограниченного класса функций, может оказаться под большим вопросом.

Тем не менее, ситуация не полностью безнадёжна. Легко указать, как минимум, один бесконечный класс достаточно нетривиальных функций, для которых алгоритм <math>\textstyle T(p,i)</math> существует: <blockquote> Функции, не использующие операции <math>\textstyle \mathbf{goto}</math> и вызывающие только ''примитивно рекурсивные'' функции, всегда останавливаются. </blockquote> Примером примитивной рекурсии является реализация функции <math>\textstyle \mathbf{mult}</math> на стр. \pageref{prg_mult_rec}. В общем случае она определяется так:

<center>[[File:logic8.png]]</center>

где <math>\textstyle {\mathcal P}</math> &mdash; любой код, который не использует оператор <math>\textstyle \mathbf{goto}</math>, вызова функции <math>\textstyle \mathbf{f}(x,y)</math>, и каких-либо функций являющихся не всюду определёнными. Кроме этого, он не должен изменять значение <math>\textstyle y</math>. Функция <math>\textstyle \mathbf{p}(y)</math> возвращает предыдущее значение <math>\textstyle y</math>, т.е. <math>\textstyle y\leftarrow y-1</math>. Она не определена при <math>\textstyle y=0</math>, но это контролируется первой строкой функции <math>\textstyle \mathbf{f}(x,y)</math>.

В определении <math>\textstyle \mathbf{f}(x,y)</math> используются две ''всюду определённые'' вычислимые функции <math>\textstyle \mathbf{g}(x)</math> и <math>\textstyle \mathbf{h}(x,y,z)</math>. То, что они всюду определены, должно устанавливаться на предыдущих итерациях алгоритма <math>\textstyle T(p,i)</math>, поддерживающего список уже проанализированных функций, и тех из них, которые являются примитивно рекурсивны. При помощи примитивной рекурсии можно организовать циклические вычисления, не используя <math>\textstyle \mathbf{goto}</math>. Поэтому они позволяют задать очень широкий класс функций.

Возможны различные расширения класса всюду определённых функций. В частности, вместо аргумента <math>\textstyle x</math> везде может стоять несколько аргументов <math>\textstyle x_1,...,x_n</math>, и тем самым будут определяться всюду вычислимые функции от <math>\textstyle n+1</math> аргументов. Можно разрешить в <math>\textstyle \mathcal P</math> изменения <math>\textstyle y</math>, которые его не увеличивают и не приводят к значению <math>\textstyle y=0</math>, и т.д.

Для подобных всюду определённых функций можно написать алгоритм их ''разрешения'', т.е. выяснения принадлежат ли они к данному классу или нет. Если да, то алгоритм решающий задачу остановки <math>\textstyle T(p,i)</math> вернёт 1. Если же функция не принадлежит к этому классу, то алгоритм <math>\textstyle T(p,i)</math> должен вообще говоря вернуть 2 (="не знаю" <math>\textstyle \ddot\smile</math>).

Можно также определить достаточно широкий класс алгоритмов частичных функций, которые определены не всюду, но при этом проблема остановки для них также решается. Примером таких функций была <math>\textstyle \mathbf{p}(x)</math> или вычислимая, но всюду не определённая функция <math>\textstyle \mathbf{Inf}(x)\;\{\;\mathbf{while}(1=1)\;\{\; \}\}</math>. Для этого класса существует разрешающий алгоритм выяснения принадлежности. Если функция под номером <math>\textstyle p</math> принадлежит этому классу, то <math>\textstyle T(p,i)</math> вернёт 0, в противном случае снова 2.

С практической точки зрения компьютерных наук максимальное расширение обоих классов играет исключительно важное значение. Однако, общая проблема остановки остаётся, и всегда будут алгоритмы, которые не попадают ни в один из этих классов. Мы вынуждены признать, что существует бесконечное количество алгоритмов для которых нельзя выяснить останавливаются они когда-либо или нет. Как минимум, это алгоритмы явно или не явно использующих саму функцию, решающую задачу остановки <math>\textstyle T(p,i)</math>. При этом выяснить используют они её или нет, вообще говоря, также алгоритмически нельзя.

<math>\textstyle \bullet</math> Прежде чем идти дальше, полезно поразмышлять над следующей проблемой. В математике нет ограничений на быстродействие компьютера. Т.е. каждая элементарная операция алгоритма может быть выполнена за сколь угодно короткое время <math>\textstyle \Delta t</math>. Если функция вычислима, то её алгоритм, совершив ''конечное'' число действий <math>\textstyle n</math>, останавливается и выдаёт результат. А это значит, что каким бы большим не было <math>\textstyle n</math>, время вычисления функции <math>\textstyle n\Delta t</math> можно сделать сколь угодно малым, в пределе <math>\textstyle \Delta t\to 0</math> (ограничений нет!), в том числе и нулевым. Но тогда не должно быть и Проблемы Остановки. Любая определённая при данном <math>\textstyle x</math> функция сразу выдаёт результат, а неопределённая не выдаёт. Между алгоритмом с большим, но ''конечным'' числом шагов и алгоритмом с бесконечным числом шагов существует принципиальная разница. Это два разных класса алгоритмов. Но различить их надо без компьютеров...

----
{| width="100%"  
 | width="40%"|[[Немного программирования]] << 
 ! width="20%"|[[Истинность и доказуемость|Оглавление]] 
 | width="40%" align="right"| >> [[Перечислимые и разрешимые множества]]
|}
----
[[Истинность и доказуемость]] - о конструктивной математике, Канторе и Гёделе