Математическая логика и теория алгоритмов

10. Связь между алгоритмами Тьюринга и нормальными алгоритмами. 11. Основная гипотеза теории алгоритмов (принцип нормализа­ ции или тезис Чёрча). Доказуема ли эта гипотеза? 12. Проблема алгоритмической неразрешимости. 13. Знаете ли вы алгоритмически разрешимые массовые про­ блемы? 14. Примеры алгоритмически неразрешимых массовых проблем. 15. Сведения любого преобразования слов в алфавите к вычис­ лению значений целочисленных функций. 16. Примитивно-рекурсивные и общерекурсивные функции. 17. Примитивно-рекурсивность некоторых функций. Вычисле­ ние значений примитивно-рекурсивных функций. 18. Частично рекурсивные функции, их связь с вычислимостью по Маркову и Тьюрингу. 19. Какие вы знаете вычислительные модели? 20. Ламбда-исчисление. Синтаксис ламбда-исчисления. 21. Р-преобразования в ламбда-исчислении. § 20. Упражнения 1. Применим ли нормальный алгоритм * 11 -> 1 < 'J' Ф Л —> 1 к слову: а) F=l l l ; б) Р=**; в) Р=11*; г) Если «да», то указать результат применения. 2. Применим ли нормальный алгоритм В = - 1->в11 265