МААТЛОГИКА

5.4 Обчислювальн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льки так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¨:

(a)функцiя слiдування s(x) = x0 = x + 1;

(b)функцiя-константа Can(x1; : : : ; xn) = a;

(c)функцiя тотожностi Imn (x1; : : : ; xn) = xm, äå 1 6 m 6 n, n = 1; 2; : : :

2.Оператор пiдстановки Sn+1. Нехай f ¹ n-мiсна числова функцiя, f1; : : : ; fn

m-мiснi числовi функцi¨, тодi через Sn+1(f; f1; : : : ; fn) будемо позначати таку m-мiсну функцiю g(x1; : : : ; xm), яка визнача¹ться рiвнiстю

g(x1; : : : ; xm) = f(f1(x1; : : : ; xm); : : : ; fn(x1; : : : ; xm))

для довiльних x1; : : : ; xm 2 N. Оператор пiдстановки визначений для функцiй f1; : : : ; fn

з однаковими аргументами. При необхiдностi пiдстановки функцiй з рiзним числом аргументiв, ускладнення можна подолати шляхом введення фiктивних аргументiв. Наприклад, функцiю двох аргументiв '(x1; x2) можна подати у виглядi:

'(x1; x2) = Ã(x1; x2; x3) = '(I13(x1; x2; x3); I23(x1; x2; x3)):

Оператор примiтивно¨ рекурсi¨ R. Нехай g ¹ n-ìiñíà, h (n + 2)-ìiñíà i f

(n + 1)-мiсна числовi функцi¨. Будемо казати, що f отриму¹ться з g i h за допомогою оператора примiтивно¨ рекурсi¨ (при цьому пишемо f = R(g; h)), якщо для довiльних x1; : : : ; xn; y 2 N справедливi рiвностi:

f(x1; : : : ; xn; 0) = g(x1; : : : ; xn);

f(x1; : : : ; xn; y + 1) = h(x1; : : : ; xn; y; f(x1; : : : ; xn; y)):

Знайдемо послiдовно значення числово¨ функцi¨ f:

f(x1; : : : ; xn; 0) = g(x1; : : : ; xn);

f(x1; : : : ; xn; 1) = h(x1; : : : ; xn; 0; g(x1; : : : ; xn));

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢

f(x1; : : : ; xn; m + 1) = h(x1; : : : ; xn; y; f(x1; : : : ; xn; m)):

81

Приклад. Нехай g = 0, h = 2x+y, òîäi f(0) = 0, f(1) = 0, f(2) = 2, f(3) = 2¢2+2 = 6, f(4) = 2 ¢ 3 + 2 ¢ 2 + 2 = 12; f(x + 1) = 2x + 2(x ¡ 1) + ¢ ¢ ¢ + 2 ¢ 2 + 2 = 2 x+12 x = (x + 1)x.

Оператор мiнiмiзацi¨ M. Цей оператор да¹ можливiсть визначати функцiю вiд n аргументiв за допомогою функцi¨ (n + 1)-го аргументу. Нехай дана обчислювальна

функцiя g(x1; : : : ; xn; y); фiксу¹мо значення аргументiв x1 = a1; : : : ; xn = an. Оператором мiнiмiзацi¨ визнача¹ться найменше натуральне число ¯, для якого

g(a1; a2; : : : ; an; ¯) = 0; познача¹ться дана операцiя так:

¯ = ¹y[ g(a1; a2; : : : ; an; y) = 0 ];

äå ¹y ¹ символ дано¨ операцi¨. Очевидно, що значення ¯ ¹ функцi¹ю вiд a1; a2; : : : ; an. Таким чином, ми ма¹мо означення обчислювально¨ функцi¨ f(x1; x2; : : : ; xn) (= (Mg)(x1; x2; : : : ; xn)) за допомогою операцi¨ ¹y (яка назива¹ться операцi¹ю

кореня):

f(x1; x2; : : : ; xn) = ¹y[ g(x1; x2; : : : ; xn; y) = 0]:

Якщо не iсну¹ таких значень y, ïðè ÿêèõ g(x1; : : : ; xn; y) = 0, то функцiя

вважа¹ться невизначеною на вiдповiдному наборi значень x1; x2; : : : ; xn. Êðiì òîãî, вважа¹ться, що функцiя f(x1; : : : ; xn) невизначена на такому наборi значень x1 = a1; : : : ; xn = an, для якого iсну¹ корiнь рiвняння g(a1; : : : ; an; y) = 0, але хоча б для одного значення (0 6 ° < ¯) функцiя g(a1; : : : ; an; °) невизначена.

3. Функцiя f назива¹ться примiтивно-рекурсивною, якщо вона ¹ однi¹ю з

äå s(x) = x + 1.

Функцiя f

функцiй s; C01; Imn за допомогою ск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в теорему про неповноту формально¨ арифметики.

82

5.5 Машина Тьюрiнга

Означення машини Тьюрiнга. Допустимi елементарнi операцi¨ машини Тьюрiнга. Програма роботи машини, конфiгурацiя, функцiональна схема машини Тьюрiнга.

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

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

Означення машини Тьюрiнга. Основними блоками машини Тьюрiнга ¹:

1)Блок зовнiшньо¨ пам'ятi (БП). Це нескiнченна в обидва боки стрiчка, яка розбита на комiрки.

2)Функцiональний (програмний) блок (БФ). Цей блок зображу¹ться скiнченною таблицею з двома входами.

3)Читаючий елемент (ЧЕ). Вiн фiксу¹ одну комiрку стрiчки пам'ятi.

4)Блок стану (БС) (блок внутрiшньо¨ пам'ятi). Вiн фiксу¹ той чи iнший стан машини.

Вхiдна iнформацiя пода¹ться (коду¹ться) в комiрках пам'ятi лiтерами зовнiшнього алфавiту: ¾ = fs0; s1; : : : ; skg. В кожнiй комiрцi може мiститися лише одна лiтера. Серед

83

лiтер алфавiту ¹ лiтера, яка вiдповiда¹ "порожньому символу", вважа¹мо ¨¨ лiтерою s0 àáî µ. "Порожнiй символ"знаходиться у всiх комiрках пам'ятi, якi не зайнятi iншими

лiтерами зовнiшнього алфавiту.

Стани машини Тьюрiнга кодуються лiтерами внутрiшнього алфавiту:

C= fq0; q1; : : : ; qmg

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ту. При цьому попереднiй вмiст фiксовано¨ комiрки витира¹ться.

2)Перехiд до нового стану. При цьому в блок станiв помiща¹ться вiдповiдна лiтера внутрiшнього алфавiту.

3)Фiксування комiрки пам'ятi за однi¹ю з адрес Н, П, Л. При цьому здiйсню¹ться змiна розташування читаючого елемента.Точнiше, за адресою Н розташування ЧЕ не змiню¹ться, за адресою П читаючий елемент зсува¹ться на одну комiрку вправо, а за адресою Л влiво.

Кожна команда дi¨ машини Тьюрiнга зображу¹ться трьома лiтерами:

sqC;

äå s лiтера зовнiшнього алфавiту, яка запису¹ться у фiксовану комiрку; q лiтера внутрiшнього алфавiту, яка розмiщу¹ться в блок станiв; C îäíà ç ë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онально¨ схеми машини.

84

Приклад. Алгоритм додавання натуральних чисел продемонстру¹мо на прикладi знаходження суми натуральних чисел 3 + 2.

Зовнiшнiй алфавiт: ¾ = fµ; 1; ¤g Внутрiшнiй алфавiт: C = fq0; q1; q2; !g Початкова конфiгурацiя машини Тьюрiнга:

Функцiональна схема машини Тьюрiнга:

85

Лiтература

[1]В. И. Игошин, Математическая логика и теория алгоритмов, Саратов: Изд. СГУ, 1991.

[2]Я. В. Хромой, Математична логiка, К.: Вища школа, 1983.

[3]Ф. М. Лиман, Математична логiка i теорiя алгоритмiв, Суми: Слобожанщина, 1998.

[4]Я. В. Хромой, Збiрник вправ i задач з математично¨ логiки, К.: Вища школа, 1978.

[5]В. И. Игошин, Задачник-практикум по математической логике, М.: Просвещение, 1986.

[6]Р. Столл, Множества, Логика. Аксиоматические теории. М.: Просвещение, 1978.

[7]Э. Мендельсон, Введение в математическую логику, М.: Наука, 1971.

[8]Л. А. Калужнин, Что такое математическая логика, М.: Наука, 1964.

[9]П. С. Новиков, Элементы математической логики, М.: Физматгиз, 1959.

[10]С. К. Клини, Математическая логика, М.: Изд. "Мир", 1973.

[11]Л. А. Калужнiн, В. С. Королюк, Алгоритми i математичнi машини, К.: Радянська школа, 1964.

[12]Ю. Л. Ершов, Е. А. Палютин, Математическая логика, М.: Наука, 1979.

[13]А. Ч¼рч, Введение в математическую логику, т. 1, М.: Изд. иностр. лит., 1960.

[14]С. Г. Гиндикин, Алгебра логики в задачах, М.: Наука, 1972.

[15]А. И. Мальцев, Алгоритмы и рекусивные функции, М.: Наука, 1965.

[16]С. К. Клини, Введение в метаматематику, М.: Изд-во иностр. лит., 1957.

[17]А. А. Френкель, И. Бар-Хиллел, Основания теории множств, М.: Изд. "Мир", 1966.

86