МААТЛОГИКА

Дана iнтерпретацiя назива¹ться моделлю для дано¨ множини формул ¡, якщо кожна

формула з ¡ iстинна в данiй iнтерпретацi¨.

Вiдмiтимо деякi властивостi формул при iнтерпретацiях:

1.Формула A хибна в данiй iнтерпретацi¨ тодi i тiльки тодi, коли » A iстинна в тiй же iнтерпретацi¨, i A iстинна тодi i тiльки тодi, коли » A хибна.

2.Жодна формула не може бути одночасно iстинною i хибною в однiй i тiй же iнтерпретацi¨.

3.Якщо в данiй iнтерпретацi¨ iстиннi A i A ¡! B, то iстинне B.

4.A ¡! B хибне в данiй iнтерпретацi¨ тодi i тiльки тодi, коли A в цiй iнтерпретацi¨ iстинне, а B хибне.

5.(a) A^B викону¹ться на послiдовностi s òîäi i òiëüêè òîäi, êîëè A викону¹ться на s

i B викону¹ться на s. A_B викону¹ться на s òîäi i òiëüêè òîäi, êîëè A викону¹ться на s àáî B викону¹ться на s. A Ã! B викону¹ться на послiдовностi s òîäi i òiëüêè òîäi, êîëè àáî A викону¹ться на s i B викону¹ться на s, àáî êîëè A не викону¹ться на s i B не викону¹ться на s.

Будемо казати, що iнтепретацiя M дано¨ теорi¨ першого порядку iзоморфна

(b) (9xi)A викону¹ться на s òîäi i òiëüêè òîäi, êîëè A викону¹ться хоч би на однiй послiдовностi s0, ÿêà âiäðiçíÿ¹òüñÿ âiä s íå áiëüø íiæ îäíi¹þ i-ю компонентою.

6. A iстинне в данiй iнтерпретацi¨ тодi i тiльки тодi, коли в цiй iнтерпретацi¨

iстинне (8xi)A. Замиканням дано¨ формули A назвемо формулу, яка отриму¹ться приписуванням до A попереду знакiв кванторiв загальностi, якi мiстiть в порядку

спадання iндексiв всi вiльнi предметнi змiннi, що входять в A.

7.Кожний частинний випадок всяко¨ тавтологi¨ iстинний у кожнiй iнтерпретацi¨.

8.Нехай вiльнi предметнi змiннi формули A мiстяться серед змiнних xi1 ; : : : ; xin . Тодi якщо у послiдовностей s i s0 компоненти з номерами i1; : : : ; in спiвпадають, то формула A викону¹ться на s тодi i тiльки тодi, коли вона викону¹ться на s0.

9.Якщо формула A замкнена, то в довiльнiй данiй iнтепретацi¨ або iстинна A, або iстинна » A (тобто хибна A).

Формула A числення предикатiв назива¹ться загальнозначущою, якщо вона iстинна в кожнiй iнтерпретацi¨. Формула A числення предикатiв назива¹ться виконуваною, якщо iсну¹ iнтерпретацiя, в якiй A викону¹ться хоча б на однiй послiдовностi iз §.

Будемо казати, що iнтепретацiя M дано¨ теорi¨ першого порядку K iзоморфна iншiй iнтерпретацi¨ M0 òåîði¨ K, якщо iсну¹ таке вза¹мно однозначне вiдображення g (назива¹ться iзоморфiзмом) областi D iнтерпретацi¨ M на область D0 iнтерпретацi¨ M0, ùî

(a)ÿêùî (Anj )¤ i (Anj )0 iнтерпретацi¨ предикатно¨ змiнно¨ Anj âiäïîâiäíî â M i M0, òî, ÿêi á íå áóëè b1; : : : ; bn ç D, умова (Anj )¤(b1; : : : ; bn) викону¹ться тодi i тiльки тодi, коли викону¹ться умова (Anj )0(g(b1); : : : ; g(bn)), тобто

(b1; : : : ; bn) 2 (Anj )¤ Ã! (g(b1); : : : ; g(bn)) 2 (Anj )0;

61

для довiльного терма t;

(b)ÿêùî (fjn)¤ i (fjn)0 iнтерпретацi¨ функцiонально¨ змiнно¨ fjn âiäïîâiäíî â M i M0, то для довiльних b1; : : : ; bn ç D справедлива рiвнiсть

g((fjn)¤(b1; : : : ; bn)) = (fjn)0(g(b1); : : : ; g(bn));

(c) ÿêùî a¤j i a0j iнтерпретацi¨ предметно¨ константи aj âiäïîâiäíî â M i M0, òî

a0j = g(a¤j ).

Вiдмiтимо, що коли iнтерпретацi¨ M i M0 iзоморфнi, то ¨х областi мають однакову потужнiсть, тобто однакове число елементiв у випадку скiнченних множин.

Теорема 30. ßêùî g iзоморфiзм iнтерпретацiй M i M0, то (1) якими б не

були формула A òåîði¨ K i ïîñëiäîâíiñòü s = (b1; b2; : : :) елементiв областi D, формула A викону¹ться на s тодi i тiльки тодi, коли вона викону¹ться на вiдповiднiй

послiдовностi g(s) = (g(b1); g(b2); : : :) i, отже, (2) формула A iстинна в M тодi i тiльки тодi, коли вона iстинна в M0.

Нехай K теорiя першого порядку, серед предикатних змiнних ¹ A21. Будемо для скорочення писати t = s çàìiñòü A21(t; s) i t 6= s çàìiñòü » A21(t; s). Òåîðiÿ K назива¹ться

теорi¹ю першого порядку з рiвнiстю, якщо наступнi формули ¹ теоремами K:

(1) (8x1)(x1 = x1), (рефлексивнiсть рiвностi);

(2) (x = y) ¡! (A(x; x) ¡! A(x; y)), (пiдстановочнiсть рiвностi),

äå x; y предметнi змiннi, A(x; x) довiльна формула, а A(x; y) отриму¹ться з A(x; x)

замiною яких-небудь вiльних входжень x входженнями y. Неважко тепер показати, що ма¹ мiсце таке твердження: у всякiй теорi¨ першого порядку з рiвнiстю

(a) ` t = t

(b) ` x = y ¡! y = x;

(c) ` x = y ¡! (y = z ¡! x = z).

Отже, для кожно¨ моделi теорi¨ першого порядку K з рiвнiстю вiдношення ", що вiдповiда¹ в цiй моделi предикатнiй змiннi =, ¹ вiдношенням еквiвалентностi. Якщо

в областi деяко¨ моделi це вiдношення ¹ тотожнiстю, то ця модель назива¹ться

нормальною.

Нехай ! кардинальне число. Теорiя K першого порядку з рiвнiстю назива¹ться

!-категоричною якщо 1) кожнi двi нормальнi моделi теорi¨ K, якi мають потужнiсть !, iзоморфнi, i 2) K ма¹ хоча б одну нормальну модель потужностi !.

3. Справедлива наступна теорема:

Теорема 31. У кожному численнi предикатiв першого порядку всяка теорема ¹ загальнозначуща формула.

Справдi, неважко бачити, що аксiоми, що задаються схемами (1) (5) ¹ загальнозначущi формули. Правила виведення МР i Gen зберiгають властивiсть загальнозначущостi, тому кожна теорема числення предикатiв ¹ загальнозначуща формула.

62

Теорема 32 (Гедель). Кожна несуперечлива теорiя першого порядку ма¹ зчисленну модель.

Означення 7. Теорiя першого порядку K назива¹ться повною, якщо для довiльно¨ замкнено¨ формули A òåîði¨ K àáî `K A, àáî `K» A.

Теорема 33. Кожна загальнозначуща формула несуперечливо¨ теорi¨ K першого порядку ¹ теоремою теорi¨ K.

Доведення. Достатньо розглянути лише замкненi формули A, оскiльки кожна формула B загальнозначуща тодi i тiльки тодi, коли загальнозначущою ¹ ¨¨ замикання, i виводиться в теорi¨ K òîäi i òiëüêè òîäi, êîëè â K виводиться ¨¨ замикання. Отже, нехай A загальнозначуща замкнена формула теорi¨ K. Припустимо, що A не ¹ теоремою в K. Тодi якщо ми додамо формулу » A ÿê íîâó àêñiîìó äî òåîði¨ K, то отрима¹мо нову теорiю K0 = K[f» Ag, яка буде несуперечливою.14 Òåîðiÿ K0 ма¹ модель M (див. теорему 32). Оскiльки » A ¹ àêñiîìîþ â K0, òî » A iстинна в M, а оскiльки формула A загальнозначуща, то i вона iстинна в M. Отже, ми прийшли до того, що формула A одночасно iстинна i хибна в M, що неможливо. Таким чином, формула A повинна бути теоремою теорi¨ K. ¤

Наслiдок 14 (теорема Геделя про повноту). У кожному численнi предикатiв першого порядку теоремами ¹ всi тi i тiльки тi формули, якi ¹ загальнозначущими.

14 Припустимо, що K0 суперечлива теорiя, тодi знайдеться формула B òàêà, ùî K0 ` B^ » B, тобто K; » A ` B^ » B, çâiäêè K `» A ¡! B^ » B. За законом контрапозицi¨ K `» (B^ » B) ¡! A, тобто K `» B _ B ¡! A, àëå `» B _ B, òîìó K ` A, що протирiччить припущенню.

63

4.3 Формальна арифметика

Система аксiом формально¨ арифметики. Стандартна модель формально¨ арифметики, неповнота формально¨ арифметики.

1. Поряд з геометрi¹ю арифметика ¹ найбiльш безпосередньо iнту¨тивною областю математики. Цiлком природно тому саме з арифметики розпочати спробу формалiзацi¨ й строгого об рунтування математики. Перша напiваксiоматична побудова цi¹¨ дисциплiни була запропонована Дедекiндом (1901 р.) i стала вiдомою пiд назвою "системи аксiом Пеано". Цю систему можна сформулювати таким чином:

(P1) 0 ¹ натуральне число;

(P2) для довiльного натурального числа x iсну¹ iнше натуральне число, яке познача¹ться x0 i назива¹ться: (безпосередньо) слiдуючим за x;

(P3) 0 6= x0 для довiльного натурального числа x; (P4) ÿêùî x0 = y0, òî x = y;

(P5) ÿêùî Q ¹ властивiсть, якою, можливо, володiють однi i не володiють iншi натуральнi числа, i якщо

1.натуральне число 0 володi¹ властивiстю Q i

2.для кожного натурального числа x ç òîãî, ùî x володi¹ властивiстю Q, виплива¹, що натуральне число x0 володi¹ властивiстю Q,

то властивiстю Q володiють всi натуральнi числа (принцип iндукцi¨ ).

Цих аксiом, разом з деяким фрагментом теорi¨ множин, достатньо для побудови не тiльки арифметики, але й теорi¨ рацiональних, дiйсних та комплексних чисел. Однак в цих аксiомах мiстяться iнту¨тивнi поняття такi, як, наприклад, "властивiсть", що заважа¹ всiй системi бути строгою формалiзацi¹ю. Тому ми зараз побуду¹мо деяку теорiю першого порядку S, засновану на системi Пеано, яка виявиться, при всiй

видимостi, достатньою для виведення основних результатiв елементарно¨ арифметики. Ця теорiя першого порядку S буде мати тiльки одну предикатну змiнну A21, îäíó предметну константу a1 i три функцiональних змiнних f11, f12, f22. Щоб не поривати iз звичними нам в неформальнiй арифметицi позначеннями, в подальшому ми будемо писати t = s çàìiñòü A21(t; s), 0 çàìiñòü a1 i t0, t + s, t ¢ s âiäïîâiäíî çàìiñòü f11(t), f12(t; s),

f22(t; s), äå t i s терми. Наступнi формули ¹ власними аксiомами теорi¨ S:

(S1) x1 = x2 ¡! (x1 = x3 ¡! x2 = x3);

(S2) x1 = x2 ¡! x01 = x02;

(S3) 0 6= (x1)0;

(S4) x01 = x02 ¡! x1 = x2;

(S5) x1 + 0 = x1;

64

(S6) x1 + x02 = (x1 + x2)0; (S7) x1 ¢ 0 = 0;

(S8) x1 ¢ (x02) = (x1 ¢ x2) + x1;

(S9) A(0) ¡! ((8x)(A(x) ¡! A(x0)) ¡! (8x)A(x)),

äå A(x) довiльна формула теорi¨ S.

Схема аксiом (S9), яку ми будемо називати принципом математично¨ iндукцi¨,

íå âiäïîâiä๠ïîâíiñòþ àêñiîìi (P5) системи аксiом Пеано, оскiльки в цiй останнiй

iнту¨тивно припускаються 2@0 властивостей натуральних чисел, а схема аксiом (S9)

може мати справу лише iз зчисленною множиною властивостей, якi визначаються формулами теорi¨ S.

Àêñiîìè (S3) i (S4) вiдповiдають аксiомам (P3) i (P4) системи аксiом Пеано. Аксiоми (P1) i (P2) пеанiвсько¨ системи забезпечу¹ iснування нуля 0i операцi¨ "безпосередньо

наступний", яким в теорi¨ S вiдповiда¹ предметна константа a1 i функцiональна çìiííà f11. Àêñiîìè (S1) i (S2) забезпечують деякi необхiднi властивостi рiвностi,

якi Дедекiндом i Пеано передбачались як iнту¨тивно очевиднi. Аксiоми (S5) (S8)

являють собою рекурсивнi рiвностi, якi слугують означеннями операцiй додавання й множення. Жодних постулатiв, якi вiдповiдають цим аксiомам, Дедекiнд i Пеано не сформулювали, тому що вони допускали використання iнту¨тивно¨ теорi¨ множин, в рамках яко¨ iснування операцiй + i ¢, якi задовольняють аксiоми (S5) (S8), âèâiäíèì.

2. Вiдмiтимо, що iнтерпретацiя теорi¨ S, â ÿêié

(a) множина всiх цiлих невiд'¹мних чисел слугу¹ областю iнтерпретацi¨;

(b) цiле число 0 iнтерпрету¹ символ 0;

(c) операцiя взяття наступного (додавання одиницi) елемента iнтерпрету¹ функцiю 0 (тобто функцiональну змiнну f11);

(d) звичайне додавання i множення iнтерпретують як + i ¢;

(e) предикатна лiтера = iнтерпрету¹ться вiдношенням тотожностi,

¹ нормальною моделлю теорi¨ S. Ця модель назива¹ться стандартною моделлю теорi¨ S. Кожна нормальна модель теорi¨ S, яка неiзоморфна стандартнiй моделi, назива¹ться

нестандартною моделлю теорi¨ S.

Якщо ми визна¹мо цю стандартну iнтерпретацiю моделлю теорi¨ S, òî òîäi ìè

повиннi будемо визнати i факт несуперечностi цi¹¨ теорi¨. Однак семантичнi методи, що включають в себе, як правило, вiдому долю теоретико-множинних мiркувань, за думкою деяких математикiв ¹ дуже ненадiйною основою для доведення несуперечностi. Бiльш того, ми i не доводимо строго, що аксiоми теорi¨ S iстиннi в стандартнiй

iнтерпретацi¨, а прийма¹мо це твердження лише всього як iнту¨тивно очевидне. Тому, а також з ряду iнших причин прийнято кожний раз, коли на твердження про несуперечнiсть теорi¨ S спира¹ться деяке доведення, явно посилатися на це твердження

як на деяку недоведену гiпотезу.

65

3. В данiй формальнiй теорi¨ S нема¹ жодних принципових перешкод для того, щоб

кожну теорему, яка доводиться в курсах елементарно¨ теорi¨ чисел (наприклад, в книзi Виноградова И.М., Основы теории чисел), перевести на мову теорi¨ S i побудувати

виведення такого перекладу в цiй теорi¨. Iснують деякi теоретико-числовi функцi¨ такi, як, наприклад, x! i xy, якi можна визначити в S. З iншого боку, деякi класичнi

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

(наприклад, теорема про простi числа) в самих формулюваннях мiстять неелементарнi поняття, подiбнi до поняття логарифмiчно¨ функцi¨, i такi теореми не можуть бути навiть сформульованi на мовi теорi¨ S, якщо тiльки для них не iсну¹ еквiвалентно¨

елементарно¨ форми.

Говорячи про силу i виражальнi можливостi теорi¨ S розглянемо вiдому теорему

Геделя про неповноту формально¨ арифметики. В цiй теоремi доведено, що iснують такi замкненi формули, якi недовiднi й неспростовнi в теорi¨ S, ÿê òiëüêè âîíà

несуперечлива; отже, iсну¹ формула, iстинна в стандартнiй iнтерпретацi¨, але невивiдна в S. Виявля¹ться, що така неповнота теорi¨ S не може бути вiднесена за рахунок

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

66

5 Елементи теорi¨ алгоритмiв

5.1 Поняття алгоритму та його характернi риси

Поняття про алгоритм, його характернi риси. Граф-схема алгоритму. Алфавiт. Кодування iнформацi¨. Алфавiтнi алгоритми.

1. Поняття алгоритму (або алгорифму) належить до основних понять сучасно¨ математики. Воно поряд з 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¨, якi дозволяють розв'язувати рiзнi задачi, вiдомi з давнiх часiв i не тiльки в математицi, але й в iнших галузях людсько¨ дiяльностi.

Розглянемо два приклади вiдомих алгоритмiв:

Приклад 1. Алгоритм Евклiда. Цей алгоритм використову¹ться при знаходженнi найбiльшого спiльного дiльника для довiльних двох даних натуральних чисел a i b.

Нехай a > b > 0. Äiëèìî a íà b, отриму¹мо остачу r1 < b. ßêùî r1 = 0, òî b ¹ найбiльший спiльний дiльник (НСД), якщо ж r1 > 0, то шуканий дiльник спiвпада¹ з НСД чисел b i r1. Òîìó b äiëèìî íà r1, i якщо нова остача r2 = 0, òî r1 шуканий дiльник, якщо r1 > r2 > 0, òî äiëèìî r1 íà r2. Продовжуючи цей процес, отрима¹мо:

a > b > r1 > r2 > : : : > rn > rn+1 = 0:

Останн¹ вiдмiнне вiд нуля в цьому ланцюгу (rn) i буде шуканим. При цьому весь процес закiнчиться за скiнченне число крокiв, оскiльки натуральних чисел, менших числа b,

скiнченне число.

Приклад 2. Додавання цiлих чисел. Вхiднi данi цифровi записи натуральних чисел у виглядi послiдовностi знакiв: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, якi називаються цифрами. Наприклад, 71, 935, 01026. Правила додавання можна сформулювати так:

1.Для фiксованих цифр доданкiв з врахуванням цифри перенесення записати вiдповiдну ¨м цифру суми i вiдмiтити нове перенесення (якщо воно ¹).

2.Фiксувати наступнi влiво цифри доданкiв i мiсце ново¨ цифри суми.

3.Повторити виконання правил 1 i 2, поки не будуть вичерпанi всi значущi цифри доданкiв i перенесення.

Цей процес можна виконувати формально не задумуючись. Кожний процес, який може бути автоматизований, ¹ алгоритмiчним процесом.

З наведених прикладiв можна зробити такi висновки:

1. Вхiднi данi задач завжди задаються у виглядi деяко¨ послiдовностi символiв.

67

2.Процес розв'язування яко¨-небудь задачi явля¹ собою послiдовнiсть перетворень записiв вхiдних даних в запис результату.

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

4.Послiдовнiсть допустимих операцiй, яка визнача¹ деякий алгоритм, не залежить вiд конкретного виду вхiдних даних.

5. Порядок виконання допустимих операцiй визнача¹ться однозначно, тобто пiсля виконання деяко¨ допустимо¨ операцi¨ точно вiдомим ¹ наступний етап перетворень.

Аналiз змiсту конкретних алгоритмiв дозволя¹ сформулювати основнi загальнi риси алгоритмiв:

1. Визначенiсть алгоритму, тобто однозначне визначення результату кожно¨ допустимо¨ операцi¨ i порядку виконання операцiй. Виконання алгоритму явля¹ собою строго детермiнований процес, який не залежить вiд того, хто його викону¹ (обчислювач чи машина).

2. Масовiсть алгоритму, тобто можливiсть застосування алгоритму до рiзних вхiдних даних. Алгоритм розв'язу¹ не одну конкретну задачу, а визначений клас однотипних задач.

3. Результативнiсть алгоритму, тобто скiнченнiсть процесу перетворення вхiдних даних. Застосування алгоритму до вхiдних даних завжди завершу¹ться утворенням певного результату розв'язку задачi.

2. 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 нормального алгоритму Маркова.

Числов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потезу про те, що клас алгоритмiчно обчислювальних функцiй спiвпада¹ з класом всiх частково-рекурсивних функцiй. Ранiше аналогiчну гiпотезу

68

в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нах класи машин, на яких можна зд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дностi з заданою програмою. Виявилось, що клас функцiй, обчислювальних за допомогою нормальних алгоритмiв, спiвпада¹ з класом частково-рекурсивних функцiй. Таким чином, всi вiдомi уточнення поняття алгоритму призводять до одного i того ж класу функцiй частково-рекурсивним функцiям. Це доводить еквiвалентнiсть перерахованих уточнень.

3.Схема побудови алгоритмiчно¨ системи:

1.Для описання задач зада¹ться система об'¹ктiв (символiв), мiж якими встановлюються деякi спiввiдношення. (Алфавiт)

2.Визнача¹ться сукупнiсть допустимих операцiй.

3.Алгоритмiчний процес процес застосування алгоритму до даного початкового стану.

4.Алгоритм визнача¹ться сукупнiстю допустимих операцiй iз вказiвкою порядку ¨х виконання.

Граф-схемою алгоритму назива¹ться скiнченна система точок (якi називаються вузлами граф-схеми), якi зв'язанi мiж собою стрiлками, що задовольняють такi властивостi:

1.Iсну¹ точка, яка назива¹ться входом граф-схеми, з яко¨ виходить лише одна стрiлка i в яку стрiлки не входять.

2.Iсну¹ точка, яка назива¹ться виходом граф-схеми, з яко¨ не виходить жодна стрiлка.

3.Iншi вузли граф-схеми можуть бути або D-точками (дi¨), або P -точками (розпiзнавання). З кожно¨ D-точки виходить тiльки одна стрiлка. З кожно¨ P -

точки виходять двi стрiлки: одна з мiткою 1 (1 !), iíøà ç ìiòêîþ 0 (0 !). В кожну точку граф-схеми може входити довiльне число стрiлок.

69

4. Абстрактним алфавiтом назива¹ться скiнченна сукупнiсть рiзних знакiв (символiв), якi називаються лiтерами алфавiту. Познача¹мо алфавiти A, B òîùî.

Слово скiнченна впорядкована сукупнiсть лiтер даного алфавiту. Наприклад, якщо A = fa; b; c; dg, òî a, aa, ab, abc, abbadaadc слова. ¤ порожн¹ слово. Два слова

A i B називаються рiвними, якщо вони складаються з однакових лiтер, якi однаково розмiщенi, при цьому пишемо A = B. На множинi слiв вводиться операцiя приписування слiв. Наприклад, якщо A = abcd, B = bcda, òî AB = abcdbcda. Ця операцiя задовольня¹ такi властивостi: A(BC) = (AB)C i ¤A = A¤ = A для довiльних слiв A; B; C. Таким чином, множина всiх слiв WA в алфавiтi A утворю¹ пiвгрупу з одиницею ¤ вiдносно

операцi¨ приписування слiв.

Довжина слова число лiтер в словi. Довжина слова A познача¹ться через l(A). Наприклад, якщо A = abcda, òî l(A) = 5. l(¤) = 0.

Слово A назива¹ться початком слова B, якщо iсну¹ слово C òàêå, ùî B = AC. Слово A назива¹ться кiнцем слова B, якщо iсну¹ слово C òàêå, ùî B = CA. Слово A

назива¹ться пiдсловом слова B, якщо iснують такi слова C i D, ùî B = CAD.

Кодування iнформацi¨. Iнформацiя про математичну задачу часто пода¹ться словами в алфавiтi з 10-ти лiтер f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g. Однак натуральнi числа можна

подати в алфавiтi з однi¹¨ лiтери f j g: 0 ¤, 1 j, 2 jj, 3 jjj, 4 jjjj тощо. Можна

подати натуральнi числа в алфавiтi f0; 1g у двiйковiй системi числення: 0 0, 1

1, 2 10, 3 11, 4 100, 5 101, 6 110, 7 111, 8 1000, 9 1001, 10 1010 тощо. В алфавiтi f¡; j; = g можна зображати рацiональнi числа, наприклад, ¡35 зображу¹ться як ¡jjj=jjjjj. В алфавiтi f¡; j; =; ¤g можна зображати вектори: пара чисел

¡	3	;	1		зображу¹ться словом ¡jjj=jjjjj ¤ j=jjjj. В алфавiтi f¡; j; =; ¤; ¤g можна зображати
	5		4
матрицi. Наприклад, матриця						2	¡3	зображу¹ться словом jj ¤ ¡jjj¤jjjj ¤ jj	. Îòæå,
						4	2

всяка iнформацiя про задачу може бути зображена словом в деякому абстрактному алфавiтi. Вiдмiтимо, що можна будь-яку iнформацiю зображати лише дволiтерному алфавiтi f0; 1g, наприклад, 010, 0110, 01110, 011110 òîùî.

Алфавiтнi алгоритми. Алгоритмiчний процес розв'язування задачi можна розглядати як процес перетворення слiв в абстрактному алфавiтi. Вхiдними даними i результатом алгоритму ¹ слова.

Означення 8. Алгоритмом в абстрактному алфавiтi A назива¹ться вiдповiд-

нiсть мiж словами в A, яка конструктивно зада¹ться скiнченною системою допустимих операцiй.

Алгоритми будемо позначати через A, B, C тощо. Говорять, що алгоритм A застосовний до слова X, якщо процес перетворень вхiдного слова X алгоритмом A закiнчу¹ться деяким словом Y , при цьому записують A(X) = Y . Сукупнiсть слiв даного алфавiту, до яких застосовний алгоритм A, назива¹ться областю застосовностi алгоритму A. Алгоритм в розширенi алфавiту A назива¹ться алгоритмом над алфавiтом A. Алгоритми A i B над алфавiтом A називаються еквiвалентними вiдносно A, якщо для довiльного слова X в алфавiтi A, до якого застосовний алгоритм A, застосовний також алгоритм B, i результати ¨х дiй спiвпадають, тобто A(X) = B(X).

70