Anisov_a_m_sovremennaya_logika - Стор 27
Розглянемо таку МНР-програму π. Початкова конфігурація: x, y, 0, 0, 0 .
L1: S(2) J(1,2,2) J(1,1,1)
Програма π додає по одиниці до y доти, доки він не зрівняється з х. Якщо це станеться (а це станеться колись при х > у), перший регістр обнулюється і туди поміщає-
ся одиниця; інакше (якщо спочатку було х ≤ у) програма ніколи не завершить роботу. Очевидно, π напівдозволяє множину А і, отже, А – напівдозволену множину.
Розглянемо ще одну МНР-програму? Початкова конфігурація: x, y, 0, 0, 0 .
Програма π′ завершує роботу при х ≤ у і потрапляє в нескінченний цикл в іншому випадку (при x> y), напівдозволяючи безліч А*. Отже, А * - напівдозвільне безліч. За теореми, множини А і А * можна розв'язати. Теорема доведена нами без вказівки явного способу побудови програм для цих множин. Однак у даному конкретному випадку легше безпосередньо довести розв'язність множини А і, відповідно, множини А*.
Таким чином, властивості Р та П один одного не виключають. При цьому суттєво, що не всяка напіврозв'язна множина є розв'язною.
Але протилежне вірно: всяке розв'язне безліч одночасно є і напіврозв'язним. Щоб переконатися у сказаному, достатньо розглянути два випадки. По-перше, безліч А може збігатися з універсумом U. Тоді програма, що дозволяє, є разом з тим і напівдозволяючою і нічого більше робити не треба. По-друге, А може не збігтися з U. Тоді для а A програма π завершить роботу з R = 0.
Можливі три способи зупинки: перехід на відсутню наступну команду, перехід до відсутньої мітки та перехід до мітки, за якою немаєкоманди. Необхідно привести програму π до стандартного вигляду. За визначенням це означає, що в ній більше немає переходів до відсутніх міток і міток, за якими немає команди за, можливо, тим винятком, що мітка без команди стоїть у програмі останньої (тобто за нею немає інших інструкцій). Зробити програму стандартною легко: достатньо в тексті програми посилання на неіснуючу мітку або мітку без команди замінити на перехід до мітки без команди, яка стоїть останньою (якщо такої мітки немає, її сліду-
ет ввести). Очевидно, що стандартизована програма π′ буде робити те саме, що й вихідна програма π. Тепер допишемо програму π′ наступним чином (поставивши першу дописану команду за останньою міткою, якщо така є).
π′ (без останньої мітки, якщо така є)
Z(2) (Li остання мітка π′, але Li може бути відсутнім) S(1)
J(1,2,j) (де j – індекс, відсутній у π′) J(1,1,k)(k відсутня у π′ і k≠j)
Зрозуміло, що стандартна програма π′, еквівалентна вихідній програмі π, завершить роботу або тому, що виконано її остання команда, або тому, що відбувся перехід на останню позначку Li. У будь-якому випадку після завершення дозволу-
ної програми π′ буде або R 1 = 1, ëèáî R 1 = 0. Ïðè R 1
після виконання двох перших додаткових команд буде R
та за командою J(1,2,j) програма завершить роботу. Але якщо R 2 = 0,
через R = 1 переходу за командою J(1,2,j) не піде і програм-
ма перейде до виконання команди Lk: J(1,1,k), що призводить до зациклювання. Таким чином, отримана розширена програма є напівдозвільною, що і потрібно.
Згадані та отримані результати дозволяють встановити, що безліч здійсненних (тобто істинних в одному або більшеуніверсумах) висловлювань логіки предикатів першого порядку не можна розв'язати. Для нього, на відміну від безлічі логічно істинних висловлювань, не існує навіть напіврозв'язної процедури перерахування. Доведемо цей найважливіший теоретико-пізнавальний факт. Припустимо, що безліч здійснюваних висловлювань напівдозволене. Його доповненням є безліч суперечливих висловлювань логіки предикатів, яке, як було встановлено, напіввирішальне. За теоремою, безліч суперечливих висловлювань тоді можна розв'язати, що суперечить згадуваному результату про те, що ця множина не є вирішальною. Отже, безліч здійсненних висловлювань першопорядкової логіки предикатів не можна розв'язати.
Сказане вище дозволяє пов'язати всі точно сформульовані питання про наявність властивостей у індивідів з роздільною здатністю, напіврозв'язністю або нерозв'язністю денотатів цих
властивостей. Назвемо проблему Q(х)? розв'язною (напіврозв'язною,
нерозв'язною), якщо денотат властивості Q(х) дозволимо (напіврозріз-
(1) Питання «Чи є формула А теореми обчислення висловлювань P?» є розв'язним. (2) Питання «Є-
Чи ся формула А теореми обчислення предикатів К?» напів-
дозволимо, але не дозволимо. (3) Питання «Чи є формула А істинною в універсумі натуральних чисел?» нерозв'язний.
На запитання (1) за кожною формулою логіки висловлювань можна відповісти або так, або ні. На питання (2) у випадку (тобто у разі довільних формул) можна отримати лише відповідь «так», але відповіді «ні» ми ризикуємо не дочекатися. Нарешті, питанням (3) у випадку немає ні ствердного, ні негативного відповіді. Звичайно, нам відомо багато прикладів конкретних формул, які не є теоремами обчислення предикатів або прикладів формул, істинних уУніверсум N. Але в нас немає і принципово не може бути ефективного обчислювального методу, що дозволяє перерахувати всі формули, що не є теоремами логіки предикатів, або всі справжні формули арифметики.
Таким чином, логіка наклала заборону на ідею автоматичного вирішення навіть точно сформульованих теоретичних проблем. Мрія Г.Лейбніца про той час, коли вчені свої суперечки вирішуватимуть обчисленнями, виявилася нездійсненною. Але тут висновок аж ніяк не лише негативний аспект. Отримані в логіці обмежувальні теореми є суворим обгрунтуванням непереборності творчого початку теоретичної науці.
До цих пір ми розглядали машини, функціонування яких однозначно визначалося крок за кроком виконанням відповідних так само однозначно певних операцій.
рів. Такі машини є детермінованими. Недетермі-
ні машини – це ті ж детерміновані, доповнені пристроєм (іноді його називають оракулом), яке здатне без обчислень правильно вгадувати деякі результати. Наприклад, забезпечимо детерміновану машину оракулом, здатним правильно вгадувати рядок у таблиці істинності, де задана формула логіки висловлювань істинна. Подальші детерміновані обчислення в явному вигляді продемонструють, що це дійсно рядок, що виконує формулу.
Ви можете сказати, що оскільки перевірка формул логіки висловлювань на здійсненність здійснюється алгоритмічно, то за тезою Черча існує відповідна детермінація.
ванна програма, що вирішує те саме завдання. Але вся справа у швидкості обчислень. Детермінованій машині в загальному випадку потрібно перевірити 2 n рядків 11 (де n – кількість змінних у формулі), а на це потрібно багато часу навіть за порівняноневеликі n. Зате недетермінованій машині, з оракулом, достатньо перевірити лише один рядок або відразу видати повідомлення, що потрібних рядків немає. Проте слід погодитися, що у принципі (відволікаючись від ресурсних обмежень) у разі те, що робить недетермінована машина, може і детермінована.
Але ми можемо піти далі, уявивши собі оракул, здатний завжди правильно вгадувати, чи формула теореми першопорядкової логіки предикатів. Так як безліч таких формул лише напіврозв'язно, але не можна розв'язати, замінити оракул детермінованою машиною неможливо в принципі. Цей оракул, так би мовити, «проникливіший» за свого попереднього колеги. І вже зовсім божественним буде виглядати дар оракула, який матиме здатність безпомилково вгадувати приналежність елемента нерозв'язній множині, наприклад, множині здійснених формул першопорядкової логіки.
Таким чином, вибудовується ієрархія недетермінованості, яку можна подати в наступних термінах: слабка, середня та сильна недетермінованість (або, якщо завгодно, слабкі, середні та сильні оракули). Слабка недетермінованість може бути ліквідована детермінованим пристроєм. Але вже середня недетермінованість не допускає такої редукції до детермінізму. Ще більш потужною є сильна недетермінованість, яка не по зубах навіть оракулам із середньої зони.
Може виникнути питання, навіщо недетермінованій машині потрібна детермінована частина поряд з оракулом, якщо відомо, що він видає правильну відповідь? Справа в тому, що в ряді випадків нас цікавить не лише відповідь на запитання, а й саме вирішення завдання. Уявімо, що ми маємо оракул середньої сили, який за пред'явленою формулою обчислення предикатівпершого порядку видає відповідь, чи буде вона теоремою, чи не буде. Якщо відповідь «ні», то вона вичерпна. Якщо ж так, то було б цікаво поглянути на доказ. У цьому випадку запускається детермінована частина машини з програмою, яка напівдозволяє безліч ло-
гічно істинних формул логіки предикатів, здійснюючи побудову відповідних доказів. Маючи позитивну відповідь оракула, ми рано чи пізно отримаємо доказ – адже тепер ми точно знаємо, що наша формула є теоремою. Без оракула цього знання ми не маємо, тому буде існувати небезпека або чекати нескінченно довго (що неможливо), або вимкнути машину, залишаючись у сумнівах з приводу того, чи не зроблено це передчасно.
Можна навести й інші приклади, коли неконструктивні пророцтва оракула бажано підтвердити конструктивно, явно пред'явивши необхідний доказ чи побудова. Лише у разі сильно недетермінованих машин їхня детермінована частина може виявитися непотрібною в ситуації, коли шукана множина нерозв'язна. Що, наприклад, ми могли б вимагати від детермінованої машини, якщо оракул відповів, що деяка формула логіки предикатів можна здійснити, але не є загальнозначущою – явно пред'явити модель? А якщо ця формула виконується лише у нескінченних областях? Якщо так, то нерозумно сподіватися отримати явну побудову моделі, оскільки все, що може бути конструктивно побудовано, має бути кінцевим. Проте безглуздо забороняти сильно недетермінованим машинам вміти вирішувати завдання, доступні оракулам меншої сили або детермінованим пристроям. Тому й у них має бути детермінована частина.
Збентежливий факт полягає в тому, що на жодному заводі з виробництва комп'ютерів ні зараз, ні внайближчому майбутньому не видно і нам на можливість створення навіть оракула слабкого типу, не кажучи вже про двох, що залишилися. Це виводить нас на проблеми, які й досі погано усвідомлюються. Справді, є підстави вважати, що недетерміновані об'єкти в нашому Всесвіті все ж таки є.