Сложность алгоритмов на основе машины Тьюринга связана с мощностью внутреннего алфавита. 2 Чем больше количество внутренних состояний, тем более сложную программу может иметь машина Тьюринга и, следовательно, вычислить более сложную функцию. 2

Также при описании сложности алгоритма используются временная и пространственная сложность. 2 Временная сложность определяется как количество тактов работы машины, а пространственная — как количество задействованных ячеек на ленте, используемых для вычисления. 2

Согласно сложности, задачи на основе машины Тьюринга можно разбить на классы, например:

• Класс P. 1 Содержит все задачи, которые можно решить за полиномиальное время. 1
• Класс NP. 1 В него входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (вариант обычной машины Тьюринга, которая может делать предположения). 1