- •1. Теорема дедукції (з доведенням).
- •2. Проблема повноти, несуперечності, розв'язності числення висловлювань. Незалежність аксіом числення висловлювань.
- •4. Визначення інтерпретації. Формальне визначення істинності.
- •5. Властивості числення предикатів першого порядку (розвязність, повнота, несуперечність)
- •6. Випереджена нормальна форма. Алгоритм приведення до пнф. Сколемівська стандартна та клаузальна форми формули логіки предикатів першого порядку. Алгоритм приведення до ссф.
- •7. Універсум Ербрана. Ербранова база.
- •8. Алгоритм уніфікації.
- •9. Формальні аксіоматичні теорії. Основні поняття.
- •10. Інтерпретації та моделі формальної аксіоматичної теорії.
- •11. Дослідження властивостей формальних аксиоматичних теорій.
- •13. Машини натуральнозначних регістрів (машини довільного доступу).
- •14. Машини Тьюрінга. Функції, які обчислювані за Тьюрінгом.
- •15. Композиція, ітерація мт. Поняття багатострічкової мт. Порівняння часу роботи комп’ютерів і мт.
- •16. Нормальні алгоритми Маркова. Функції, які обчислювані за Марковим.
- •17. Елементарні функції. Операції суперпозиції, примітивної рекурсії, мінімізації.
- •18. Поняття прф, рф, чрф. Приклади.
- •19. Елементарні властивості прф. Теореми 1, 2 (з доведенням).
- •20. Елементарні властивості прф. Теореми 3, 4 (з доведенням).
- •21. Теза Черча і його значення.
- •22. Канторові нумерації. Теорема про властивості функцій c(X,y), l(n), r(n).
- •23. Алгоритмічно нерозв’язні проблеми. Приклади.
15. Композиція, ітерація мт. Поняття багатострічкової мт. Порівняння часу роботи комп’ютерів і мт.
Композиция: Т1, Т2; f1(p)=f2(f1(p)) начальное состояние Т будет началом состояния машины Т1. Заключительным состоянием Т будет заключительное состояние Т2. Заключительное Т1=начальное Т2. Команды обеих программ объединяются в одну программу.
Итерация: пусть q’ – некоторое заключительное состояние машины Т, а q” – какое-либо состояние машины Т, не являющееся заключительным. Заменим повсюду в программе П машины Т символ q’ на q”. Получим программу, определяющую машину Т’(q’, q”). Машина Т’ называется итерацией машины Т по паре состояний q’, q”.
Многоленточная МТ - состоит из конечного управления с k ленточными головками, по одной на каждой ленте.
Каждая лента бесконечна в обоих направлениях. При одном движении, зависящем от состояния конечного управления и сканируемого символа каждой из ленточных головок, машина может:
1) изменить состояние;
2) напечатать новый символ на каждой из сканируемых ячеек;
3) передвинуть каждую из ее ленточных головок независимо друг от друга на одну ячейку влево, вправо или оставить ее на том же месте.
Сравнение времени работы:
Теорема: Пусть компьютер обладает следующим свойством: 1) У него есть только инструкция, увеличивающая максимальную длину слова не более, чем на 1. 2)у него есть только инструкции, которая многоленточная МТ может выполнить на словах длиной к за 0(к2) шагов или за меньше. Тогда выполнение n шагов компьютера можно проимитировать на одноленточной МТ не более, чем за 0(n6) шагов.
16. Нормальні алгоритми Маркова. Функції, які обчислювані за Марковим.
НА в алфавите Т это упорядоченная последовательность подстановок. Для определения НАМ вводится произвольный алфавит - конечное непустое множество символов, при помощи которых описывается алгоритм и данные. В алфавит также включается пустой символ, который обозначается греческой буквой . Схемой нормального алгоритма называется конечный упорядоченный набор формул подстановки, каждая из которых может быть простой или заключительной.-простая,- заключительная подстановка, где- слова принадлежащие Т.
Конечная упорядоченная последовательность подстановок называется схемой НА. НА создает отображение Т*->Т*. Пусть слово х; А(х) – результат работы НА над словом х. Слововходит в слово, еслислова Е1 и Е2(возможно пустые) такие что:. П:=abcbcaa;=bc; 1)bc->d addcaa; 2) bc->.d adbcaa
Опишем работу НА. Пусть задано слово х; х0=х. Пусть Хn получено после применения n этапов НА. Опишем (n+1) этап. Ищем первую по порядку подстановку , такую что- подслово Хn. Применяем эту подстановку к Хn, то есть заменяем в Хn первое вхождение на. Полученное слово обозначаем Хn+1. Если применяемая подстановка не является заключительной, то переходим на (n+2) этап. Результат: А(х)= Хn+1. Если же ни одна из подстановок НА не применима к Хn, то алгоритм заканчивает работу и результат А(х)= Хn. НА называется НА над алфавитом Т, если он является нормальным алгоритмом в некотором расширенном алфавите Т\>=Т. Он задает изображение Т*->Т* использую а процессе обработки слов в алфавите Т вспомогательные символы с алфавита Т\. НА вычисляет математическую функцию если он каждое слово х1…xk переводит в слово f(x1…xk) если и значение его не определено, если. Функция называется вычислимой по Маркову, если существует НА, который ее вычисляет.