АЛГОРИТМІЧНІ НЕДОЗВІЛЬНІ ПРОБЛЕМИ - Логіка - доступно для всіх
АЛГОРИТМІЧНІ НЕДОЗВІЛЬНІ ПРОБЛЕМИ
Однією з властивостей алгоритму є його масовість. Це означає, що алгоритм являє собою спосіб вирішення деякої масової проблеми, що формулюється у вигляді проблеми відображення не одного, а цілої множини вхідних слів у відповідні вихідні слова. Отже, будь-який алгоритм можна як деяке універсальне засіб на вирішення цілого класу завдань.
Виявляється, що є такі класи завдань, на вирішення яких немає і може бути єдиного універсального прийому. Проблеми вирішення такого роду завдань називають алгоритмічно нерозв'язними проблемами. Однак алгоритмічна нерозв'язність проблеми вирішення завдань того чи іншого класу зовсім не означає неможливість розв'язання будь-якої конкретної задачі цього класу. Йдеться про неможливість вирішення всіх завдань даного класу одним і тим самим прийомом.
Таким чином, завдання (проблеми) можна розділити на алгоритмічно розв'язні та алгоритмічно нерозв'язні. Прикладом алгоритмічно вирішуваної проблеми є проблема доказу тотожностей у звичайній алгебрі. Існує єдиний конструктивний прийом (розкриття дужок, приведення подібних членів), що дозволяє за кінець кількох кроків вирішити, чи є будь-яке задане співвідношення тотожним.
Перехід від інтуїтивного поняття алгоритму до точного поняття рекурсивної функції (машини Тьюринга, нормального алгоритму) дозволив довести алгоритмічну нерозв'язність низки проблем.
Одним із перших результатів такого типу є доказ нерозв'язності проблеми розпізнавання виведення в математичній логіці, виконаної Черчем у 1936 р. Результат цього доказу формулюється яктеорема Черча (5). Проблема розпізнавання виведення алгоритмічно нерозв'язна.
Тим самим не лише з'ясовується причина безуспішності всіх попередніх спроб створення відповідного алгоритму, а й виявляється повна безглуздість таких спроб. . Доказ цієї теореми Черча розглядати не будемо через його складність. Зазначимо лише, що суть його зводиться до доказу нерекурсивності функції, що вирішує це завдання.
Як приклад доказу алгоритмічної нерозв'язності розглянемо проблему розпізнавання самозастосовності. Існують як самозастосовні, так і незастосовні алгоритми. Прикладом самозастосовного алгоритму є так званий тотожний алгоритм у будь-якому алфавіті А, що містить дві або більше двох літер. Цей алгоритм застосовується до будь-якого слова р в алфавіті А і переробляє будь-яке вхідне слово у собі.
Прикладом непридатного алгоритму є так званий нульовий алгоритм у будь-якому кінцевому алфавіті В. Цей алгоритм задається схемою, що містить єдину підстановку ® у (де у будь-яка літера алфавіту В). За своїм визначенням він не застосовується до жодного вхідного слова, а значить, і до свого зображення.
Проблема розпізнавання самозастосовності алгоритмів полягає в тому, щоб знайти єдиний конструктивний прийом, що дозволяє за кінцеве число кроків за схемою будь-якого алгоритму дізнатися, є алгоритм самозастосовним або неприйнятним.
Доказ алгоритмічної нерозв'язності цієї проблеми проводитимемо, використовуючи алгоритмічні системи Тьюринга. Для цього сформулюємо проблему самозастосовності в термінах машини Тьюринга. Нехай у машині Тьюринга зафіксована якась конфігурація. Можливі два випадки:
1) машина застосовна до цієї конфігурації, тобто після кінцевогочисла тактів вона зупиняється у заключній конфігурації;
2) машина не застосовується до цієї конфігурації. Це означає, що машина ніколи не переходить у заключну конфігурацію, вона впадає у безкінечний процес.
Припустимо тепер, що у стрічці машини Тьюринга зображено її власний шифр (т. е. шифр таблиці відповідності та вихідної конфігурації), записаний в алфавіті машини. Якщо машина застосовна до такої конфігурації, то будемо називати її самозастосовною, інакше - нездатною.
Тоді проблема розпізнавання самозастосовності полягає в наступному: за будь-яким заданим шифром встановити, до якого класу належить машина, зашифрована ним, — до класу самозастосовних чи незастосовних?
Виявляється, можна довести таку теорему (6). Проблема розпізнавання самозастосовності алгоритмічно нерозв'язна.
Доведення. Припустимо, що така машина М існує. Тоді в М всякий самозастосовний шифр переробляється в якийсь символ v (має сенс ствердної відповіді на поставлене питання про самозастосовність), а всякий непридатний шифр - символ т (має сенс негативної відповіді на поставлене питання).
У такому разі можна було б побудувати і таку машину М1, яка, як і раніше, переробляє несамозастосовні шифри в t, тоді як до самозастосовних шифрів М1 вже не застосовується. Цього можна досягти шляхом такої зміни схеми машини (таблиці відповідності) M, щоб після появи символу замість зупинки машина стала б необмежено повторювати цей же символ.
Отже, М1 застосовна до будь-якого непридатного шифру (виробляючи у своїй символ t ) і застосовна до самозастосовним шифрам. Однак це призводить до суперечності.
1) нехай машина М1 самозастосовна, тодівона застосовна до свого шифру M1' і переробляє їх у символ t , але поява цього символу таки має означати, що машина непридатна;
2) нехай M1 не застосовується, тоді вона застосовна до M1 ', що повинно означати, що М1 самозастосовна.
Отримане протиріччя доводить теорему, т. е. наше припущення про машину М невірно.
Оскільки різних слів у будь-якому обчисленні може бути безліч, то фактично тут є нескінченна серія однотипних завдань. Потрібно знайти алгоритм, що розпізнає еквівалентність чи нееквівалентність будь-якої пари слів.
Проблема еквівалентності слів для асоціативних обчислень було сформульовано ще 1914 р. норвезьким математиком Туе. Їм був запропонований алгоритм для розпізнавання еквівалентності слів у деяких асоціативних обчисленнях спеціального виду. З того часу робилися багато спроб побудувати такий загальний алгоритм, який для будь-якого асоціативного обчислення
і для будь-якої пари слів у ньому дозволив встановити, еквівалентні ці слова чи ні.
У 1946 та 1947 рр. А. А. Марков та Е. Пост, незалежно один від одного, побудували конкретні приклади асоціативних обчислень, для кожного з яких проблема еквівалентності слів алгоритмічно нерозв'язна. Тим більше немає алгоритму для розпізнавання еквівалентності слів у будь-якому асоціативному обчисленні.
У 1955 р. радянський математик П. С. Новіков довів алгоритмічну нерозв'язність проблеми розпізнавання слів для асоціативних обчислень спеціального виду званих теорією груп.