Автор: Катленд Н. Название: Вычислимость. Введение в теорию рекурсивных функций Издательство: М.: Мир Год: 1983 Язык: Русский, пер. с англ. Формат: pdf, djvu Размер: 13,9 mb Страниц: 256 с., ил.
Предлагаемая читателю книга известного английского математика представляет собой элементарное введение в область, служащую теоретической основой программирования и различных приложений теории алгоритмов в математике и логике, теории формальных языков, информационных системах и системах управления, биологии и других науках.
При небольшом объеме автор сумел охватить обширный материал, представив в наглядном виде даже весьма нетривиальные результаты (например, теорему Блюма об ускорении). Наряду с собственно теорией рекурсивных функций излагаются ее основные приложения в формальной арифметике (теорема Гёделя о неполноте) и в математической логике (теорема Чёрча о неразрешимости узкого исчисления предикатов).
Книга рассчитана на широкий круг читателей, включая старшеклассников, интересующихся перечисленными областями. Формально для ее чтения не требуется специальной подготовки, необходимые сведения из теории множеств и математической логики приводятся во введении и основном тексте.