Anisov_a_m_sovremennaya_logika - Страница 27
Помислете за следната програма MHP π. Първоначална конфигурация: x, y, 0, 0, 0 .
L1: S (2) J (1,2,2) J (1,1,1)
Програмата π добавя едно към y, докато не се изравни с x. Ако това се случи (и ще стане по някое време, когато x> y), първият регистър се нулира и се поставя там-
Xia единица; в противен случай (ако първоначално е имало x ≤ y) програмата никога няма да излезе. Очевидно е, че π е полуразтворимо множество A и следователно A е полуразрешимо множество.
Помислете за друга програма MHP π ′. Първоначална конфигурация: x, y, 0, 0, 0 .
Програмата π ′ завършва за x ≤ y и навлиза в безкраен цикъл в противен случай (за x> y), като полуразрешава множеството A *. Следователно A * е полуразрешим набор. По теорема множествата A и A * са разрешими. Доказахме теоремата, без да посочваме изричен метод за конструиране на разрешаващи програми за тези множества. В този конкретен случай обаче е по-лесно директно да се докаже разрешимостта на множеството A и съответно на множеството A *.
По този начин свойствата на P и P не се изключват взаимно. Освен това е от съществено значение не всеки комплект за полуразрешаване да бъде разрешим.
Но е точно обратното: всеки разрешим набор е едновременно полуразрешим. За да се убедим в казаното, е достатъчно да разгледаме два случая. Първо, множеството A може да съвпада с вселената U. Тогава програмата за разрешаване е в същото време полуразрешаваща и нищо друго не трябва да се прави. Второ, A може да не съвпада с 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) няма да последва и програмата-
ma ще премине към изпълнението на командата Lk: J (1,1, k), която води до цикъл. По този начин получената разширена програма е полуразрешаваща, което е необходимо.
Споменатите и получени резултати дават възможност да се установи, че множеството от изпълними (т.е. верни в една или повече вселени) изрази на предикатната логика от първи ред е неразрешимо. За него, за разлика от множеството логически верни твърдения, няма дори процедура за изброяване, полуразрешима. Нека докажем този най-важен познавателен факт. Да предположим, че наборът от изпълними изявления е полуразрешим. Неговото допълнение е набор от противоречиви твърдения на предикатната логика, за които е установено, че са полуразрешими. По теорема множеството противоречиви твърдения тогава може да се реши, което противоречи на споменатия резултат, че това множество не може да се реши. Така че, множеството удовлетворими изрази на предикативната логика от първи ред е неразрешимо.
Горното ни позволява да свържем всички точно формулирани въпроси относно наличието на свойства у индивидите с разрешимостта, полуразрешимостта или неразрешимостта на обозначенията от тях
Имоти. Нека наречем проблема Q (x)? разтворим (полуразтворим,