$$ M = (Q, q_0, q_f, \Sigma, b, \delta) $$

• $Q$ - множество состояний
• $q_0, q_f$ - начальное и конечное состояния
• $\Sigma$ - конечный алфавит
• $b$ - пустой символ из алфавита
• $\delta: \Sigma \times Q \rightarrow \Sigma \times Q \times {\leftarrow, \rightarrow}$

Фиксируем бинарный алфавит $\mathbb{B}^*$ - конечные бинарные последовательности (включающие пустой символ)

Параметры

• $M(\omega)$ - вычисляемая функция
• $T(\omega)$ - время работы (количество тактов)
• $S(\omega)$ - используемая память (количество ячеек ленты)

Задачи

• Распознавание $L \subset \mathbb{B}^$ $$ \forall \omega \in \mathbb{B}^:~ (M(\omega) \neq~\perp)\wedge(M(\omega) = 1 \iff \omega \in L) $$
• Поиск по отношению $R$ $$ \forall \omega \in \mathbb{B}^:~ (M(\omega) \neq~\perp)\wedge(\exists a \in \mathbb{B}^~(\omega, a)\in R \implies (\omega, M(\omega)) \in R) $$