Сложность относительно декомпрессора. Оптимальный декомпрессор. Свойства колмогоровской сложности. Вычислимые функции и перечислимые множества. Невычислимость нетривиальной нижней оценки на колмогоровскую сложность. Доказательство Чайтина первой теоремы Геделя о неполноте. Доказательство бесконечности простых чисел. Нижняя оценка на время работы одноленточной машины Тьюринга, распознающей палиндромы.