Лекція 4 Обчислення
Існує клас завдань, математичні моделі та алгоритми, рішення яких зручно представляти у вигляді формальних обчислень. Поряд з машиною станів та функціями, що обчислюються алгоритмом, «алгоритм-обчислення» є третім видом уточнення поняття алгоритму. Технологія проектування програм, заснована на формальних обчисленнях, має певну специфіку, яка і розглядається в цій лекції.
1. Обчислення та формальні системи
Змістовно літочислення задає конструктивний спосіб породження слів деякої мови. Наприклад, обчислення кінцевих різниць Ньютона дає можливість породжувати (обчислювати) для деякого правильного виразу формул з диференціалами всі еквівалентні вирази, задані правилами тотожних перетворень. Обчислення висловлювань дозволяє конструктивно породжувати всі можливі логічні закони у вигляді тотожно істинних висловлювань. Обчислення предикатів дозволяє будувати формальні теорії у вигляді системи формул, які є істинними у вибраній інтерпретації.
1.1. Обчислення Туе(Норвезький математик Туе в 1912 р. сформулював найбільш загальну модель обчислення)
-правила підстановок, де
ІТ дозволяє конструктивно вирішити дві основні завдання – завдання породження та завдання розпізнавання слів, що входять до ІТ.
а)Завдання породження еквівалентних слів у ІТ.
Задано слово
б)Завдання розпізнавання еквівалентності пари слів
ZW(еквівалентні), якщо зZвиводиться словоWза правиламиР
Порядок застосування правил під час вирішення завдань не регламентований і здійснюється відповідно до дерева повного перебору.
Приклад 1: , де – порожня множина. Слово
Слово «аbа» у цьому ІТ виводиться кількома шляхами (послідовностями застосування правил).
1.2. Обчислення Ербрана - Геделя. (7) (ІЕГ)
У 1934 р. Ербран і незалежно від нього Гедель як уточнення поняття алгоритму побудували формальне обчислення для обчислення всіх можливих функцій на безлічі натуральних чисел.
, де
б)ППФ- правильно побудовані формули, які складаються з термів, побудованих за правилами, прийнятими в математиці, і мають вигляд -
в)
Приклад 2.Задано системуППФ.
1. .
2. .
Обчислити функцію
Застосування
1.
2.
Якщо
3.
4. ,
то
Алгоритм у вигляді обчислення Ербрана - Геделя не визначає порядок застосування правил підстановок і не визначає навіть схему підстановок, як це заведено в рекурсивних функціях Кліні. Як і в будь-яких визначеннях поняття алгоритму (МТ, НАМ, РФ) формалізм ІЕГ побудований тільки наперетворення послідовності символів і не вимагає залучення жодної семантики.
2. Формальні системи (ФС)
Формальна система є обчислення, де виділено підмножина формул (слів), яке оголошено спочатку виведеним. Ці формули називаютьсяаксіомами.
а)ППФ– правильно побудовані формули в алфавітіА,
б)
в) - аксіоми є підмножиноюППФ.
г)ПВ- правила виду, що означає, із сукупностіППФвиводитьсяППФ. У будь-якій ФС безліч формул ППФВ виводяться з ППФА за допомогою правил ПВ. При цьому ППФВ>ППФ>, – називаються виведеними формулами.
Наприклад, обчислення висловлювань є формальною системою, деППФє формули, побудовані з імен змінних, знаків операцій ( – кон'юнкція, – диз'юнкція, – заперечення, – імплікація) та дужок. Виділяються ППФ, які оголошуються аксіомами та єдине правило виведення «modus ponens». У вирахуванні висловлювань породжуються тільки такіППФ, які можуть інтерпретуватися як тотожно істинні формули (тавтології) і вони.
3. Формальні граматики(ФГ)
Обчислення у виглядіФСзапропоновано американським математиком Хомським (1953) спочатку для вирішення проблем структурної лінгвістики, а далі описи формальних мов програмування.
ФГ=, деА
-допоміжний алфавіт,S- єдина аксіома,Р -правила виду
ФГпороджує характерну мову у вигляді підмножини слів
