Элементы математической логики. Алгоритмы и рекурсивные функции

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ. АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ. Учебно-методическое пособие......Page 1 Содержание......Page 3 Введение......Page 4 1.1. Машина Тьюринга......Page 5 1.2. Произведение......Page 6 1.4. Разветвления с циклом......Page 7 1.5. Вычислимые по Тьюрингу-Посту функции......Page 8 1.6. Неразрешимые множества......Page 12 2.1. Определение частично-рекурсивных функций......Page 14 2.2. Нумерации кортежей чисел......Page 18 3.1. Совпадение классов ч.р.ф. и функций, вычислимых по Тьюрингу......Page 19 3.2. Рекурсивные и рекурсивно-перечислимые множества......Page 21 4. Теорема Поста-Маркова о конечно-определенной полугруппе с неразрешимой проблемой равенства......Page 24 4.2. Теорема Поста-Маркова......Page 25 Список литературы......Page 28