Теорія алгоритмів 2

3.Рекурсивні та рекурсивно перелічні мн-ни (РМ та РПМ), рек-ні та частково рек-ні предикати, їх влас-ті. 4

4.Алгоритмічна розв’язність та нерозв’язність масових проблем. Нерозв’язність проблем зупинки та самозастосованості, наслідки. 5

5.Логіка висловлень (пропозиційна логіка), закони логіки висловлень, тавтології. Числення висловлень. Теорема тавтології. 5

6.Логіка предикатів 1-го порядку, мови 1-го порядку. Мова арифметики. Істинність та виконуваність, логічний наслідок та логічна еквів-сть. Еквів-ні перетвореня формул. Пренексна форма. 6

7.Арифметичні предикати, мн-ни та функції. Арифметичність ЧРФ та РПМ. Теорема Тарського. 7

8.Теорія 1-го порядку, числення предикатів 1-го порядку. Моделі теорій 1-го порядку. Теорема дедукції. Поняття несупреречливості, повноти. 8

9.Теорема Гьоделя про повноту (теорема адекватності) та її наслідки. Теорема компактності. Теореми Гьоделя про неповноту, їх значення. 8

Теорія алгоритмів

1.Формальні моделі алгоритмів та алгоритмічно обчислювальних функцій. Мнр-програми, машини Тьюрінга; чрф, рф, прф. Теза Чорча.

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

Під алгоритмом розуміють скінчену множину точно визначених правил для чисто механічного розв’язку задач певного класу.

Виділимо його характерні властивості: фінітність, масовість, дискретність, елементарність, детермінованість, результативність.

За допомогою алгоритму кожний конкретний результат отримується за скінчену

кількість кроків із скінченої множини даних.

Алгоритм із множиною вхідних даних X та множиною вихідних даних Y

називають X-Y-алгоритмом.

Функція називається алгоритмічно обчислюваною (скорочено АОФ), якщо

існує алгоритм, який її обчислює.

Tеза Чорча. Клас ЧРФ співпадає з класом п-арних АОФ, заданих на множині натуральних чисел.

Машина з натуральнозначними регiстрами (скорочено МНР) є iдеалiзозованою

моделлю комп’ютера. МНР мiстить нескiнченну кiлькiсть регiстрiв, вмiстом яких є натуральнi числа. Регiстри нумеруємо (iменуємо) натуральними числами, починаючи з 0, i позначаємо їх R₀ , R₁ , ..., R_n , .... Вмiст регiстру R_n позначаємо ’R_n.

Послiдовнiсть (’R₀ , ’R₁, ..., ’R_n, ...) вмiстiв регiстрiв МНР назвемо конфiгурацiєю МНР.

МНР може змiнити вмiст регiстрiв згiдно виконуваної нею команди. Скiнченний

список команд утворює програму МНР. Команди програми послiдовно нумеруємо (iменуємо) натуральними числами, починаючи з 1. Номер команди в програмі називатимемо також адресою команди. МНР-програму з командами I₁ , I₂ ,..., I_k будемо позначати I₁I₂...I_k. Довжину (кiлькiсть команд) МНР-програми P позначатимемо |P|.

Команди МНР бувають 4-х типiв.

Тип 1. Обнулення n-го регiстру Z(n): ’R_n : 0.

Тип 2. Збiльшення вмiсту n-го регiстру на 1 S(n): ’R_n :’R_n+1.

Тип 3. Копіювання вмісту регістру T(m,n): ’R_n :’R_m (при цьому ’R_m не змiнюється).

Тип 4. Умовний перехiд J(m,n,q): якщо ’R_n =’R_m , то перейти до виконання q-ї команди, iнакше виконувати наступну за списком команду програми.

Число q в команді J(m,n,q) назвемо адресою переходу.

Виконання однiєї команди МНР назвемо кроком МНР.

Зрозуміло, що саме МНР-програми є формальними моделями алгоритмів, а

поняття МНР використовується для опису функціонування МНР-програм.

Виконання програми МНР починає, перебуваючи в деякiй початковiй конфiгурацiї, з виконання 1-ї за списком команди. Виконання програми завершується (програма зупиняється), якщо наступна для виконання команда вiдсутня (тобто номер наступної команди перевищує номер останньої команди програми). Конфiгурацiя МНР в момент завершення виконання програми називається фiнальною, вона визначає результат роботи МНР-програми над даною початковою конфiгурацiєю. Функцiю називають МНР-обчислюваною, якщо iснує МНР-програма, яка обчислює цю функцiю.

Пiд машиною Тьюрiнга (скорочено МТ) розумiтимемо впорядковану 5-ку (Q,T,, q₀ ,F), де:

Q скiнченна множина внутрiшнiх станiв;

T  скiнченний алфавiт символiв стрiчки, причому T мiстить спецiальний символ порожньої клiтки ;

: QT→QT{R,L,}  функцiя переходiв;

q₀Q  початковий стан;

FQ  множина фiнальних станiв.

Функцiю переходiв в на практицi задають скiнченною множиною команд одного з 3-х видiв: qapbR, qapbL та qapb, де p, qQ, a, bT, QT.

Неформально МТ складається з скiнченної пам’ятi, роздiленої на клiтки нескiнченної з обох бокiв стрiчки та голiвки читання-запису. В кожнiй клiтцi стрiчки мiститься єдиний символ iз T, причому в кожен даний момент стрiчка мiстить скiнченну кiлькiсть символiв, вiдмiнних вiд символа . Голiвка читання-запису в кожен даний момент оглядає єдину клiтку стрiчки.

Якщо МТ знаходиться в станi q та голiвка читає символ a, то при виконаннi команди qapbR (команди qapbL, команди qapb) МТ переходить в стан p, замiсть символу a записує на стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).

Конфiгурацiя, або повний стан МТ  це слово виду xqy, де x,yT*, qQ.

Конфiгурацiю виду q₀x, де 1-й та останнiй символи слова x вiдмiннi вiд , називають початковою. Конфiгурацiю виду xqy, де qF, називають фiнальною. Пiсля переходу до фiнального стану, отже, до фiнальної конфiгурацiї, МТ зупиняється.

Функцiя називається обчислюваною за Тьюрiнгом, або МТ-обчислюваною, якщо iснує МТ, яка її обчислює.

Основними обчислюваними операцiями для п-арних функцiй натуральних аргументiв i значень є наступні операцiї: операція суперпозицiї Sⁿ⁺¹, операція примiтивної рекурсiї R, операція мiнiмiзацiї M.

Операцiя Sⁿ⁺¹ n-арнiй функцiї g(x₁,...,x_n) та n функцiям g₁(x₁,...,x_т), ..., g_n(x₁,...,x_m) одної i тої ж арностi ставить у вiдповiднiсть функцiю

f(x₁,...,x_m)= g(g₁(x₁,...,x_т), ..., g_n(x₁,...,x_m)).

Операцiя примiтивної рекурсiї R n-арнiй функцiї g та (n+2)-арнiй функцiї h ставить у вiдповiднiсть (n+1)-арну функцiю f, яку позначають R(g,h), що задається рекурсивним визначенням

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

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

Це означає, що для всiх значень a₁,..., a_n, b значення f(a₁,...,b_n ,b) обчислюється так:

f(a₁,...,a_n,0) = g(a₁,...,a_n)

f(a₁,...,a_n,1) = h(a₁,...,a_n,0, f(a₁,...,a_n,0))

... ... ... ... ... ... ... ... ... ... ...

f(a₁,...,a_n ,b) = h(a₁,...,a_n ,b-1, f(a₁,...,a_n ,b-1))

Операцiя мiнiмiзацiї M (n+1)-арнiй функцiї g ставить у вiдповiднiсть n-арну функцiю f, яку позначають M(g), що задається спiввiдношенням

f(x₁,...,x_n) = _y(g(x₁,...,x_n,y)=0)

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

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

Тотальну ЧРФ називають рекурсивною функцiєю (скорочено РФ).