Изменения

<tex>k</tex>-счетчиковой счётчиковой машиной называется набор <tex>A=\langle\Sigma, Q, s\in Q, T \subset Q, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \{0,1\}^k \rightarrow Q \times \{ -1, 0, 1\}^k \rangle</tex>, где

*<tex>\delta</tex> — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счетчиков счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счетчиковсчётчиков.Для каждого счетчика счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить является ли значение счетчика нулем.Будем считать, что значение нулевых счетчиков счётчиков уменьшать нельзя.

По сути, <tex>k</tex>-счетчиковая счётчиковая машина является [[Стековые машины, эквивалентность двухстековой машины МТ|<tex>k</tex>-стековой машиной]] с односимвольным алфавитом.

|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчетчиковой трехсчётчиковой машиной.

Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчетчиковая трехсчётчиковая машина эквивалентна по вычислительной мощности двухстековой машине.Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соответствует число на первом счетчике трехсчетчиковой счётчике трехсчётчиковой машины, второму стеку - — второе, а третий счетчик счётчик используется для временных вычислений.Тогда операции со стеком можно реализовать на трехсчетчиковой трехсчётчиковой машине:*добавление символа в стек: умножить значение счетчика счётчика на <tex>|\Pi|</tex> и прибавить число, соответствующее символу алфавита (цифре);*удаление символа из стека: целочисленно разделить значение счетчика счётчика на <tex>|\Pi|</tex>;*проверить верхний символ стека: найти остаток от деления значения счетчика счётчика на <tex>|\Pi|</tex>.Все эти элементарные операции очевидно реализуются при помощи третьего счетчикасчётчика. Например, рассмотрим операцию добавления символа в стек. Напишем программу для трехсчетчиковой трехсчётчиковой машины, реализующую эту операцию. '''while''' (первый счетчик счётчик не ноль)

увеличить третий счетчиксчётчик; уменьшить первый счетчиксчётчик;

увеличить третий счетчиксчётчик; '''while''' (третий счетчик счётчик не ноль)

уменьшить третий счетчиксчётчик; увеличить первый счетчиксчётчик;

Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с трехсчетчиковой трехсчётчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчетчиковой трехсчётчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчетчиковаятрехсчётчиковая.

|statement=Для любого <tex>k</tex> и для любой <tex>k</tex>-счетчиковой счётчиковой машины существует эквивалентная ей двухсчетчиковая двухсчётчиковая машина.

Пусть <tex>C_1, C_2, ..., C_k</tex> - — значения счетчиков счётчиков <tex>k</tex>-счетчиковой счётчиковой машины. Тогда состояние <tex>k</tex>-счетчиковой счётчиковой машины можно охарактеризовать одним числом <tex>2^{C_1}*3^{C_2}*...*p_k^{C_k}</tex>, где <tex>p_k</tex> - — <tex>k</tex>-е простое число. Тогда любое состояние k-счетчиковой счётчиковой машины можно хранить на одном счетчикесчётчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулем нулём осуществляются на двухсчетчиковой двухсчётчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счетчика счётчика простое число. Для этих вычислений и будет использоваться второй счетчиксчётчик. Таким образом, для любого <tex>k</tex> и для любой <tex>k</tex>-счетчиковой счётчиковой машины существует эквивалентная ей двухсчетчиковая двухсчётчиковая машина.

|statement=Для любого перечислимого языка <tex>L</tex> существует двухсчетчиковая двухсчётчиковая машина, которая распознает этот язык.