Что такое машина Тьюринга и для чего она используется?

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

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

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