Вычислимость и логика, Булос Дж., Джеффри Р., 1994

Вычислимость и логика, Булос Дж., Джеффри Р., 1994.

   Книга известных американских математиков, являющаяся в настоящее время одной из наиболее известных в США книг по математической логике, выдержавшая там три издания (1974, 1980, 1989 гг.). В ней содержатся начала и некоторые дополнительные главы математической логики, последовательно и строго излагаются классические теоремы о неразрешимости логики предикатов и разрешимости некоторых ее фрагментов, знаменитые теоремы Гёделя о полноте, нестандартные модели и многое другое. Материал дополнен упражнениями.
Для всех, кто интересуется математической логикой, а также информатикой, философией и лингвистикой.




Неразрешимость в контексте диагонализации.
В этой главе мы демонстрируем различные невычислимые функции, подобные рассмотренным в упр. 3.8, 3.9 и 3.10. Мы называем эти функции просто «невычислимыми», а не «не допускающими вычисление на машинах Тьюринга», имея в виду тезис Чёрча, несомненность которого обосновывается в гл. 6-8. Всюду в этой главе термин «функция» обозначает функцию на множестве положительных целых чисел со значениями в том же множестве.

Существование невычислимых функций как таковое доказывается легко и просто, поскольку нам известно (упр. 2.4(d)), что множество всех машин Тьюринга (задаваемых конечными наборами четверок) счетно, тогда как (упр. 2.3) множество всех функций несчетно. Если бы множество всех функций, вычислимых по Тьюрингу, совпадало с множеством всех функций вообще, то это множество должно было бы одновременно быть и не быть счетным. Следовательно, эти два множества различны: первое есть собственное подмножество второго.

ОГЛАВЛЕНИЕ.
Предисловие редактора перевода.
Предисловие.
Предисловие к третьему изданию.
Глава 1. Счетность.
Глава 2. Диагонализация.
Глава 3. Машины Тьюринга.
Глава 4. Невычислимость в контексте проблемы усердного бобра.
Глава 5. Неразрешимость в контексте диагонализации.
Глава 6. Функции, вычислимые на абаке, вычислимы по Тьюрингу.
Глава 7. Рекурсивные функции вычислимы на абаках.
Глава 8. Вычислимые по Тьюрингу функции рекурсивны.
Глава 9. Логика первого порядка: напоминание.
Глава 10. Логика первого порядка неразрешима.
Глава 11. Формализация логики первого порядка: выводы и корректность.
Глава 12. Полнота формализации; компактность.
Глава 13. Теорема Лёвенгейма-Сколема.
Глава 14. Представимость в Q.
Глава 16. Предикаты доказуемости и недоказуемость непротиворечивости.
Глава 17. Нестандартные модели арифметики.
Глава 18. Логика второго порядка.
Глава 19. Об определимой арифметической истине.
Глава 20. Определимость в арифметике и вынуждение.
Глава 21. Разрешимость арифметики со сложением, но без умножения.
Глава 22. Диадическая логика неразрешима: элиминация имен и функциональных символов.
Глава 23. Интерполяционная лемма Крейга.
Глава 24. Два применения леммы Крейга.
Глава 25. Монадическая логика в сравнении с диадической.
Глава 26. Теорема Рамсея.
Глава 27. Доказуемость, рассматриваемая средствами модальной логики.
Глава 28. Неразрешимые предложения.
Глава 29. Нестандартные модели теории 2 нерекурсивны.
Именной указатель.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Вычислимость и логика, Булос Дж., Джеффри Р., 1994 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


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




Хештеги: #учебник по математике :: #математика :: #Булос :: #Джеффри :: #диагонализация :: #вычислимость :: #логика