Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Міністерство освіти та науки України

Хмельницький національний університет

Реферат

З курсу Математичної логіки та теорії алгоритмів

На тему: “Поняття примітивно рекурсивної функції (ПРФ), частково рекурсивної функції (ЧРФ) та рекурсивної функції (РФ)”

Виконала:

Ст. групи ПМ 14-1

Горбачова Анастасія

Викладач:

Драч Ілона Володимирівна

2015



Зміст

Вступ

1. Походження рекурсивних функцій

2. Поняття рекурсивної функції

3. Поняття примітивно рекурсивної функції(ПРФ)

4. Поняття частково рекурсивної функції (ЧРФ)

Висновок

Додатки



Вступ

Спочатку для того, щоб розглянути поняття рекурсивних функцій потрібно мати уявлення про саму рекурсію. Рекурсія - це часткове визначення об'єкта через себе, визначення об'єкта через використання раніше визначених. У математиці та інформатиці рекурсія пов'язана з методом визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекурентною формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через саму себе з використанням раніше заданих окремих визначень. Приклади рекурсії: факторіал, числа Фібоначчі, трикутник Серпінського та ін.(див. додаток 1).[1]

Сам термін рекурсивна функція в теорії обчислюваності використовується для позначення трьох класів функцій. Вони були виведені Куртом Геделем з метою формалізації поняття обчислюваності. [3] Також такими математики як: Стівен Коул Кліні - автор монографій з математичної логіки, основах математики і теорії рекурсивних функцій [4], Алонзо Черч - автор тези Черча, теореми Черча, лямбда-оператора та похідних понять [5], Алан Тьюрінг відомий як творець абстрактної машини Тьюрінга, - зробили істотний вплив на розвиток теорії рекурсивних функцій та математики в цілому.

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

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



1. Походження рекурсивних функцій

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

Дослідження цих питань призвело до створення в 1930-х роках теорії рекурсивних функцій, яка була розроблена С.Кліні. При цьому клас обчислюваних (рекурсивних) функцій отримав такий опис, який нагадав процес побудови аксіоматичної теорії на основі деякої системи аксіом. Спочатку були обрані найпростіші функції, ефективне обчислення яких було очевидне ( свого роду «аксіоми»). Потім були сформульовані деякі правила (оператори), на основі яких можна побудувати нові функції з вже наявних (свого роду «правила виведення»). Потім необхідним класом функцій стала сукупність всіх функцій, які утворюються з найпростіших за допомогою вибраних операторів. [6]

Самі ж терміни «рекурсивна функція» та «загально рекурсивна функція» прижилися в силу історичних причин і по суті є результатом неточного перекладу англійських термінів partial recursive function і total recursive function, які за змістом більш правильно перекладати як «рекурсивні функції, визначені на частині множини можливих аргументів» та «рекурсивні функції, визначені на всій множині можливих аргументів». Прислівник «частково» відноситься не до прикметника «рекурсивні», а до області визначення функції. Можливо, більш правильною було б «частково визначені рекурсивні функції» і просто « скрізь визначені рекурсивні функції». Але довгі назви не прижилися. [3]

2. Поняття рекурсивної функції

Другий напрямок уточнення поняття алгоритму проходило по шляху уточнення класу обчислюваних об'єктів. Розглянемо тут систему С.Кліні - клас рекурсивних функцій. Доведено, що обчислювана на машині Тьюрінга функція є рекурсивною і , навпаки, для всякої рекурсивної функції знайдеться машина Тьюрінга, яка обчислює її. Це говорить про еквівалентність даних визначень. В даний час відомо кілька еквівалентних понять алгоритму та обчислюваності ( машини Тьюрінга, нормальні алгоритми Маркова, продукції Поста, Ербран-Геделевське числення рівностей, частково рекурсивні функції і т.д.) [7]

Базовими примітивними функціями, за визначенням, є такі наступні функції:

1) Нульова функція ;

2) Функція слідування: ;

3) Функція проектування: .

Очевидно, що всі базові функції є обчислювані.

Оператори, які зберігають обчислюваність функції:

1). Операція суперпозиції :

Кажуть, що функція виникає із функцій , суперпозицією, якщо

,

Говорять, що ця функція одержана шляхом підстановки функцій у функцію .

Зауваження:

1. Якщо тотальні, то і функція тотальна.

2. Якщо обчислювані, то і функція обчислювана.

2). Операція примітивної рекурсії:

Функція утворюється із функцій , за допомогою примітивної рекурсії, якщо для всіх натуральних значень маємо: рекурсивний функція арифметичний множення

,

,

Зауваження:

1. Якщо , то - це число.

2. Якщо тотальні, то тотальна.

3. Якщо обчислювані, то і функція обчислювана.

3). Операція мінімізації:

Розглянемо -місну функцію . Про -місну функцію говорять, що вона одержана мінімізацією функції

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

Зауваження:

1. Функція може не бути тотальною, навіть якщо тотальна.

2. Якщо обчислювана, тоді і обчислювана. [2]

Приклади рекурсивних функції:

Наступні функції є рекурсивними:

1) Нульмісні функції ;

2) Двомісна функція додавання +;

3) Двомісна функція множення;

4) Двомісна функція різниці, визначеної наступним чином:

,



5) Одномісні функції та , визначені наступним чином:

,

,

6) Двомісна функція ідентифікації , визначена наступним чином:

,

Рекурсивні функції в програмуванні:

Також популярним є використання рекурсивних функцій в програмуванні на мові C++. Ось їх деякі приклади:

Обрахування факторіалу:

int fac(int n)

{if ( n==0) return 1;

n=n*fac(n-1);

returnn;

}

Функція Акермана:

int Akk( int m, int n)

{ if (!m and n)

return (n+1);

else

if (m and !n)

return Akk(m-1, 1);

return Akk( m-1, Akk(m, n-1));

Функція Фібоначчі:

int fib_rec(int n)

{

if (n==1)or(n==2)

return 1;

return fib_rec(n-1)+fib_rec(n-2);

}

3. Поняття примітивно рекурсивної функції(ПРФ)

Функція називається примітивно рекурсивною, якщо її можна отримати із функцій та ( базові примітивні функції) скінченною кількістю операцій суперпозиції та примітивної рекурсії. [2]

Приклади примітивно рекурсивної функції:

Вкажемо на ряд широко відомих арифметичних функцій, що є примітивно рекурсивними:

1) Функція додавання двох натуральних чисел може бути розглянута в якості примітивно рекурсивної функції двох змінних, одержаних в результаті застосування оператора примітивної рекурсії до функцій , друга з яких виходить підстановкою основної функції в основну функцію :

,

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



,

2) Симетрична різниця (абсолютна величина різниці) двох натуральних чисел може бути розглянута в якості примітивно рекурсивної функції двох змінних, отриманих в результаті застосування наступних підстановок і примітивних рекурсій:

;

;

;

;

;

Властивості:

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

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

Доволі тяжко довести існування і привести приклад загально рекурсивної функції, що не є примітивно рекурсивною. Одним із відомих прикладів є функція Аккермана. Другий приклад загально рекурсивної функції, який не є примітивно рекурсивною, будується діагональним методом Кантора з універсальної функції для множини одномісних примітивно рекурсивних функцій. [3]

4. Поняття частково рекурсивної функції (ЧРФ)

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

Частково рекурсивні функції для деяких значень аргументу можуть бути не визначені, так як оператор мінімізації аргументу не завжди коректно визначений, оскільки функція еф можу бути не рівною нулю ні при яких значеннях аргументів. З точки зору імперативного програмування, результатом часткової рекурсивної функції може бути не тільки число, а й виключення або вихід в нескінченний цикл, відповідний невизначеному значенню. [3]

Функція називається частково рекурсивною, якщо отримана із вказаних функцій застосуванням скінченної кількості операцій суперпозицій, примітивної рекурсії та мінімізації. Всюди визначена частково рекурсивна функція називається загально рекурсивною. Одним з популярних прикладів загально рекурсивної, але не примітивно рекурсивної функції є функція Акермана. [2]

Означення. Частково функція називається частково рекурсивною, якщо існує така скінчена послідовність часткових функцій , що і кожна , або базова, або виходить із деяких попередніх регулярної суперпозицією, примітивною рекурсією або мінімізацією. Ця послідовність називається визначеною послідовністю для . Якщо для усюди визначеної частково рекурсивної функції існує визначена послідовність, що складається тільки з всюди визначених функцій, то називається рекурсивною.

Доказано, що будь-яка всюди визначена частково рекурсивна функція є рекурсивною.

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

Протилежне твердження носить назву тези Черча: Будь-яка обчислювана часткова функція частково рекурсивна.

Історично саме це твердження було першим точним математичним визначенням поняття (алгоритмічно) обчислюваної функції.

Має місце наступна теорема, доказ якої ми опустимо через його громіздкість.

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

Таким чином, теза Тьюрінга еквівалентна тезі Черча. [7]

Обчислюваність по Тьюрінгу частково рекурсивних функцій:

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

Наслідок. Всяка частково рекурсивна функція обчислювана по Тьюрінгу.

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

Теорема. Якщо функція обчислювана по Тьюрінгу, то вона частково рекурсивна.

І вірним є обернена теорема.

Теорема. Функція обчислювана по Тьюрінгу тоді і тільки тоді, коли вона частково рекурсивна.

Функція Акермана:

Функція Акермана - в теорії складності обчислень є найпростішим прикладом обчислювальної функції, що не є примітивно-рекурсивною. Названа на честь автора - Вільгельма Акермана, студента Гільберта.

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

,

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

Доказано, що функція Акермана зростає швидше любої примітивно рекурсивної функції. [8]

Теза Черча:

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

Також виділяють тезу Черча-Тюрінга



Висновок

Самі же рекурсивні функції являють собою клас функцій, введений як уточнення класу обчислювальних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу в математичній логіці, основах математики та кібернетики, як ефективно обчислювальні функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях.[2]



Додатки

Те ще деякі приклади рекурсії:

1) Якщо в пошуковій системі Google ввести запит «рекурсія», то в пошуковій видачі побачите слова «Можливо, ви мали на увазі рекурсія».

2) Відоме висловлення: «Щоб зрозуміти рекурсію, потрібно спочатку зрозуміти рекурсію».

3) Російська народна казка-пісня «У попа була собака…» виявляє приклад рекурсії:

У попа була собака, він її любив.

Вона з'їла шматок м'яса, він її убив.

Убив і закопав,

а на могилі написав: « У попа була собака… (лапки цитат ніколи не закриваються)



Размещено на Allbest.ru