Теория вычислений: Машина Тьюринга, Машина Поста, НАМ и Автоматы

1. Машина Тьюринга (Turing Machine)

Машина Тьюринга — абстрактный исполнитель, состоящий из бесконечной ленты, считывающей головки и таблицы состояний.

Формально задается кортежем из 7 элементов:

$Q$ — конечное множество состояний;

$\Sigma$ — входной алфавит;

$\Gamma$ — ленточный алфавит ($\\Sigma \subset \Gamma$, включая пустой символ $\sqcup$);

$\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R, N\}$ — функция переходов;

$q_0$ — начальное состояние, $q_{accept}, q_{reject}$ — терминальные состояния.

Тезис Чёрча — Тьюринга: Любая функция, которая может быть вычислена алгоритмически, может быть вычислена на машине Тьюринга.

---

2. Машина Поста

Состоит из ленты с ячейками (0 или 1), каретки и программы из команд:

$V$ (поставить 1 / метку);

$E$ (стереть метку / поставить 0);

$\leftarrow$ (сдвиг влево);

$\rightarrow$ (сдвиг вправо);

$? (j_1, j_2)$ (ветвление: если в ячейке 1 переход на команду $j_1$, иначе $j_2$);

$!$ (останов).

---

3. Нормальные алгоритмы Маркова (НАМ)

Основаны на продукционных правилах подстановки в строке:

Правила упорядочены в список и применяются первое подходящее в самом левом вхождении.