Нижняя оценка на палиндром на одноленточной машине Тьюринга. Моделирование k-ленточной машины на k-ленточной с линейным замедлением. Эффективное моделирование k-ленточной машины на 2-ленточной. Недетерминированные машины Тьюринга и класс NP. Задача Circuit-SAT, сведение Circuit-SAT к 3SAT.