Машина Тьюринга — это абстрактный исполнитель (абстрактная вычислительная машина), предложенная Аланом Тьюрингом в 1936 году для определения понятия алгоритма. 1

Используется для следующих целей:

• Формализация понятия алгоритма. 2 Если задачу можно решить с помощью какого-то алгоритма, то только тогда, когда её решение можно представить в виде программы для машины Тьюринга. 2
• Имитация других исполнителей. 1 На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. 1
• Получение оценок. 1 Машина Тьюринга оказалась удобным математическим аппаратом, позволяющим получать оценки как времени выполнения алгоритмов (в частности, и на реальных компьютерах), так и размера памяти, требуемой для вычислений. 1