Абстрактная модель вычислительной машины. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга способна имитировать процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга