Машина Тьюринга в модели курса имеет конечный алфавит ленты, конечное множество состояний, одностороннюю бесконечную ленту и головку, которая на каждом шаге читает символ, изменяет его, меняет состояние и сдвигается на одну ячейку либо остаётся на месте. Состояние вычисления в данный момент задаётся конфигурацией
Время работы \(t_M(w)\) на слове \(w\) определяется числом конфигураций вычисления. Для оценки задачи по размеру входа рассматривают зависимость времени от \(n=|w|\). Полиномиальное время служит в курсе формальной моделью эффективной
Что важно запомнить
- Программа МТ состоит из конечного числа команд над символом ленты и состоянием.
- Конфигурация фиксирует содержимое используемой части ленты, состояние и положение головки.
- Вычисление — последовательность конфигураций, каждая следующая получается применением одной команды.
- Время \(t_M(w)\) — число конфигураций вычисления на конкретном
- Полиномиальная временная оценка означает ограничение вида \(O(n^k)\) для некоторой константы \(k\).
Структура машины Тьюринга
В используемой в курсе модели имеется конечный ленточный алфавит \(A\), конечное множество состояний \(Q\), начальное состояние и выделенные принимающее и отвергающее состояния. Входное слово записывается в первых ячейках ленты, остальные содержат пустой
Команда имеет вид «по текущему символу и состоянию записать новый символ, перейти в новое состояние и сдвинуть головку влево, вправо или остаться на месте». Для детерминированной МТ каждой паре «символ–состояние» соответствует не более одной команда.
Конфигурация и вычисление
Конфигурация — мгновенное описание вычисления: содержимое ленты вместе с текущим состоянием и положением головки. Вычисление машины на слове \(w\) — последовательность \(C_1,C_2,\ldots\) таких конфигураций. Если машина останавливается, последняя конфигурация является
Временная сложность
Время \(t_M(w)\) задаётся числом конфигураций в вычислении на \(w\). Если вычисление бесконечно, полагают \(t_M(w)=\infty\). Для массовой задачи интересует рост времени с длиной входа. Полиномиальными считаются оценки, ограниченные некоторым полиномом от \(|w|\). Именно это различие между полиномиальным и существенно более быстрым ростом используется далее при определении классов \(P\) и
Пример простыми словами
Если на всех входах длины \(n\) алгоритм заканчивает работу не более чем за \(3n^2+5n+7\) шагов, его временная сложность имеет порядок \(O(n^2)\). Конкретные коэффициенты важны для реализации, но при определении класса \(P\) существенно прежде всего полиномиальное поведение.
Частые ошибки
- Путать конфигурацию с командой машины: конфигурация описывает состояние всего текущего вычисления.
- Считать длину программы МТ временной сложностью. Время измеряет число шагов на входе.
- Говорить «полиномиальный алгоритм» без указания размера входных данных, относительно которого рассматривается полином.
