- •Введение
- •Глава 1
- •§ 1. «Алгоритмические джунгли»
- •§ 2. Исходные данные и результаты. Массовость алгоритма
- •§ 4. Понятность алгоритма
- •§ 5. Рекурсивные определения
- •§ 6. Определенность алгоритма
- •§ 1. Роль алгоритмов в науке и технике
- •§ 7. Выводы
- •Глава 2 создание алгоритмов
- •§ 2. Как возникают алгоритмы
- •§ 3. Алгоритмы в математике
- •§ 4. Алгоритм Евклида
- •§ 5. Решето Эрагосфена
- •§ 6. Алгоритм разложения на простые множители. Определение наименьшего кратного двух чисел
- •§ 7. Распознавание алгебраического тождества
- •§ 8. Задачи на построение алгоритмов
- •Глава 3 кризис математики в начале XX века
- •§ 1. Арифметизация математики
- •§ 2. Теория множеств
- •§ 3. Кардинальные числа
- •§ 4. Антиномии
- •§ 5. Выводы из антиномий
- •Глава 4 логические теории алгоритмов
- •§ 1. Рекурсивные функции
- •§ 2. Машины Тьюринга
- •§ 3. Нормальные алгоритмы Маркова
- •§ 4. Эквивалентность описанных теорий
- •Глава 5
- •§ 1. Массовые проблемы. Неразрешимость проблем
- •§ 2. Экстраалгоритм и три неразрешимые проблемы
- •§ 3, Некоторые замечания
- •Глава 6 электронные вычислительные машины и программирование
- •§ 1. Устройство эвм
- •§ 2. Процессоры эвм. Рабочий цикл
- •§ 3. Что такое программа
- •§ 4. Особенности современных эвм
- •§ 5. Входные языки программирования
- •§ 6. Необходимость содержательной теории алгоритмов. Какой она должна быть
- •Г л а в а 7 формальные языки
- •§ 1. Анализ естественного языка
- •§ 2. Искусственные языки. Формальные языки
- •§ 3. Буквы, связи, оболочки, конструкции
- •§ 4. Формальные грамматики
- •§ 5. Нотация Бекуса. Тезаурусы
- •§ 1. Что такое операция?
- •§ 2. Натуральные операции
- •§ 4. Первичные алгоритмы
- •§ 5. Натуральные алгоритмы
- •§ 6. Ограничения на структуру исходных данных сняты
- •§ 8. Соотношение с алгоритмами в интуитивном смысле
- •§ 10. Исследование тупиков (клинчей)
- •§ 11. Формальная семантика формального языка
- •Глава 9 математическое обеспечение эвм
- •§ 1. Анализ эвм и программ
- •§ 2. Что такое математическое обеспечение эвм
- •§ 3. Функциональная классификация программ математического обеспечения эвм
- •§ 4. Операционные системы
- •И автоматизация процессов
- •§ I. Использование эвм для управления
- •§ 2. Информационные системы
- •§ 3. Алгоритмизация процессов
- •§ 4. Язык алгоритмизации процессов
- •§ 5. Наука и искусство алгоритмизации
- •Заключение
- •§ 1. Может ли машина мыслить? Может ли человек решить алгоритмически неразрешимую проблему?
- •§ 2. Детерминированность машин. Самообучение
- •§ 3. Сознание машин. Алгоритмическое моделирование
§ 3. Кардинальные числа
Теория множеств позволяет сделать очень интересное обобщение понятия числа. Условимся мощностью конечного множества называть наибольшее натуральное число, которое будет использовано при нумерации его элементов, т. е. при установлении взаимно однозначного соответствия с последовательными числами 1, 2, 3, ..., принадлежащими натуральному ряду. При этом мощности равномощных конечных множеств оказываются равными, что подтверждает естественность нового термина.
Множеству всех натуральных чисел поставим в соответствие некоторую мощность, которую будем обозначать символом N. Ее же будем считать мощностью каждого множества, равномощного множеству натуральных чисел (т. е. каждому счетному множеству). Будем, наконец, считать, что множеству положительных действительных чисел, не превосходящих единицы, соответствует некоторая мощность К, которая является мощностью также каждого континуального множества.
Если каждое множество, являющееся правильной частью множества М, а также само множество М называть подмножествами множества М, можно доказать теорему:
Если М — конечное множество мощности п, то множество всех его подмножеств (считаемых элементами этого нового множества) имеет мощность 2n (имеются в виду только попарно неравные между собой подмножества).
Мы не будем приводить доказательства этой теоремы, подтвердим ее только примером. Пусть множество М состоит из элементов а1, а2, а3 и, следовательно, имеет мощность 3. Его подмножествами будут три одноэлементных множества {a1}, {a2}, {а3}, три двухэлементных множества {а1, а2}, {а1, а3}, {a2, а3}, одно трехэлементное множество {а1, а2, а3} и одно пустое множество { }. Их ровно восемь, а это значит, что мощность множества, для которого они являются элементами, равна 23.
Обратим внимание на способ обозначения множеств, которым мы пользовались. Мы перечисляли элементы множества и заключали их в фигурные скобки. Множество подмножеств множества М можно было обозначить так:
{{ },
{а1},
{a2,
{a3},
{a1.
a2},
{a1,
а3},
{а2,
а3},
{a1,
а2,
а3}}.
По аналогии с мощностями конечных
множеств условимся мощность множества
всех (не равных между собой) подмножеств
бесконечного множества обозначать
символом 2т,
если
мощность исходного множества т.
Доказано,
что K=2N.
При
этом 2К
будет
равно
.
Мы не знаем, все ли возможные мощности могут быть обозначены с помощью введенных обозначений, но это пока для нас и неважно. Будем только считать, что для каждого множества (а значит, и для всех равномощных ему множеств) существует некоторая мощность.
Остается «установить порядок» между мощностями. Делается это так. Полагают, что мощности равиомощных множеств равны. Это условие уже выполнено. Далее, считают, что мощность множества M1 (обозначим ее m1) меньше мощности множества М2 (обозначим ее m2), если M1 равномощно некоторому подмножеству множества М2, причем М2 не равномощно ни одному подмножеству множества M1. Это записывают так:
m1<m2.
Наконец считают, что mt больше тг и пишут т1>тг, если сформулированное выше условие при взаимной замене M1 на M2 окажется верным. Итак, теперь каждое множество характеризуется своей мощностью, и любые две мощности находятся в одном из трех перечисленных отношений.
Новая характеристика множества — его мощность — чем-то напоминает число, а для конечных множеств совпадает с числом. Это позволило ввести термин кардинальное число.
Кардинальным числом (элементов) множества М называется его мощность т. Все натуральные числа содержатся среди кардинальных, но существуют кардинальные числа, не являющиеся натуральными. Г. Кантор доказал следующие две теоремы.
Теорема 1. Для любого кардинального числа т справедливо неравенство m<2m.
Теорема 2. Мощность т' подмножества множества, имеющего мощность т, удовлетворяет неравенству т' ≤ т.
Теперь мы достаточно углубились в теорию множеств для того, чтобы суметь описать те «подземные толчки», которые потрясли математику в конце XIX — начале XX в.
