АЛГОРИТМИЧНО НЕРЕШИМИ ЗАДАЧИ - Логика - достъпна за всички
АЛГОРИТМИЧНО НЕРЕШИМИ ЗАДАЧИ
Едно от свойствата на алгоритъма е неговата масовост. Това означава, че алгоритъмът е начин за решаване на някакъв масов проблем, формулиран като проблем за картографиране не на една, а на цял набор от входни думи в съответните им изходни думи. По този начин всеки алгоритъм може да се разглежда като някакъв универсален инструмент за решаване на цял клас проблеми.
Оказва се, че има такива класове задачи, за чието решаване няма и не може да има единна универсална техника. Проблемите за решаване на такива задачи се наричат алгоритмично неразрешими задачи. Алгоритмичната неразрешимост на задачата за решаване на проблеми от един или друг клас обаче изобщо не означава невъзможността за решаване на конкретен проблем от този клас. Говорим за невъзможността да се решат всички задачи от даден клас по един и същи метод.
По този начин задачите (проблемите) могат да бъдат разделени на алгоритмично разрешими и алгоритмично нерешими. Пример за алгоритмично разрешима задача е задачата за доказване на идентичности в обикновената алгебра. Има една конструктивна техника (отваряне на скоби, редуциране на подобни термини), която позволява да се реши в краен брой стъпки дали дадено отношение е идентично.
Преходът от интуитивната концепция за алгоритъм към точната концепция за рекурсивна функция (машина на Тюринг, нормален алгоритъм) позволи да се докаже алгоритмичната неразрешимост на редица проблеми.
Един от първите резултати от този тип е доказателството на Чърч от 1936 г. за неразрешимостта на проблема с разпознаването на изводимостта в математическата логика.Резултатът от това доказателство е формулиран катоТеорема на Чърч (5). Проблемът с разпознаването на извеждаемостта е алгоритмично неразрешим.
Това не само разкрива причината за провала на всички минали опити за създаване на подходящ алгоритъм, но и разкрива пълната безсмисленост на подобни опити. . Няма да разглеждаме доказателството на тази теорема на Чърч поради нейната сложност. Отбелязваме само, че същността му се свежда до доказване на нерекурсивността на функцията, която решава дадения проблем.
Като пример за доказване на алгоритмична неразрешимост, разгледайте проблема с разпознаването на самоприложимостта. Има както самоприложими, така и неприложими алгоритми. Пример за самоприложим алгоритъм е така нареченият алгоритъм за идентичност във всяка азбука А, съдържаща две или повече от две букви. Този алгоритъм е приложим към всяка дума p в азбуката A и обработва всяка входна дума в себе си.
Пример за неприложим самостоятелен алгоритъм е така нареченият нулев алгоритъм във всяка крайна азбука B. Този алгоритъм се дава от верига, съдържаща едно заместване ® y (където y е всяка буква от азбуката B). По своята дефиниция той не е приложим към никоя входна дума и следователно към нейното изображение.
Проблемът с разпознаването на самоприложимостта на алгоритмите е да се намери единична конструктивна техника, която позволява в краен брой стъпки по схемата на всеки даден алгоритъм да се установи дали алгоритъмът е самоприложим или не е самоприложим.
Ще докажем алгоритмичната неразрешимост на този проблем с помощта на алгоритмични системи на Тюринг.За да направим това, ние формулираме проблема за самоприложимостта по отношение на машина на Тюринг. Нека да бъде фиксирана някаква конфигурация в машината на Тюринг. Възможни са два случая:
1) машината е приложима към тази конфигурация, т.е. след финалаброя цикли, които спира в крайната конфигурация;
2) Машината не е приложима за тази конфигурация. Това означава, че машината никога не влиза в окончателната конфигурация, тя попада в безкраен процес.
Да предположим сега, че лентата на машината на Тюринг показва свой собствен шифър (т.е. шифърът на справочната таблица и първоначалната конфигурация), написан с азбуката на машината. Ако машината е приложима към такава конфигурация, тогава ще я наречем самоприложима; в противен случай неприложима.
Тогава проблемът за разпознаване на самоприложимостта е следният: за всеки даден шифър да се определи към кой клас принадлежи машината, криптирана от него - към класа на самоприложимите или неприложимите?
Оказва се, че следната теорема (6) може да бъде доказана. Проблемът с разпознаването на самоприложимостта е алгоритмично неразрешим.
Доказателство. Да предположим, напротив, че такава машина M съществува. След това в M всеки самоприложим шифър се обработва в някакъв символ v (имащ значението на утвърдителен отговор на въпроса за самоприложимостта), а всеки неприложим шифър в символа m (имащ значението на отрицателен отговор на поставения въпрос).
В този случай би било възможно да се изгради такава машина M1, която все още обработва неприложими шифри в t, докато M1 вече не е приложим за самоприложими шифри. Това може да се постигне чрез промяна на схемата на машината (таблицата на съответствие) M, така че след появата на символа v, вместо да спре, машината да повтаря един и същ символ безкрайно дълго.
И така, M1 е приложим за всеки неприложим шифър (произвеждащ символа t в процеса) и не е приложим за самоприложими шифри. Това обаче води до противоречие.
1) тогава нека машината M1 е самоприложиматой е приложим към своя шифър M1' и го трансформира в символа t, но появата на този символ трябва да означава, че машината не е самоприложима;
2) ако M1 не е самоприложимо, то е приложимо към M1', което би трябвало да означава, че M1 е самоприложимо.
Полученото противоречие доказва теоремата, т.е. предположението ни за машината M е грешно.
Тъй като може да има безкраен брой различни думи във всяко смятане, всъщност има безкрайна поредица от един и същи тип задачи. Изисква се да се намери алгоритъм, който разпознава еквивалентността или нееквивалентността на всяка двойка думи.
Проблемът за еквивалентността на думите за асоциативни изчисления е формулиран още през 1914 г. от норвежкия математик Туе. Той също така предложи алгоритъм за разпознаване на еквивалентността на думите в някакво асоциативно смятане от специална форма. Оттогава са правени много опити да се конструира такъв общ алгоритъм, че за всяко асоциативно смятане
и за всяка двойка думи в него е позволено да се установи дали тези думи са еквивалентни или не.
През 1946 и 1947г А. А. Марков и Е. Пост, независимо един от друг, конструираха конкретни примери за асоциативни изчисления, за всеки от които проблемът за еквивалентност на думите е алгоритмично неразрешим. Освен това няма алгоритъм за разпознаване на еквивалентността на думите в което и да е асоциативно смятане.
През 1955 г. съветският математик П. С. Новиков доказва алгоритмичната неразрешимост на проблема за разпознаване на думи за асоциативни смятания от специален вид, наречен теория на групите.