Кибернетика. Вычислимое и невычислимое

Автор(ы):Манин Ю. И.
19.01.2012
Год изд.:1980
Описание: Использование электронно-вычислительной техники связано с возможностью алгоритмического решения задач и эффективного вычисления функций. Между тем в математике широко используются функции, заданные неэффективными определениями. Столь же часты доказательства разрешимости задач, например оптимизации, не сопровождаемые алгоритмами их решения. В действительности класс задач, доступных классическим средствам, в некотором трудно уточняемом смысле строго шире класса задач, решаемых алгоритмически. Книга посвящена прояснению смысла этого утверждения, изложению математических моделей вычислимости, а также некоторых недавних результатов, которые используют понятия теории вычислимости, но выходят за ее пределы. В ней обсуждаются проблемы оценки сложности вычислений и алгоритмов. Книга будет полезна широкому кругу специалистов, занимающихся проблемами машинного перевода, искусственного интеллекта, общего использования ЭВМ.
Оглавление:
Кибернетика. Вычислимое и невычислимое — обложка книги.
Предисловие [3]
Введение [5]
Глава I. Рекурсивные функции и алгоритмы [16]
  1. Интуитивная вычислимость [16]
  2. Частично рекурсивные функции [20]
  3. Образцы рекурсивности [25]
  4. Перечислимые и разрешимые множества [29]
  5. Элементы рекурсивной геометрии [39]
  6. Конструктивные объекты и алгоритмы [44]
Глава II. Диофантовы множества и алгоритмическая неразрешимость [46]
  1. Основные результаты [46]
  2. План доказательства. [49]
  3. Перечислимые множества являются D-множествами [51]
  4. Редукция [53]
  5. Конструкция специального диофантова множества [56]
  6. График экспоненты диофантов [61]
  7. Графики факториала и биномиальных коэффициентов диофантовы [62]
  8. Дополнения [64]
Глава III. Сложность и случайность [65]
  1. Версальные семейства [65]
  2. Сложность по Колмогорову [68]
  3. Сложность и случайность [73]
Глава IV. Формальные языки и вычислимость [74]
  1. Арифметика синтаксиса [74]
  2. Синтаксический анализ [80]
  3. Перечислимость выводимых формул [85]
Глава V. Теорема Геделя [87]
  1. Принцип неполноты [87]
  2. Неперечислимость истинных формул [88]
  3. О длине доказательств [91]
  4. Арифметическая иерархия [93]
  5. Продуктивность арифметической истины [96]
  6. Вычислимые функции с очень быстрым ростом [99]
Глава VI. Рекурсивные группы [101]
  1. Основной результат и его следствия [101]
  2. Свободные произведения и HNN-расширения [104]
  3. Вложения в группы с двумя образующими [107]
  4. Хорошие подгруппы [108]
  5 Ограниченные системы образующих [111]
  6. Окончание доказательства [116]
Список литературы [123]
Именной указатель [125]
Предметный указатель [125]
Формат: djvu
Размер:2859147 байт
Язык:РУС
Рейтинг: 261 Рейтинг
Открыть: