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