Стековые машины, эквивалентность двухстековой машины МТ

Стековая машина

Рис. 1. Стековая машина с k стеками

Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного.
На рис. 1 изображена k-стековая машина. С ленты последовательно считываются символы входного алфавита ([math]c_i[/math] — текущий считываемый символ). Для каждого стека с вершины снимается символ [math]x_i[/math]. Вместо него помещается строка [math]\alpha_i[/math] таким образом, чтобы первый символ строки находился на вершине стека.

Определение:

[math]k[/math]-cтековой машиной называется набор A=[math]\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle[/math], где [math]\Sigma[/math] — входной алфавит на ленте; [math]\Gamma[/math] — стековый алфавит; [math]Q[/math] — множество состояний автомата; [math]s[/math] — стартовое состояние автомата; [math]T[/math] — множество допускающих состояний автомата; [math]z_0[/math] — маркер дна стека; [math]\delta[/math] — функция переходов.

Эквивалентность двухстековой машины машине Тьюринга

Теорема:

Язык [math]L[/math] допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.

Доказательство:

[math]\triangleright[/math]

Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом [math]\$[/math], которого нет в исходном алфавите (аналог пробела в МТ).

[math]\triangleleft[/math]