Предисловие § 1. Постановка задачи § 2. Начальные понятия теории алгоритмов и их применения § 3. Простейшие критерии неполноты § 4. Язык арифметики § 5. Три аксиомы теории алгоритмов Приложения A. Синтаксическая и семантическая формулировки теоремы о неполноте Б. Арифметические множества и теорема Тарского о неариф-метичности множества истинных формул языка арифметики B. Язык адресных программ, расширенный арифметический язык и аксиома арифметичиости B.I. Язык адресных программ В.2. Расширенный арифметический язык В.3. Выразимость адресно вычислимых функций в расширенном арифметическом языке В.4. Сведение расширенного арифметического языка к обычному В.5. Первый способ построения арифметического кодирования --- способ Гёделя 8.6. Второй способ построения арифметического кодирования --- способ Смальяна Г. Языки, связанные с ассоциативными исчислениями Д. Исторические замечания Е. Упражнения
![]() Доктор физико-математических наук, профессор. Заведующий кафедрой математической логики и теории алгоритмов механико-математического факультета Московского государственного университета имени М. В. Ломоносова. Окончил механико-математический факультет МГУ в 1952 г.; ученик великого математика А. Н. Колмогорова. Один из организаторов отделения структурной и прикладной лингвистики (ныне отделение теоретической и прикладной лингвистики) филологического факультета МГУ. Инициатор реформы лингвистического образования в России. Автор научных работ в области теории алгоритмов и лингвистики, а также художественных произведений в жанре мемуарной прозы. Подготовил 25 кандидатов и 4 докторов наук. За книгу «Апология математики» получил главный приз премии «Просветитель» в 2010 году в области естественных и точных наук.
|