Машина Тьюринга — абстрактный исполнитель, предназначенный для формализации понятия алгоритма. Описание и устройство машины: основные свойства, продуктивность; тезис Черча. Машина Тьюринга и алгоритмически неразрешимые функции. Проблема остановки машины.