Алгоритмічно нерозв'язні проблеми

Одним із властивостей алгоритму є його масовість. Це означає, що алгоритм являє собою спосіб рішення деякої масової проблеми, формулюемої у вигляді проблеми відображення не одного, а цілої множини вхідних слів у відповідні їм вихідні слова. Таким чином, усякий алгоритм можна розглядати як деякий універсальний засіб для рішення цілого класу задач.

Виявляється, що існують такі класи задач, для рішення яких немає й не може бути єдиного універсального прийому. Проблеми рішення такого роду задач називають алгоритмічно нерозв'язними проблемами. Однак алгоритмічна нерозв'язність проблеми рішення задач того або іншого класу зовсім не означає неможливість рішення будь-якої конкретної задачі із цього класу. Мова йде про неможливість рішення всіх задач даного класу тим самим прийомом.

Таким чином, задачі (проблеми) можна розділити на алгоритмічно розв'язні й алгоритмічно нерозв'язні. Прикладом алгоритмічно розв'язної проблеми є проблема доказу тотожностей у звичайній алгебрі. Існує єдиний конструктивний прийом (розкриття дужок, приведення подібних членів), що дозволяє за скінченне число кроків вирішити, чи є будь-яке задане співвідношення тотожним.

Перехід від інтуїтивного поняття алгоритму до точного поняття рекурсивної функції (машини Т'юрінга, нормального алгоритму) дозволив довести алгоритмічну нерозв'язність ряду проблем.

Одним з перших результатів такого типу є доказ нерозв'язності проблеми розпізнавання виводимості в математичній логіці, виконаної Черчем в 1936 р. Результат цього доказу формулюється як теорема Черча (5). Проблема розпізнавання виводимості алгоритмічно нерозв'язна. Тим самим не тільки з'ясовується причина безуспішності всіх минулих спроб створення відповідного алгоритму, але й виявляється повна безглуздість таких спроб.

Доказ даної теореми Черча розглядати не будемо через його складність. Відзначимо лише, що суть його зводиться до доказу нерекурсивності функції, що вирішує дану задачу.

Як приклад доказу алгоритмічної нерозв'язності розглянемо проблему розпізнавання самозастосовності. Існують як самозастосовні, так і несамозастосовні алгоритми. Прикладом самозастосовного алгоритму є так званий тотожний алгоритм у будь-якому алфавіті А, що містить дві або більше двох букв. Цей алгоритм застосовний до будь-якого слова р в алфавіті А и переробляє будь-яке вхідне слово в себе.

Прикладом не самозастосовного алгоритму є так званий нульовий алгоритм у будь-якому скінченному алфавіті В. Цей алгоритм задається схемою, що містить єдину підстановку —y (де y — будь-яка буква алфавіту В). По своєму визначенню він не застосовний ні до якого вхідного слова, а виходить, і до свого зображення.

Проблема розпізнавання самозастосовності алгоритмів полягає в тому, щоб знайти єдиний конструктивний прийом, що дозволяє за скінченне число кроків за схемою будь-якого даного алгоритму довідатися, є алгоритм самозастосовним або не самозастосовним.

Доказ алгоритмічної нерозв'язності даної проблеми будемо проводити, використовуючи алгоритмічні системи Т'юрінга.

Для цього сформулюємо проблему самозастосовності в термінах машини Т'юрінга. Нехай у машині Т'юрінга зафіксована яка-небудь конфігурація. Можливі два випадки:

1) машина застосовна до цієї конфігурації, тобто після скінченного числа тактів вона зупиняється в заключній конфігурації;

2) машина не застосовна до цієї конфігурації. Це означає,

що машина ніколи не переходить у заключну конфігурацію, вона впадає в нескінченний процес.

Припустимо тепер, що на стрічці машини Т'юрінга зображений її власний шифр (тобто шифр таблиці відповідності й вихідної конфігурації), записаний в алфавіті машини. Якщо машина застосовна до такої конфігурації, то будемо називати її самозастосовною, у іншому випадку - не самозастосовною.

Тоді проблема розпізнавання самозастосовності полягає в наступному: по будь-якому заданому шифрі встановити, до якого класу належить машина, зашифрована їм, - до класу самозастосовних або несамозастосовних?

Виявляється, можна довести наступну теорему (6). Проблема розпізнавання самозастосовності алгоритмічно нерозв'язна.

Доказ. Припустимо, навпроти, що така машина М існує. Тоді в М усякий самозастосовний шифр переробляється в якийсь символ V (що мае зміст позитивної відповіді на поставлене питання про самозастосовність), а всякий несамозастосовних шифр — у символ х (що мае зміст негативної відповіді на поставлене питання).

У такому випадку можна було б побудувати й таку машину М₁, що як і раніше переробляє несамозастосовні шифри в т, у той час як до самозастосовних шифрів M₁ уже не застосовна. Цього можна домогтися шляхом такої зміни схеми машини (таблиці відповідності) М, щоб після появи символу v замість зупинки машина стала б необмежено повторювати цей же символ.

Отже, М₁ застосовна до всякому несамозастосовного шифру (виробляючи при цьому символ т) і не застосовна до самозастосовних шифрів. Однак це приводить до протиріччя.

Дійсно:

1) нехай машина M₁ самозастосовна, тоді вона застосовна до свого шифру й переробляє його в символ т, але поява цього символу саме й повинна означати, що машина несамозастосовна;

2) нехай М₁ несамозастосовна, тоді вона застосовна до М₁', що повинне означати, що М₁ самозастосовна.

Отримане протиріччя доводить теорему, тобто наше припущення про машину М невірно.

Із цієї теореми випливає алгоритмічна нерозв'язність більш загальної проблеми - проблеми розпізнавання застосовності. Суть цієї проблеми полягає в наступному: установити застосовність будь-якої заданої машини до будь-якої заданої конфігурації.

Доказу теореми про самозастосовність алгоритму можна виконати, використовуючи нормальні алгоритми. У термінах нормальних алгоритмів проблема самозастосовності формулюється в такий спосіб.

Проблема розпізнавання самозастосовності алгоритмів полягає в тому, щоб знайти єдиний конструктивний прийом, що дозволяє за скінченне число кроків за схемою будь-якого даного алгоритму А довідатися, є алгоритм А самозастосовним або несамозастосовним.

Якщо вважати справедливим принцип нормалізації, можна припустити, що єдиний конструктивний прийом — це не що інше, як нормальний алгоритм В, певний на будь-якому слові р, що є зображенням довільного нормального алгоритму А, і переводячим це слово у два різних фіксованих слова q₁ й q₂ залежно від того, буде алгоритм А самозастосовним або несамозастосовним (слово q₁ відповідає самозастосовності, а q₂ — несамозастосовності).

На будь-якому вхідному слові l, що не є зображенням якого-небудь (нормального) алгоритму, алгоритм B також повинен бути визначений. Дійсно, у іншому випадку, не одержавши ніякого результату після досить великої кількості кроків роботи алгоритму, невідомо було б, зображенням якого алгоритму — самозастосовного або несамозастосовного — є слово l. Очевидно, що результат застосування алгоритму В к будь-якому слову, що не є зображенням алгоритму, повинен бути відмінним як від слова q₁, так і від слова q₂.

Припустимо, що алгоритм B с зазначеними властивостями існує. У такому випадку існує нормальний алгоритм С у тім же самому алфавіті X, що й алгоритм В, певний на всіх тих і тільки тих словах в алфавіті X, які є зображеннями несамозастосовності алгоритмів (нагадаємо, що по самому визначенню алгоритму В алфавіт X містить у собі стандартний двійковий алфавіт).

Дійсно, побудуємо нормальний алгоритм D в алфавіті X, область визначення якого складається з одного лише слова q₂. Такий алгоритм може бути заданий, наприклад, у вигляді суперпозиції двох нормальних алгоритмів D₁ й D₂, перший з яких задається схемою, що складається з однієї підстановки q₂—>• , а другий — схемою, що складається з підстановок виду x_i—>x_i де x_i послідовно приймає значення всіх букв алфавіту X. Ясно, що перший алгоритм переводить у порожнє слово тільки слово q₂, а область визначення другого алгоритму складається тільки з порожнього слова. Тому область визначення суперпозиції D алгоритмів D₁ й D₂ буде складатися тільки зі слова q₂ що й потрібно.

Побудувавши алгоритм D, образуя суперпозицію з ним алгоритму В и нормалізуючи цю суперпозицію, прийдемо до нормального алгоритму С у алфавіті X, область визначення якого складається із всіх тих і тільки тих слів в алфавіті X, які є записами несамозастосовних алгоритмів. Однак подібна властивість алгоритму C внутрішньо суперечлива, оскільки до свого власного зображення С^U алгоритм C не може бути застосовний й не застосовний.

Справді, у першому випадку алгоритм C був би. застосовний до свого зображення й був би тому самозастосовним. Але це суперечило б тому, що алгоритм С у силу своеї побудови повинен бути застосовним тільки до несамозастосовних алгоритмів. У другому випадку, будучи незастосовним до свого зображення, алгоритм С належав би до числа несамозастосовних алгоритмів. Але тоді по визначенню алгоритм С повинен був би бути застосовним до свого зображення, оскільки він застосовний до зображення всіх несамозастосовних алгоритмів. Отже, алгоритм С є самозастосовним.

Таким чином, припущення про алгоритмічну можливість розв'язання проблеми розпізнавання самозастосовності приведе до логічного протиріччя й тому невірне. Тим самим показана алгоритмічна нерозв'язність цієї проблеми.

Висновок обґрунтований нами лише за умови, що принцип нормалізації алгоритмів справедливий. Однак природа протиріччя, використаного при доказі алгоритмічної нерозв'язності проблеми розпізнавання самозастосовності алгоритмів, є в дійсності більш глибокою. Читач, знайомий з парадоксами теорії множин і математичної логіки, легко помітить, що зазначене протиріччя має ту ж природу, що й протиріччя у відомому парадоксі Рассела, що встановлює внутрішню суперечливість поняття «множина всіх множин, не утримуюче себе як свій елемент».

Ця обставина приводить до висновку, що алгоритмічна нерозв'язність проблеми розпізнавання самозастосовності не є наслідком вузькості сучасного точного поняття алгоритму. Якби вдалося побудувати точне поняття алгоритму, що включає в себе деякі ненормалізуемі алгоритми, то проблема розпізнавання самозастосовності алгоритмів як і раніше залишалася б алгоритмічно нерозв'язної.

При доказі алгоритмічної нерозв'язності проблеми розпізнавання самозастосовності був використаний метод «від противного». За допомогою цього методу доведена алгоритмічна нерозв'язність множини різних проблем, у тому числі й проблема еквівалентності слів для асоціативних вирахувань.

Розглянемо цю проблему більш детально.

Умовимося називати асоціативним вирахуванням сукупність всіх слів у деякому алфавіті разом з якою-небудь скінченною системою підстановок. Щоб задати асоціативне вирахування, досить указати відповідний алфавіт і систему підстановок.

Ми будемо розглядати перетворення одних слів в інші за допомогою деяких припустимих підстановок, які задаються у вигляді: р — q або р-q, де р и q — слова в одному й тому самому алфавіті.

Перша із цих підстановок називається неорієнтованою, друга - орієнтованою.

Орієнтована підстановка означає заміну р на q, тобто замість лівої частини підставляється права частина. Неорієнтована підстановка означає допустимість заміни лівої частини правою, і навпаки, правої частини — лівою (тобто р на q або q на р).

Розглянемо приклад асоціативного вирахування, заданого алфавітом А = {а, b, с} і підстановкою ab — bcb. Розглянемо слово abcbcbab. Заміна кожного із двох входжень ab дає слово abcbcbab—>bcbcbcbab—>bcbcbcbbcb. Заміна ж bcb дає слово abcbcbab—>aabcbab—>aaabab.

Якщо слово r може бути перетворене в слово s за допомогою однократного застосування припустимої підстановки, то й s може бути перетворене в r таким же шляхом. Такі слова r й s будемо називати суміжними.

Два слова r й s називаються суміжними, якщо одне з них може бути перетворене в інше за допомогою однократного застосування припустимої підстановки.

Послідовність суміжних слів, що веде від r₁ до r_n, будемо називати дедуктивним ланцюжком від r₁ до r_n.

Слова r й s називаються еквівалентними, якщо існує дедуктивний ланцюжок, що веде від слова r до слова s, і навпаки, від слова s до слова r.

Еквівалентність будемо позначати як r~s. Еквівалентність слів а) рефлексивна, тобто r~ r; б) симетрична, тобто якщо r~s, те s~r; в) транзитивна, тобто якщо s~ г, r~t, то s~t.

Для кожного асоціативного вирахування виникає своя спеціальна проблема еквівалентності слів. Вона полягає в наступному.

Для будь-яких двох слів у даному вирахуванні потрібно довідатися, еквівалентні вони чи ні.

Оскільки різних слів у будь-якому вирахуванні може бути незліченна множина, то фактично тут є нескінченна серія однотипних задач. Потрібно знайти алгоритм, що розпізнає еквівалентність або нееквівалентність будь-якої пари слів.

Проблема еквівалентності слів для асоціативних вирахувань була сформульована ще в 1914 р. норвезьким математиком Туе. Їм же був запропонований алгоритм для розпізнавання еквівалентності слів у деяких асоціативних вирахуваннях спеціального виду. З тих пор уживали багато спроб побудувати такий загальний алгоритм, що для будь-якого асоціативного вирахування й для будь-якої пари слів у ньому дозволив установити, еквівалентні ці чи слова ні.

В 1946 й 1947 р. А. А. Марков й Е. Пост, незалежно один від іншого, побудували конкретні приклади асоціативних вирахувань, для кожного з яких проблема еквівалентності слів алгоритмічно нерозв'язна. Тим більш не існує алгоритму для розпізнавання еквівалентності слів у будь-якому асоціативному вирахуванні.

В 1955 р. математик П. С. Новіков довів алгоритмічну нерозв'язність проблеми розпізнаваемості слів для асоціативних вирахувань спеціального виду називаних теорією груп.

Перші приклади, побудовані А. А. Марковим і П. С. Новиковим для спростування алгоритмічної можливості розв'язання проблемиеквівалентності, були досить громіздкими й нараховували сотні припустимих підстановок.

Пізніше радянським математиком Г. С. Цейтіним був побудований приклад асоціативного вирахування, що нараховує всього лише сім припустимих підстановок, для якого проблема еквівалентності слів була також алгоритмічно нерозв'язна.

Приклад цього асоціативного вирахування ми й розглянемо. Задані: алфавіт А = (а, b, c, d, е) і система припустимих підстановок: ас— са, ad — da, bc — cb, bd — db, abac-—abacc, eca — ae, edb — be.

Якщо взяти слово abcde у цьому вирахуванні, то до нього застосовна тільки третя підстановка й воно має тільки одне суміжне слово acbde. Далі має місце еквівалентність abcde~ cadedb, що видно з наступного дедуктивного ланцюжка:

abcde-acbde->cabde-f-cadbe->cadedb.

Якщо ж взяти слово aaabb, то до нього незастосовна жодна з підстановок, і тому воно не має ніяких суміжних слів. Не існує й слів, відмінних від aaabb, які були б йому еквівалентні.

Цейтін доводить, що для даного асоціативного вирахування не може бути єдиного алгоритму для розпізнавання еквівалентності будь-якої пари слів.

Можна було привести ще багато,прикладів алгоритмічно нерозв'язних проблем, з ними ми ще зустрінемося при вивченні теорії граматик алгоритмічних мов. До типу алгоритмічних проблем стосується й теорема Геделя про неповноту арифметичної логіки. Насамперед уточнимо основні поняття, використовувані в теоремі Геделя.

Під арифметичною логікою розуміється сукупність аксіом і правил виводу теорем в елементарній теорії чисел (теорії позитивних цілих чисел). Логіка називається повною, якщо в ній можна довести істинність або хибність кожного твердження. Логіка називається несуперечливою, якщо вона вільна від протиріч.

Теорема Геделя (7). Кожна адекватна - несуперечлива арифметична логіка неповна. Теорема стверджує, що будь-яка адекватна несуперечлива арифметична логіка неповна, тобто існує правдиве твердження про цілі числа, яке не можна довести в такій логіці.

Більше того, Гедель показав, що неможливо довести несуперечність арифметичної логіки (навіть неповної) тими методами, які виражаемі в самій цій логіці.

Щоб було зрозуміло значення результатів, отриманих Геделем, згадаємо, що першою аксіоматичною системою була геометрія Евкліда (III в. до н.е.). В основі евклідової геометрії лежить сукупність визначень й аксіом, що відбивають найпростіші геометричні властивості, підтверджені багатовіковим людським досвідом.

У число аксіом, які в геометрії Евкліда приймаються без доказів, входить й аксіома про паралельні лінії. Вона формулювалася Евклідом так: «Якщо дві прямі, що лежать в одній площині, при перетинанні їх якої-небудь третьої утворять внутрішні однобічні кути, сума яких менше двох прямих, то ці прямі перетинаються по ту сторону від третьої прямої, на якій сума зазначених кутів менше двох прямих».

Ця аксіома з багатьох причин бентежила математиків. Вона значно складніше інших аксіом і по затверджуваному нею факту й по своєму формулюванню. Адже навіть для усвідомлення її змісту треба попередньо опанувати рядом відомостей.

Аксіому про паралельні лінії нерідко називали темним пятком у геніальній праці Евкліда. Не була також доведена повнота й несуперечність евклідової геометрії. І дуже рано почалися завзяті спроби математиків звільнити евклидову геометрію від усяких плям.

Із цією метою прагнули довести аксіому про паралельні. Намагалися логічно-вивести її твердження з інших аксіом Евкліда. Такі спроби тривали протягом двох із зайвим тисячоліть. Майже всі видатні математики випробовували свої сили на рішенні цієї проблеми (Декарт, Лейбніц, Гаусе й ін.).

Повну безплідність спроб довести аксіому про паралельні вперше строго науково встановив великий російський математик Н. И. Лобачевський в XVIII столітті. Він довів, що твердження цієї аксіоми не можна вивести з інших аксіом Евкліда.

Лобачевский постулював особливу неевклідову геометрію, названу його ім'ям. Вона відкидала істинність наступної аксіоми Евкліда: «Якщо дані пряма й крапка, що не лежить на ній, то існує тільки одна пряма, що проходить через дану крапку паралельно даній прямій». У геометрії Лобачевського паралельних ліній не існує. Стосовно цієї нової геометрії евклідова геометрія є тільки частковим випадком.

Ріман довів, що неевклідова геометрія Лобачевського несуперечлива, якщо несуперечлива евклідова геометрія, а Гільберт довів, що евклідова геометрія несуперечлива, якщо несуперечлива арифметика, тобто елементарна теорія позитивних цілих чисел.

Для доказу несуперечності шукали арифметичну логіку, що була б повна, тобто таку, у якій можна було б вивести (як теореми) всі правдиві твердження про цілі числа.

Гедель же показав даремність таких пошуків і довів алгоритмічну нерозв'язність проблеми доказу несуперечності арифметичної логіки. Таким чином, у своїй теоремі про неповноту Гедель показав, що існує нескінченне число проблем елементарної теорії чисел, рішення яких неможливо ніяким даним аксіоматичним методом.

Для доказу теореми Геделя можна використати машини Т'юрінга. Для цього введемо наступні визначення.

Множина будемо називати рекурсивно перечислюваною, якщо існує машина Т'юрінга — МТ, що допускає всі ланцюжки цієї множини — і тільки їх. Множина називається рекурсивною, якщо вона і його доповнення рекурсивно перечислювані.

Виявляється, існують рекурсивно перечислювані множини, які не рекурсивні. До числа таких множин належить аксіоматична система звичайної арифметики. Відомо, що множина теорем буде хоча й рекурсивно перечислюваною, але не рекурсивно.

Дійсно, формальна арифметика має наступну властивість: існує механічна процедура f, така, що якщо M_i являє собою яку-небудь МТ із двома виходами, що допускає всі теореми 2, виведені з деякої несуперечливої множини аксіом цієї теорії, і забороняє заперечення всіх цих теорем (2), то f(i) є формула формальної арифметики, що не допускається й не відкидається машиною М_i.

Таким чином, не існує МТ із двома виходами, що допускала б множину 2 і забороняла б його доповнення 2.