КОНСПЕКТ

за курса по Теоретични основи на функционалното програмиране, четен през летния семестър на 2002/2003 уч. година

  1. Частични функции и предикати в дадено множество. Композиция, разклонение и итерация.
  2. Московакисово разширение на множество. Абсолютна проста изчислимост и проста изчислимост на функция относно дадено множество от функции.
  3. Кодиране на естествени числа и на крайни редици в Московакисово разширение.
  4. Представяне на частично рекурсивните функции чрез абсолютно просто изчислими функции в произволно Московакисово разширение.
  5. Абсолютна проста изчислимост на частично рекурсивните функции относно функциите прибавяне и изваждане на единица и предиката, разпознаващ нулата.
  6. Абсолютна проста изчислимост и проста изчислимост на частично рекурсивни функции относно функцията изваждане на единица и предиката, разпознаващ нулата.
  7. Разрешимост и полуразрешимост на множество относно дадено множество от функции.
  8. Пример за това, че не винаги относителната полуразрешимост на множество се запазва при образуване на допълнение и не винаги от нея следва относителна разрешимост.
  9. Примери за това, че не винаги от относителната полуразрешимост на едно множество и на неговото допълнение следва относителната разрешимост на това множество, и затова, че може една функция да е абсолютно просто изчислима относно дадено множество от функции без множеството на стойностите й да е полуразрешимо относно него.
  10. Пример за това, че не винаги относителната полуразрешимост на множество се запазва при образуване на обединение.
  11. Итерацията като минимална неподвижна точка.
  12. Абсолютно просто изчислими оператори.
  13. Привеждане на рекурсията към каноничен вид.
  14. Тъждества, чрез които могат да се пресмятат рекурсивно определени функции.
  15. Итеративен метод за преснятане на рекурсивно определени функции.
  16. Конструиране на най-малкото решение на система от каноничен вид.
  17. Проста изчислимост на рекурсивно определените функции.
  18. Действия с функции, зависещи от параметри.
  19. Универсални абсолютно просто изчислими функции.
  20. Втора теорема за рекурсия и теорема на Райс-Успенски в теорията на просто изчислимите функции.