| Оглавление | 3
|
| Предисловие | 7
|
| Введение. Сигнифика | 9
|
| 1. Буква | 9
|
| 2. Алфавит | 11
|
| 3. Слово | 12
|
| 4. Конструктивный объект | 19
|
| Глава I. Общая теория алгоритмов | 23
|
| § 1. Предписания | 24
|
| § 2. Перечислимые множества | 30
|
| 1. Перечислимое множество | 30
|
| 2. Операции над перечислимыми множествами | 31
|
| 3. Существование не перечислимого множества натуральных чисел | 33
|
| 4*. Относительная перечислимость | 36
|
| § 3. Алгоритмы | 38
|
| 1. Алгоритм | 38
|
| 2. Алгоритмы и перечислимые множества | 42
|
| 3. Каноническое задание (разложение) программы алгоритма | 43
|
| § 4. Вычислимые функции | 46
|
| 1. Вычислимая функция | 46
|
| 2. Существование не вычислимой всюду определенной функции типа N ( N | 49
|
| 3. Вычислимые функции и алгоритмы | 50
|
| 4. Вычислимые функции и перечислимые множества | 51
|
| § 5. Разрешимые множества | 54
|
| 1. Разрешимое множество | 54
|
| 2. Операции над разрешимыми множествами | 56
|
| 3. Вычислимые функции и разрешимые множества | 58
|
| 4. Множество, разрешимое относительно перечислимого надмножества | 60
|
| 5. Разрешимые и перечислимые множества | 61
|
| 6*. Разрешимые и относительно перечислимые множества | 62
|
| Глава II. Машины Тьюринга | 65
|
| § 1. Тьюринговы алгоритмы | 65
|
| 1. Тьюрингов алгоритм | 65
|
| 2. Вычисление «арифметических» функций на машинах Тьюринга | 76
|
| 3. Принцип тьюрингизации | 78
|
| § 2. Кодирование тьюринговых алгоритмов | 81
|
| 1. Кодирование тьюринговых алгоритмов | 81
|
| 2. Пример не перечислимого множества натуральных чисел | 83
|
| 3. Универсальная машина Тьюринга | 84
|
| § 3. Алгоритмически неразрешимые проблемы | 87
|
| 1. Алгоритмически неразрешимые проблемы | 87
|
| 2. Существование перечислимого не разрешимого множества | 91
|
| 3. Нераспознаваемые свойства | 92
|
| ДОПОЛНЕНИЯ | 99
|
| Глава III. Нормальные алгорифмы | 101
|
| Глава IV. Рекурсивные функции | 105
|
| Глава V. Универсальная функция | 113
|
| Глава VI. Нумерационная теория алгоритмов | 117
|
| § 1. Основные понятия | 117
|
| § 2. Нумерации класса и наследственные нумерации | 122
|
| ПРИЛОЖЕНИЯ | 129
|
| 1. Две теоремы о натуральных числах | 131
|
| 2. Три определения | 133
|
| 3. Программа | 135
|
| Примечания | 143
|
| Упомянутая литература | 145
|
| Указатель терминов | 146
|
| Указатель обозначений 150 | 152
|
Шиханович Юрий Александрович Кандидат педагогических наук. В 1955 г. окончил механико-математический факультет МГУ имени М. В. Ломоносова. В 1955–1957 гг. преподавал в Московском авиационном институте (МАИ) и Московском энергетическом институте (МЭИ), работал в Лаборатории электромоделирования АН СССР. В 1960–1968 гг. преподавал математику на Отделении структурной и прикладной лингвистики филологического факультета МГУ. В 1968–1972 гг. работал инженером в Специальном конструкторском бюро биофизической аппаратуры и электронных машин, в 1975–1983 гг. — редактором в журнале «Квант». С 1995 по 2011 гг. преподавал в Российском государственном гуманитарном университете (РГГУ) математику студентам-лингвистам.
Ю. А. Шиханович стал одним из тех, кто вел в СССР пропаганду и преподавание современной математики. Он был редактором книги В. А. Успенского «Лекции о вычислимых функциях», изданной в серии «Математическая логика и основания математики», и, по свидетельству автора, «без его помощи эта книга, вероятно, не была бы написана». Вместе с Г. Н. Поваровым он перевел на русский язык книгу коллектива французских математиков, объединившихся под псевдонимом Н. Бурбаки: «Начала математики: Основные структуры анализа». В 1965 г. им была опубликована книга «Введение в современную математику: Начальные понятия» (в 1967 г. книга была издана в Японии). В 2005 г. вышла книга «Введение в математику» — переработанное и дополненное переиздание книги 1965 г. Он также опубликовал следующие книги: «Группы, кольца, решетки» (книга по алгебре) (2006), «Минимум по теории алгоритмов для нематематиков» (2009), «Начальные главы математического анализа в полуформальном изложении» (2010), «Логические и математические исчисления» (2011).
