Вычислимость, Введение в теорию рекурсивных функций, Катленд H., 1983

Вычислимость, Введение в теорию рекурсивных функций, Катленд H., 1983.

   Книга известного английского математика, охватывающая основные вопросы теории вычислимых функций и ее приложений: сложность вычислений и алгоритмов, теоремы Гёделя о неполноте и Чёрча о неразрешимости, семантику языков программирования. Изложение замкнутое, методически продуманное, имеется много упражнений.
Для математиков, специалистов по ЭВМ, желающих ознакомиться с теоретическими основами машинной математики.




Алгоритмы или вычислительные процедуры.
Обучаясь арифметике в начальной школе, мы познакомились со сложением и умножением двух чисел. Нам в явной форме не говорили, что у любой пары чисел существуют произведение и сумма, а указали способы или правила их нахождения. Такие способы или правила являются примерами алгоритмов, или вычислительных (эффективных) процедур. Их применение не требует изобретательности или сообразительности, ученику необходимо было только следовать инструкциям учителя.

Более общо, алгоритм, или эффективная процедура, — это механическое правило или автоматический метод, или программа для выполнения некоторых математических операций. Приведем еще несколько примеров операций, для которых легко можно указать алгоритмы:
(а) по данному n найти n-е простое число;
(b) дифференцирование полинома;
(c) нахождение наибольшего общего делителя двух натуральных чисел (алгоритм Евклида);
(d) для двух данных чисел х, y решить, является ли х кратным у.

Оглавление.
Предисловие редактора перевода.
Предисловие.
Введение. Предварительные замечания и обозначения.
1. Множества.
2. Функции.
3. Отношения и предикаты.
4. Логические обозначения.
5. Ссылки.
Глава 1. Вычислимые функции.
1. Алгоритмы или вычислительные процедуры.
2. Машина с неограниченными регистрами.
3. МНР-вычислимые функции.
4. Разрешимые предикаты и проблемы.
5. Вычислимость на других областях.
Глава 2. Порождение вычислимых функций.
1. Основные функции.
2. Соединение программ.
3. Подстановка.
4. Рекурсия.
5. Минимизация.
Глава 3. Другие подходы к вычислимости: тезис Чёрча.
1. Другие подходы к вычислимости.
2. Частично рекурсивные функции (Гёдель — Клини).
3. Отступление: примитивно рекурсивные функции.
4. Тьюрингова вычислимость.
5. Системы обработки символов Поста и Маркова.
6. Вычислимость на областях, отличных от N.
7. Тезис Чёрча.
Глава 4. Нумерация вычислимых функций.
1. Нумерация программ.
2. Нумерация вычислимых функций.
3. Обсуждение: диагональный метод.
4. s-m-n-теорема.
Глава 5. Универсальные программы.
1. Универсальные функции и универсальные программы.
2. Два приложения универсальной программы.
3. Эффективные операции на вычислимых функциях.
Приложение. Вычислимость функции σn.
Глава 6. Разрешимость, неразрешимость и частичная разрешимость.
1. Неразрешимые проблемы в теории вычислимости.
2. Проблема слов в теории групп.
3. Диофантовы уравнения.
4. Алгоритм Штурма.
5. Математическая логика.
6. Частично разрешимые предикаты.
Глава 7. Рекурсивные и рекурсивно перечислимые множества.
1. Рекурсивные множества.
2. Рекурсивно перечислимые множества.
3. Продуктивные и креативные множества.
4. Простые множества.
Глава 8. Арифметика и теорема Гёделя о неполноте.
1. Формальная арифметика.
2. Неполнота.
3. Теорема неполноты Гёделя.
4. Неразрешимость.
Глава 9. Сводимости и степени.
1. Многозначная сводимость.
2. Степени.
3. m-полные p, n, множества.
4. Относительная вычислимость.
5. Сводимость по Тьюрингу и степени Тьюринга.
Глава 10. Эффективные операции на множестве частичных функций.
1. Рекурсивные операторы.
2. Эффективные операции над вычислимыми функциями.
3. Первая теорема о рекурсии.
4. Приложение к семантике языков программирования.
Глава 11. Вторая теорема о рекурсии.
1. Вторая теорема о рекурсии.
2. Обсуждение.
3. Теорема Майхилла.
Глава 12. Сложность вычисления.
1. Сложность и меры сложности.
2. Теорема об ускорении.
3. Классы сложности.
4. Элементарные функции.
Глава 13. Пути дальнейшего изучения.
Словарь обозначений.
Список литературы.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Вычислимость, Введение в теорию рекурсивных функций, Катленд H., 1983 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать файл № 1 - pdf
Скачать файл № 2 - djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - djvu - Яндекс.Диск.

Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Катленд