URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ.
Id: 2414
 
899 руб.

Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ.

1983. 256 с. Мягкая обложка. Букинист. Состояние: 4+. Есть погашенная библиотечная печать.

 Аннотация

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

Для математиков, специалистов по ЭВМ, желающих ознакомиться с теоретическими основами машинной математики.


 ОГЛАВЛЕНИЕ

Предисловие редактора перевода

Предисловие

Введение

Предварительные замечания и обозначения

1. Множества

2. Функции

3. Отношения и предикаты

4. Логические обозначения

5. Ссылки

Глава 1. Вычислимые функции

1. Алгоритмы или вычислительные процедуры

2. Машина с неограниченными регистрами

3. МНР-вычислимые функции

4. Разрешимые предикаты и проблемы

5. Вычислимость на других областях

Глава 2. Порождение вычислимых функций

Основные функции. Соединение программ

Подстановка

Рекурсия

Минимизация

Глава 3. Другие подходы к вычислимости: тезис Чёрча

1. Другие подходы к вычислимости

2. Частично рекурсивные функции (Гёдель ---Клини)

3. Отступление: примитивно рекурсивные функции

4. Тьюрингова вычислимость

5. Системы обработки символов Поста и Маркова

6. Вычислимость на областях, отличных от N

7. Тезис Чёрча

Глава 4. Нумерация вычислимых функций

1. Нумерация программ

2. Нумерация вычислимых функций,

3. Обсуждение: диагональный метод,

4. s-m-я-теорема

Глава 5. Универсальные программы

1. Универсальные функции и универсальные программы

2. Два приложения универсальной программы

3. Эффективные операции на вычислимых функциях

Глава 6. Разрешимость, неразрешимость и частичная разрешимость

1. Неразрешимые проблемы в теории вычислимости

2. Проблема слов в теории групп

3. Диофантовы уравнения

4. Алгоритм Штурма

5. Математическая логика

6. Частично разрешимые предикаты

Глава 7. Рекурсивные и рекурсивно перечислимые множества

1. Рекурсивные множества

2. Рекурсивно перечислимые множества

3. Продуктивные и креативные множества

4. Простые множества

Глава 8. Арифметика и теорема Гёделя о неполноте

1. Формальная арифметика

2. Неполнота

3. Теорема неполноты Гёделя

4. Неразрешимость

Глава 9. Сводимости и степени

1. Многозначная сводимость

2. Степени

3. m-полные р. п. множества

4. Относительная вычислимость

5. Сводимость по Тьюрингу и степени Тьюринга

Глава 10. Эффективные операции на множестве частичных функций

1. Рекурсивные операторы

2. Эффективные операции над вычислимыми функциями

3. Первая теорема о рекурсии

4. Приложение к семантике языков программирования

Глава 11. Вторая теорема о рекурсии

1. Вторая теорема о рекурсии

2. Обсуждение

3. Теорема Майхилла

Глава 12. Сложность вычисления

1. Сложность и меры сложности

2. Теорема об ускорении

3. Классы сложности

4. Элементарные функции

Глава 13. Пути дальнейшего изучения

Словарь обозначений

Список литературы

 
© URSS 2016.

Информация о Продавце