Теорія алгоритмів та математична логіка:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Державний іспит

Зміст

1 Формальні мови. Числення предикатів, як формальна мова.
2 Формальні теорії. Числення предикатів, як формальна теорія.
3 Теорії першого порядку. Теорема К. Гьоделя про повноту числення предикатів.
4 Алгоритмічна мова К. Гьоделя. Примітивно рекурсивні, загально-рекурсивні та частково-рекурсивні функції, множини, предикати. Теза Черча.
5 Поняття універсальної функції для класу рекурсивних функцій. Довести, що універсальна функція для класу примітивно-рекурсивних функцій однієї змінної не є примітивно-рекурсивною.
6 Машина Тьюринга. Теза Черча. Еквівалентність концепцій алгоритму за Гьоделем та Тюрингом.
7 Алгоритмічно-нерозв’язні проблеми. Проблема застосовності для машин Тьюринга або визначенності чвсткової функції в точці. Класичні алгоритмічно-нерозв’язні проблеми.
8 Рекурсивні та рекурсивно зліченні множини (предикати). Властивості таких множин.

Формальні мови. Числення предикатів, як формальна мова.

Формальна мова складається з таких елементів:

1) Алфавіт $A$ - довільна скінченна або зліченна множина, яка розбивається на дві підмножини

A

= $A_{0} \cup A_{S}$ , де елементи множини

A 0

називають термінальними (основними) символами, а елементи множини

A S

службовими символами;

2)У множині А* всіх слів в алфавіті А , яка є зліченною, виділяється підмножина $W \subseteq A$ , яка називається підмножиною слів (речень, формул) формальної мови, крім того, якщо F $\in$ W, тобто є правильно побудованим реченням (формулою), то і його заперечення ¬F є також правильно побудованим. Сукупність правил, які визначають W, називають синтаксисом формальної мови.

Інтерпретатором формальної мови на множині Т називають функцію І : W $\rightarrow$ Т, таку, що для довільної формули має місце I(F) $\neq$ I(¬F), а сукупність правил, які її визначають, називають семантикою формальної мови

Висловлювальна форма - це твердження, в якому пропущені певні слова; після заповнення порожніх місць назвами елементів з певної множини D висловлювальна форма стає висловлюванням. Кількість змінних від яких залежить висловлювальна форма називається її арністю. Визначити дію інтерпретатора І_с на висловлювальній формі А(х₁,х₂,...,х_n) означає описати інтерпретацію всіх висловлювань, які вона задає.

Тобто слід співставити кожному набору d₁,d₂,...,d_n, d_i $\in$ D, елемент I(A) d₁,d₂,...,d_n $\in$ {0,1}.

Отже, результатом дії інтерпретатора І_с на висловлювальну форму А є предикат І_с(А) – функцiя яка приймає значення в області істинності {0,1}.

Функція, яка ставить у відповідність кожному набору d₁,d₂,...,d_n, d_i $\in$ D елемент з множини {0,1} називається n-містним (n- арним) предикатом визначеним на множині D.

Таким чином, щоб проінтерпретувати висловлювальну форму А(х₁,х₂,...,х_n) як предикат треба обрати область інтерпретації - множину D і співставити цій формі предикат І_с(А) відповідної арності, визначений на цій множині.

Операції над висловлювальними формами (предикатами):

операції над висловлюваннями( $\land, \lor, \lnot, \rightarrow, \leftrightarrow$ )
квантування( $\forall, \exists$ ).

Синтаксис. Формальна мова має алфавіт А, який включає в себе множину термінальних сим¬волів А₀, яка складається з елементів: a, b, с ... - прості висловлювання, f, g, h ... - функціональні константи, А, В, С ... - предикатні константи, х, у, z, ... – змінні,

та множини спеціальних символів:

А_S={ $\land, \lor, \lnot, \rightarrow, \leftrightarrow, (,), \forall, \exists$ }

Введемо поняття терму або функціональної форми індуктивно:

База: а, b, с, х, у, z - найпростіші терми;

Індукційний крок: якщо t1,t2,..,tk - терми, а f - функціональна константа, то f(t1,t2,...,tk) - теж терм.

Поняття формули числення предикатів вводиться також індуктивно. Нехай t1,t2,...- довільні терми, А - деяка предикатна константа.Тоді формула A(t1,t2,...) називається атомарною.

База: Атомарні формули - формули числення предикатів.

Індукційний крок: F₁,F₂- формули числення предикатів, тоді:

F₁ $\land$ F₂, F₁ $\lor$ F₂,F₁ $\rightarrow$ F₂, ¬(F₁), $\forall x$ (F₁), $\exists x$ (F₁) - теж формули

Семантика. Інтерпретатором формули числення предикатів називається трійка {D,I_C,I_V), яка складається з множини D - області інтерпретації, та двох інтерпретаторів (відображень) I_C – інтерпретатор констант, I_V – інтерпретатор змінних.

Областю значень відображення I_C є множина Т предикатів, а областю значень композиції І = I_V(I_C) є область істинності Т₀ = {0,1}. Для даного набору формул, які підлягають інтерпретації, відображення I_C та I_V однозначно визначені, якщо:

1) кожному простому висловлюванню (константі) з даного набору формул співставлено її значення істинності або 1, або 0 a $\mapsto$ I_C(a) $\in$ {0,1}

2) кожній функціональній константі з даного набору формул співставлено функцію від певної кількості змінних, яка визначена на множині D і набуває значень в цій же множині f $\mapsto$ I_C(f):D $\times ... \times$ D $\rightarrow$ D

3)кожній предикатній константі А з даного набору формул співствлено предикат певної арності A $\mapsto$ I_C(A):D $\times ... \times$ D $\rightarrow$ {0,1}

4) інтерпретатор змінних присвоює кожній вільній змінній формули певне значення I_V(x):x $\mapsto$ d_x $\in$ D

Формальні теорії. Числення предикатів, як формальна теорія.

Формальною теорією називається формальна мова (A,W), в якій виділена певна підсукупність (пгдмножина) слів Axioms $\in$ W, елементи якої називаються аксіомами, і сформульовані правила виводу одних формул або слів з інших.

При цьому запис F₁, F₂, ..., F_k $\vdash$ F означає: формула отримана з шляхом застосування правил виводу формальної теорії.

Якщо формули F₁, F₂, ..., F_k $\in$ Axioms, то формула називається теоремою формальної теорії.

Послідовність формул U₁, U₂, ..., U_S називається формальним виводом формули F множини формул Г={F₁, F₂, ..., F_k} якщо:

1) кожна формула U_i або U_i $\in$ Axioms, або U_i $\in$ Г , або U_i $\in$ Axioms $\cup$ Г $\cup$ { $U 1,..., U i - 1$ }

2) $U S$ = F

Якщо F є теоремою теорії, то відповідний вивід будемо називати доведенням теореми. Формальна теорія називається несуперечливою, якщо не існує формули F такої, що F та ¬F є теоремами. Моделлю формальної теорії називається модель множини її теорем, тобто така інтерпретація І множини її формул, що $\vdash$ F \Rightarrow I(F) = 1

Лема. Якщо формальна теорія допускає принаймні одну модель, то вона несуперечлива.

Числення висловлювань як формальна теорія

Приймається синтаксис числення висловлювань, як формальної мови, де формули Зображення:TAML 1.GIF приймаються за означення зв’язок $\land, \lor, \leftrightarrow$

Аксіоми числення предикатів:

A1: $F \rightarrow (G \rightarrow F)$

A2: $(F \rightarrow (G \rightarrow H)) \rightarrow ((F \rightarrow G)\rightarrow(F \rightarrow H))$

A3: $(\lnot G \rightarrow \lnot F) \rightarrow ((\lnot G \rightarrow F) \rightarrow G)$

A4: $\forall x F(x) \rightarrow F(t)$ , де t - терм вільний для х у формулі F(x);

A5: $\forall x (F \rightarrow G) \rightarrow (F \rightarrow \forall x G)$

Правилами виводу в численні предикатів є modus ponens F, F $\rightarrow$ G $\vdash$ і правило узагальнення Gen $F(x) \vdash \forall x F(t)$ , де t - терм вільний для х у формулі $F (x)$

Будь-яка теорема числення предикатів, як формальної теорії є тотожно-істинною формулою числення предикатів, як формальної мови, тобто $\vdash F \Rightarrow \vDash F$

Наслідок. Будь-яке числення предикатів є несуперечливою теорію.

Метатеорема дедукції в численні предикатів. Нехай Г- деяка множина формул числення висловлювань і А деяка формула. Нехай Г, А├F (формула F виводиться з множини формул Г і формули А), і при цьому не застосовується правило Gen по вільним змінним формули А, тоді Г├ А→F.

Доведення. Доведення теореми проведемо методом математичної індукції по довжині виводу формули F.

Нехай U₁, U₂, ..., U_S $\vdash$ F- вивід формули F з множини формул Г,A.

База індукції: s = 1. У цьому випадку U₁ $\vdash$ F і це можливо лише за одної з трьох умов:

а) F $\in$ Г;

б) F- аксіома;

в) F $\vdash$ А.

У випадку а) маємо: 1)F(гіпотеза);2)F->(A->F)(A1,де A=G);3)A->F(MP 1,2).

У випадку б) доведення дослівно повторюється, а у випадку в) попередньо доведена теорема F->F. Цим базу індукції доведено.

Припустимо, що метатеорема дедукції має місце для формул F, довжина виводу яких з множини формул Г, А менша за s.

Тоді, за припущенням індукції, для довільного к : 1 < к < s, має місце: Г $\vdash$ А->U_k, а для формули U_S є такі можливості:

а) F $\in$ Г
б)F- аксіома
в)F = А
г)існують i,j : 1 < i,j < s такі, що U_j= U_i ->U_s, тобто U_s отримана за правилом modus ponens;
д)F= $\forall x U_{i}(x)$ і отримано застосуванням правила Gen.

У перших трьох випадках міркування, проведені при доведенні бази індукції, дослівно повторюються. У випадку г), користуючись припущенням індукції, отримуємо Г $\vdash$ А->U_i, Г $\vdash$ А->(U_i->U_S). За схемою аксіом А2, отримуємо (A->(U_i->U_S))->((A->U_i)->(A->U_S)

Застосувавши два рази modus ponens отримуємо Г $\vdash$ А-> U_S, а U_S=F.

У випадку д) за припущенням індукції маємо Г $\vdash$ А->U_i.

За зробленим припущенням х не є вільною змінною формули А. Тоді за А5 $\forall x(A \rightarrow U_{i}) \rightarrow (A \rightarrow \forall x U_{i}(x)$ .

Оскільки Г $\vdash$ A-> U_i , то за правилом Gen: Г $\vdash$ $\forall$ x (A-> U_i) Звідки застосувавши М.Р. маємо потрібний результат.

Теорії першого порядку. Теорема К. Гьоделя про повноту числення предикатів.

Формальна теорія Т, список аксіом якої містить в собі аксіоми А1,А2,АЗ,А4,А5 і правилом виводу якої є modus ponens і правило узагальнення називається теорією 1-го порядку; аксіоми цієї теорії відмінні від А1, А2, A3, А4, A5 називаються спеціальними аксіомами теорії.

Лема. У суперечливій теорії будь-яка формула є теоремою.

Лема 2.5. Якщо тотожно-істинна формула числення предикатгв отримана шляхом підстановки у тавтологію числення висловлювань формул числення предикатів, то вона є теоремою числення предикатів.

Теорія Т1 називається розширенням теорії Т, якщо множина формул теорії Т1 містить множину формул теорії Т і кожна аксіома теорії Т входить в список аксіом теорії. Умовно це буде записуватися Т $\subset$ Т1.

Лема. Якщо замкнена формула $\lnot$ F не є теоремою в теорії Т, то її розширення, яке отримано додаванням формули F до списку аксіом теорії Т є несуперечливим.

Теорія Т називається повною, якщо для будь-якої замкненої формули Т або вона або її заперечення є теоремою, тобто або $\vdash$ x F або $\vdash$ x $\lnot$ F.

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

Теорема. Будь-яка несуперечлива теорія 1-го порядку має зліченну модель

Теорема. В довільній теорії першого порядку Т будь-яка тотожно-істинна формула є теоремою цієї теорії.

Теорема Гьоделя про повноту числення предикатів. Для довільної формули F будь-якого числення предикатів має місце $\vDash F \Leftrightarrow \vdash F$

Алгоритмічна мова К. Гьоделя. Примітивно рекурсивні, загально-рекурсивні та частково-рекурсивні функції, множини, предикати. Теза Черча.

Нехай N+ - множина натуральних чисел з нулем. Визначимо деякий клас функцій f= f(x₁,x₂,...,x_k) : N+^(k)=N+ $\times ... \times$ N+ $\mapsto$ N+, k=0,1,2,..., індуктивно.

1. Базові функції:

1А. Z(x) = 0 для всіх х $\in$ N+

1B. N(x) = х+1 -функція, що видає наступний номер(next)

1С. I_n^k(x₁,x₂,...,x_k,...,x_n,)= х_к –проектори, які з кортежів змінних "вирізають"певну координату, n = 1, 2, 3,... , k = 1, 2,... , n

2. Правила побудови нових функцій

2А. Оператор підстановки (суперпозиції) дозволяє з даних n + 1 функцій - g(y₁, y₂, ..., y_m), h_i(x₁, x₂, ..., x_n), i=1, ..., m утворювати нову функцію f(x₁, x₂, ..., x_n)=g(h₁(x₁, x₂, ..., x_n), h₂(x₁, x₂, ..., x_n), h_m(x₁, x₂, ..., x_n))

2Б. Оператор примітивної рекурсії дозволяє з функцій g(x₁, x₂, ..., x_n) та h(x₁, x₂, ..., x_n, x_n+1, x_n+2) будувати функції від n + 1 змінних, які визначаються таким чином

f(x₁, x₂, ..., x_n,0)=g(x₁, x₂, ..., x_n)

f(x₁, x₂, ..., x_n, y+1)=h(x₁, x₂, ..., x_n, y, f(x₁, x₂, ..., x_n,y))

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

Введемо в розгляд ще один оператор для утворення нових функцiй.

2С. Обмежений оператор мiнiмiзацiї або µ- оператор.

Нехай f(x₁,x₂,..., x_n,y)- деяка частково-визначена функцiя вiд n + 1- ї змiнної i x*₁,x*₂,..., x*_n деякий набiр значень змiнних x₁,x₂, ...,x_n.

Можливi такi випадки:

1)f(x*₁, x*₂, ..., x*_n,y) не приймає значення 0 ні при яких значеннях y

2)f(x*₁, x*₂, ..., x*_n,y) приймаэ значення 0 і y* є мінімальним значенням, при якому )f(x*₁, x*₂, ..., x*_n,y)=0, але існують значення y: y<y*, такі, що значенням, при якому )f(x*₁, x*₂, ..., x*_n,y*)=0, то для всіх y: y<y*, значення f(x*₁, x*₂, ..., x*_n,y) э визначеним відмінним від нуля числом.

Оператор мінімізації дiє наступним чином. Отримавши частково-визначену функцiю f(x₁, x₂, ..., x_n, y), він повертає частково-визначену функцію.

Базові функції є частково-рекурсивними; функції, які отримані застосуванням операторів підстановки, примітивноїре-курсії або мінімізації до частково-рекурсивних функцій є частково-рекурсивними. Частково-рекурсивна функція, яка визначена для всіх значень змінних називається загально-рекурсивною. Згідно концепції К. Гьоделя алгоритм це програма обчислення значень деякої частково-рекурсивної функції.

Теза Чорча. Клас алгоритмічно (механічно) обчислювальних функцій збігається з класом частково-рекурсивних функцій.

Якщо частково-визначена на множині Nⁿ функція А(х₁ ...,х_n) є примітивно-рекурсивною (загально-рекурсивною, частково-рекурсивною) і приймає лише значення 0 та 1, то , А(х₁ ...,х_n) називається примітивно-рекурсивним (загально-рекурсивним, частково-рекурсивним) предикатом. n- арне відношення R визначене на множині N+ називається примітивно-рекурсивним (загально-рекурсивним), якщо таким є його характеристичний предикат.

Лема. Нехай f(x₁,x₂,... ,х_n)- примітивно-рекурсивна (загально-рекурсивна, частково-рекурсивна) функція, тоді множина розв’язків рівняння f(x₁,x₂,... ,х_n) = 0 є примітивно-рекурсивною (загально-рекурсивною, частково-рекурсивною) множиною.

Лема. Графік примітивно-рекурсивної (загально-рекурсивної, частково-рекурсивною) функції є примітивно-рекурсивної (загально-рекурсивної, частково-рекурсивною) множиною.

Лема. Якщо А(x₁,x₂,... ,х_m) таВ(x₁,x₂,... ,х_n)- примітивно-рекурсивні (загально-рекурсивні) предикати, то такими є $\lnot$ А, A $\land$ В, А $\lor$ В; якщо R₁, R₂ $\subseteq$ N^k примітивно-рекурсивні (загально-рекурсивні) відношення, то такими є R₁ $\cup$ R₂, R₁ $\cap$ R₂.

Введемо операції обмеженого квантування предикатів

А: В1(у, х2, ...,хn) = $\forall$ х(х < у)А(х,х2, ...,хn), В2(у, х2, ...,хn) = $\exists$ х(х < у)А(х,х2, ...,хn), при цьому В1(у,х2, ...,хn) = 1 тоді і лише тоді коли для будь-якого z* : z* < у має місце A(z,x2,...,xn) = 1, а В2(у,х2,...,хn) = 1 тоді і лише тоді коли знайдеться z* : z* < у таке, що A(z : *, х2,... , хn) = 1.

Лема. Якщо А примітивно-рекурсивний (рекурсивний) предикат, то примітивно-рекурсивними (загально-рекурсивнимиб частково-рекурсивними) є також і предикати B1(y, x2, . . . , xn), В2(у, х2,...,хn).

Теорема Робінсона. Всі примітивно-рекурсивні функції від однієї змінної можуть бути отримані з функцій N(x),q(x)=х-[ $\sqrt{x}$ ] застосуванням скінченної кількості операцій додавання +, суперпозицій * і оператора примітивної рекурсії J(ітерування функцій) g(х) -> J[g](x), дія якого визначається наступним чином J[g](0)=0, J[g](n+1)=g(J[g](n)) , де g - примітивно рекурсивна функція.

Множина R $\subset$ N називається рекурсивно зліченною, якщо існує така примітивно рекурсивна функція f= f(x,у), така, що рівняння f(a,x) = 0 (а -параметр, х - невідоме) має розв’язок тоді і лише тоді, коли a $\in$ R.

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

Теорема. Об’єднання i перетин скінченного числа рекурсивно зліченних множин є рекурсивно зліченною множиною.

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

Нехай К - деякий клас функцій (наприклад клас примітивно-рекурсивних функцій). Частково визначена функція U(y,x₁,x₂,... ,x_k) називається універсальною функцією для класу К , якщо:

1) $\forall$ a $\in$ N+ U(a,x₁x₂,...,x_k) $\in$ К

2)для довільної функції f $\in$ K існує a $\in$ N+: U(a,x₁x₂,...,x_k)=f(x₁x₂,...,x_k).

При цьому, число n називають номером функції f(x₁x₂,...,x_k). В якості прикладу, побудуємо універсальну функцію для класу примітивно рекурсивних функцій від однієї змінної. Для спрощення побудови скористаємося теоремою Робінсона.

Згідно цієї теореми довільна примітивно рекурсивна функція є значенням певного терму (функціональної форми), складеного з символів N, q і функціональних символів + , *, J. Визначимо нумерацію v термів індуктивно: v(N) = 1, v(q)=3, v(t₁+t₂)=2*3^v(t₁)*5^v(t₂), v(t₁*t₂)=4*3^v(t₁)*5^v(t₂), v(Jt)=8*3^v(t₁). Визначимо нову функцію U(n,x)=f_n(x), де f_n - примітивно-рекурсивна функція, яку обчислює програма, що має номер n, тобто v(f_n(x))=n. Оскільки, не всі натуральні числа є номерами термів, то ця функція є частково визначеною. З означення випливає, що

Доозначимо функцію U поклавши: U(n,x) = Z(x). для всіх n, які мають дільники відмінні від 2, 3, 5, а також діляться на 40. Для зручності введемо в розгляд предикат δ(х), який приймає значення 1 саме для таких n. Тоді маємо таке рекурентне означення

де ex_i(n) - функція, яка повертає степінь, з яким просте число з номером _i входить в розклад числа n. Для того щоб за цими формулами можна було вираховувати значення функції U для довільних n та x,треба її визначити в точках (n, 0), n > 0 і в точках (0,x). Покладемо

Теорема. Універсальна функція класу примітивно рекурсивних функцій від однієї змінної не є примітивно рекурсивною.

Доведення.

Доведення проведемо від супротивного. Припустимо, що U(y,x)- універсальна функція вказаного класу і вона сама є примітивно рекурсивною функцією. Тоді функція від однієї змінної g(x)=U(x,x)+1 також буде примітивно рекурсивною. За означенням універсальної функції п. 2) існує а* $\in$ N+: U(a*,x)=g(x)=U(x,x)+1.Покладемо в отриманій рівності х=а* і прийдемо до суперечності U(a*,a*)= U(a*,a*)+1

Машина Тьюринга. Теза Черча. Еквівалентність концепцій алгоритму за Гьоделем та Тюрингом.

Машина Тьюринга складається з плівки, рухливого читаючо-записуючого приладу, програми, яка складається з програм виду

q_ia_j $\rightarrow$ q_ka_lS.

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

Теза Чорча. Клас алгоритмічно (механічно) обчислювальних функцій збігається з класом частково-рекурсивних функцій.

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

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

Схема доведення в інший бік наступна. Визначимо кодування програм наступним чином:

код(δ)=0, код(L)=1, код(R)=2, код(q_ia_j $\rightarrow$ q_ka_lS)=(i,j,k,l,код(S)).

Тоді код програми, яка складається з команд с₁,...,с_s визначимо як натуральне число (код(с₁), ..., код(c_s)).

Назвемо кодом конфігурації машини Тьюринга, яка описується словом a_i₁, ..., q_ja_{i_p}, ..., a_{i_r} число (i₁, ..., i_p, ... , i_r, j, p).

Послідовність конфігурацій ω₀, ω₁, ..., ω_u, в яких послідовно знаходиться машина М, ω₀ $\Rightarrow$ M, ω₁ $\Rightarrow$ M, ... $\Rightarrow$ M, ω_u назвемо обчисленням, якщо в останній конфігурації міститься команда зупинки. Кодом обчислення ω₀, ω₁, ..., ω_u назвемо число ( код(ω₀), код(ω₁), ..., код(ω_u)).

Далі треба довести, що відношення T'_k(e,x₁, ..., x_k, y) $\rightleftharpoons$ y - код обчислення на машині Тьюринга програми, номер якої дорівнює е, початку з конфігурації 0q₁1^x₁0...01^x_k+10 рекурсивне і існує загальнорекурсивна функція U1(y), яка по будь-якому коду y обчислення, яке закінчується конфігурацією виду 0q₀1^z+10 β видає результат цього обчислення. Тепер залшається відмітити, що б-якій обчислювальній на машині Тьюринга функції f:N^k $\rightarrow$ N справджується нерівність f(x₁, ..., x_k) $\simeq$ U₁(μ y T'_k (e, x₁, ..., x_k, y))

Алгоритмічно-нерозв’язні проблеми. Проблема застосовності для машин Тьюринга або визначенності чвсткової функції в точці. Класичні алгоритмічно-нерозв’язні проблеми.

Якщо теза Чорча є справедливою, ми повинні визнати наступне.

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

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

Припустимо, що такий алгоритм існує. Якщо W(n,x)- універсальна частково-рекурсивна функція класу частково-рекурсивних функцій від однієї змінної, то згідно концепції К. Гьоделя, має існувати частково-рекурсивний предикат А такий, що

(1).

Побудуємо частково-рекурсивну функцію B(x)=μ[A(x,x)+t=0] (2).

З означення випливає, що В(х) є визначеним в точці х і приймає значення 0 тоді і тільки тоді, коли А(х,х)=0, для всіх інших х значення В(х) не визначено. Отже

Оскільки В(х) є частково-рекурсивною функцією, то існує номер n* N: W(n*,x) = B(x)(3).

Чи визначено значення функції В(х) в точці n*? Якщо так, то цим значенням може бути лише 0, а тоді 0 = В(n*) = W(n*,n*), звідки, згідно (2), А(n*,n*) = 0, а за означенням (1) предиката А, маємо що значення W в точці (n*,n*) не є визначеним. Але тоді (див. (3)) і значення функції В в точці n* також є невизначеним.

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

Деякі інші класичні алгоритмічно-нерозвязні проблеми: визначення по формулі числення предикатів чи є вона тотожно-істинною; на вхід подається поліном

a(x,y) $\in$ Z[x,y] , чи існує алгоритм, який би по коефіціентам поліном визначав би чи є у нього цілі корені(10-та проблема Гільберта).

Рекурсивні та рекурсивно зліченні множини (предикати). Властивості таких множин.

Теорія алгоритмів та математична логіка:Іспит

Матеріал з USIC Wiki

Зміст

Формальні мови. Числення предикатів, як формальна мова.

Формальні теорії. Числення предикатів, як формальна теорія.

Теорії першого порядку. Теорема К. Гьоделя про повноту числення предикатів.

Алгоритмічна мова К. Гьоделя. Примітивно рекурсивні, загально-рекурсивні та частково-рекурсивні функції, множини, предикати. Теза Черча.

Машина Тьюринга. Теза Черча. Еквівалентність концепцій алгоритму за Гьоделем та Тюрингом.

Рекурсивні та рекурсивно зліченні множини (предикати). Властивості таких множин.

Перегляди

Особисті інструменти

Навігація

Пошук

Інструменти