Существуют различные теории сложности для хорошо определенных систем, и эти теории не всегда, естественно, связаны или даже сравнимы между собой. Одна из таких теорий требует использования машин Тьюринга и алгоритмов для этих машин, порождающих вычислимые функции. Структура и длина этих алгоритмов образуют основу, с помощью которой можно определить «вычислительную сложность». K сожалению, интуитивное понимание сложности, данное выше, не может быть применимо к машинам Тьюринга, так как в принципе машина Тьюринга может, вообще говоря, все (предполагается, что она имеет неограниченную память и неограниченное время для выполнения вычислений), т. е. она имеет бесконечную сложность. Ситуация становится более интересной, когда рассматривают только алгоритмы независимо от машин. При вычислении данного множества функций следует различать выполняющие это действие алгоритмы по их вычислительной сложности. Для того чтобы определить уровень сложности алгоритма, необходимо рассмотреть всевозможные вычисления и алгоритмы, а затем показать, сколько шагов данный алгоритм требует для вычисления конкретной функции.

Проблему вычислительной сложности можно исследовать с различных точек зрения (см. литературу в конце главы). Использование понятия вычислительной сложности, вообще говоря, значительно ограничивает возможности системного анализа. Отметим только, что при любом определении сложности сложность всего процесса вычислений определяется сложностью компонентных вычислений. Рассмотрим аксиоматический подход к проблеме сложности.