КОНСПЕКТ

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

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