Понятие машины Тьюринга возникает в результате прямой попытки разложить интуитивно известные нам вычислительные процедуры на элементарные операции: Тьюринг привел ряд доводов в пользу того, что повторения его элементарных операций было бы достаточно для проведения любого возможного вычисления. Поэтому машина Тьюринга (МТ) используется:
1) если требуется доказать возможность алгоритмической реализации вычислительной функции;
2) если требуется оценить вычислительную сложность или трудоемкость решения задачи по данному алгоритму, т.е. время выполнения алгоритма.
Для этого мы моделируем работу произвольного алгоритма в терминах рассматриваемой задачи. Затем определяется класс машин-вычислителей, которые могут решить данную задачу – формально описываются правила работы машины, исходные данные, ограничения и т.д. (поскольку в определении задачи ничего не говорится о программах так таковых в привычном для нас понимании, то алгоритмическая разрешимость или неразрешимость, сводится к проблеме остановки произвольного алгоритма решения задачи). В качестве машины-вычислителя выберем машину Тьюринга, поскольку ранее было показано, что всякая вычислимая функция реализуема на МТ и сведем решение данной задачи к существующим группам задач, для которых известно, что они решаются на МТ.