Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

является основой создания функционального программирования и таких языков как Lisp, SML, Scheme, Haskell и других языков функционального программирования. Вопросы и темы для самопроверки 1. Интуитивное понятие алгоритма, его свойства. 2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные в данном алфавите алгоритмы. 3. Нормальный алгоритм (алгоритм А.А.Маркова), его задание, примеры. 4. Функции вычислимые и частично вычислимые по Маркову. 5. Замыкание, распространение нормального алгоритма. 6. Операции над нормальными алгоритмами: композиция, соединение, разветвление, повторение. 7. Машина Тьюринга, общее описание. 8. Задание машины Тьюринга, примеры. 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу. 10. Связь между алгоритмами Тьюринга и нормальными алгоритмами. 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча). Доказуема ли эта гипотеза? 12. Проблема алгоритмической неразрешимости. 13. Знаете ли вы алгоритмически разрешимые массовые проблемы? 14. Примеры алгоритмически неразрешимых массовых проблем. 15. Сведения любого преобразования слов в алфавите к вычислению значений целочисленных функций. 16. Примитивно рекурсивные и обш,ерекурсивные функции. 17. Примитивно рекурсивность некоторых функций. Вычисление значений примитивно рекурсивных функций. 18. Частично рекурсивные функции, их связь с вычислимостью по Маркову и Тьюрингу. 19. Какие вы знаете вычислительные модели? 20. Ламбда-исчисление. Синтаксис ламбда-исчисления. 21. уб-преобразования в ламбда-исчислении. Если действовать не будешь, ни к чему ума палата. Ш. Руставели (Витязь в тигровой шкуре) Упражнения 1. Применим ли нормальный алгоритм 178