Нижняя оценка на произведение времени и памяти для многоленточной машины Тьюринга, которая распознает язык палиндромов. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте. Бесконечность простых чисел. Нижняя оценка на сложность распознавания палиндромов на одноленточной машине Тьюринга.