Лекции по математической логике и теории алгоритмов. Вычислимые функции

Автор(ы):Верещагин Н. К.
06.10.2007
Год изд.:1999
Описание: Книга написана по материалам лекций и семинаров, читавшихся на мехмате МГУ. В ней рассказывается об основных понятиях теории вычислимых функций (вычислимость, разрешимость, перичислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степень неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции). Изложение рассчитано на учеников математических школ, студентов-математиков и др.
Оглавление:
Лекции по математической логике и теории алгоритмов. Вычислимые функции — обложка книги.
Предисловие [б]
1. Вычислимость, разрешимость и перечислимость [8]
  1.1. Вычислимые функции [8]
  1.2. Разрешимые множества [9]
  1.3. Перечислимые множества [10]
  1.4. Перечислимые и разрешимые множества [13]
  1.5. Перечислимость и вычислимость [14]
2. Универсальные функции и неразрешимость [17]
  2.1. Универсальные функции [17]
  2.2. Диагональная конструкция [18]
  2.3. Перечислимое неразрешимое множество [20]
  2.4. Перечислимые неотделимые множества [21]
  2.5. Простые множества: конструкция Поста [22]
3. Нумерации и операции [24]
  3.1. Главные универсальные функции [24]
  3.2. Вычислимые последовательности функций [28]
  3.3. Главные универсальные множества [29]
4. Свойства главных нумераций [32]
  4.1. Множества номеров [32]
  4.2. Новые номера старых функций [36]
  4.3. Изоморфизм главных нумераций [39]
  4.4. Перечислимые свойства функций [41]
5. Теорема о неподвижной точке [45]
  5.1. Неподвижная точка и отношения эквивалентности [45]
  5.2. Программа, печатающая свой текст [47]
  5.3. Системный трюк: ещё одно доказательство [50]
  5.4. Несколько замечаний [53]
6. m-сводимость и свойства перечислимых множеств [59]
  6.1. m-сводимость [59]
  6.2. m-полные множества [60]
  6.3. m-полнота и эффективная неперечислимость [62]
  6.4. Изоморфизм m-полных множеств [66]
  6.5. Продуктивные множества [68]
  6.6. Пары неотделимых множеств [72]
7. Вычисления с оракулом [76]
  7.1. Машины с оракулом [76]
  7.2. Эквивалентное описание [79]
  7.3. Релятивизация [81]
  7.4. О'-вычисления [85]
  7.5. Несравнимые множества [88]
  7.6. Теорема Мучника-Фридберга: схема конструкции [92]
  7.7. Теорема Мучника-Фридберга: выигрышные условия [94]
  7.8. Теорема Мучника-Фридберга: метод приоритета [96]
8. Арифметическая иерархия [98]
  8.1. Классы (?) и (?) [98]
  8.2. Универсальные множества в (?) и (?) [101]
  8.3. Операция скачка [102]
  8.4. Классификация множеств в иерархии [108]
9. Машины Тьюринга [112]
  9.1. Зачем нужны простые вычислительные модели? [112]
  9.2. Машины Тьюринга: определение [113]
  9.3. Машины Тьюринга: обсуждение [115]
  9.4. Ассоциативные исчисления [118]
  9.5. Моделирование машин Тьюринга [120]
  9.6. Двусторонние исчисления [124]
  9.7. Полугруппы, образующие и соотношения [125]
10. Арифметичность вычислимых функций [129]
  10.1. Программы с конечным числом переменных [129]
  10.2. Машины Тьюринга и программы [132]
  10.3. Арифметичность вычислимых функций [134]
  10.4. Теоремы Тарского и Гёделя [138]
  10.5. Прямое доказательство теорем Тарского и Гёделя [140]
  10.6. Арифметическая иерархия и перемены кванторов [142]
11. Рекурсивные функции [145]
  11.1. Примитивно рекурсивные функции [145]
  11.2. Примеры примитивно рекурсивных функций [146]
  11.3. Примитивно рекурсивные множества [147]
  11.4. Другие виды рекурсии [150]
  11.5. Машины Тьюринга и рекурсивные функции [153]
  11.6. Частично рекурсивные функции [155]
  11.7. Вычислимость с оракулом [159]
  11.8. Оценки скорости роста. Функция Аккермана [162]
Литература [166]
Предметный указатель [168]
Указатель имён [174]
Формат: djvu
Размер:475304 байт
Язык:RUS
Рейтинг: 156 Рейтинг
Открыть: