В чём сложность алгоритмов на основе машины Тьюринга?

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

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

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

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