Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ — различия между версиями
(→Эквивалентность двухсчетчиковой машины машине Тьюринга) |
|||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | <tex>k</tex>- | + | <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>\Sigma</tex> — входной алфавит на ленте; | *<tex>\Sigma</tex> — входной алфавит на ленте; | ||
*<tex>Q</tex> — множество состояний автомата; | *<tex>Q</tex> — множество состояний автомата; | ||
*<tex>s</tex> — стартовое состояние автомата; | *<tex>s</tex> — стартовое состояние автомата; | ||
*<tex>T</tex> — множество допускающих состояний автомата; | *<tex>T</tex> — множество допускающих состояний автомата; | ||
− | *<tex>\delta</tex> — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния | + | *<tex>\delta</tex> — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счётчиков. |
− | Для каждого | + | Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить является ли значение счетчика нулем. |
− | Будем считать, что значение нулевых | + | Будем считать, что значение нулевых счётчиков уменьшать нельзя. |
}} | }} | ||
− | По сути, <tex>k</tex>- | + | По сути, <tex>k</tex>-счётчиковая машина является [[Стековые машины, эквивалентность двухстековой машины МТ|<tex>k</tex>-стековой машиной]] с односимвольным алфавитом. |
== Эквивалентность двухсчетчиковой машины машине Тьюринга == | == Эквивалентность двухсчетчиковой машины машине Тьюринга == | ||
{{Лемма | {{Лемма | ||
− | |statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается | + | |statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчётчиковой машиной. |
|proof= | |proof= | ||
− | Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что | + | Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчётчиковая машина эквивалентна по вычислительной мощности двухстековой машине. |
− | Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соответствует число на первом | + | Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соответствует число на первом счётчике трехсчётчиковой машины, второму стеку — второе, а третий счётчик используется для временных вычислений. |
− | Тогда операции со стеком можно реализовать на | + | Тогда операции со стеком можно реализовать на трехсчётчиковой машине: |
− | *добавление символа в стек: умножить значение | + | *добавление символа в стек: умножить значение счётчика на <tex>|\Pi|</tex> и прибавить число, соответствующее символу алфавита (цифре); |
− | *удаление символа из стека: целочисленно разделить значение | + | *удаление символа из стека: целочисленно разделить значение счётчика на <tex>|\Pi|</tex>; |
− | *проверить верхний символ стека: найти остаток от деления значения | + | *проверить верхний символ стека: найти остаток от деления значения счётчика на <tex>|\Pi|</tex>. |
− | Все эти элементарные операции очевидно реализуются при помощи третьего | + | Все эти элементарные операции очевидно реализуются при помощи третьего счётчика. Например, рассмотрим операцию добавления символа в стек. Напишем программу для трехсчётчиковой машины, реализующую эту операцию. |
− | '''while''' (первый | + | '''while''' (первый счётчик не ноль) |
{ | { | ||
'''for''' (i = 0; i < <tex>|\Pi|</tex>; ++i) | '''for''' (i = 0; i < <tex>|\Pi|</tex>; ++i) | ||
− | увеличить третий | + | увеличить третий счётчик; |
− | уменьшить первый | + | уменьшить первый счётчик; |
} | } | ||
'''for''' (i = 0; i < номер добавляемого символа в алфавите; ++i) | '''for''' (i = 0; i < номер добавляемого символа в алфавите; ++i) | ||
− | увеличить третий | + | увеличить третий счётчик; |
− | '''while''' (третий | + | '''while''' (третий счётчик не ноль) |
{ | { | ||
− | уменьшить третий | + | уменьшить третий счётчик; |
− | увеличить первый | + | увеличить первый счётчик; |
} | } | ||
− | Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с | + | Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с трехсчётчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчётчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчётчиковая. |
}} | }} | ||
{{Лемма | {{Лемма | ||
− | |statement=Для любого <tex>k</tex> и для любой <tex>k</tex>- | + | |statement=Для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина. |
|proof= | |proof= | ||
− | Пусть <tex>C_1, C_2, ..., C_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> существует | + | |statement=Для любого перечислимого языка <tex>L</tex> существует двухсчётчиковая машина, которая распознает этот язык. |
|proof= | |proof= | ||
Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]]. | Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]]. |
Версия 19:51, 5 января 2012
Определение: |
Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить является ли значение счетчика нулем. Будем считать, что значение нулевых счётчиков уменьшать нельзя. | -счётчиковой машиной называется набор , где
По сути, с односимвольным алфавитом. -стековой машиной
-счётчиковая машина являетсяЭквивалентность двухсчетчиковой машины машине Тьюринга
Лемма: |
Язык допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчётчиковой машиной. |
Доказательство: |
Так как двухстековая машина эквивалентна машине Тьюринга, то достаточно показать, что трехсчётчиковая машина эквивалентна по вычислительной мощности двухстековой машине. Пусть стековая машина имеет стековый алфавит . Тогда любое из состояний стеков можно считать числом в системе счисления с основанием . Пусть первому стеку соответствует число на первом счётчике трехсчётчиковой машины, второму стеку — второе, а третий счётчик используется для временных вычислений. Тогда операции со стеком можно реализовать на трехсчётчиковой машине:
Все эти элементарные операции очевидно реализуются при помощи третьего счётчика. Например, рассмотрим операцию добавления символа в стек. Напишем программу для трехсчётчиковой машины, реализующую эту операцию. while (первый счётчик не ноль)
{
for (i = 0; i <
Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с трехсчётчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчётчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчётчиковая. ; ++i)
увеличить третий счётчик;
уменьшить первый счётчик;
}
for (i = 0; i < номер добавляемого символа в алфавите; ++i)
увеличить третий счётчик;
while (третий счётчик не ноль)
{
уменьшить третий счётчик;
увеличить первый счётчик;
}
|
Лемма: |
Для любого и для любой -счётчиковой машины существует эквивалентная ей двухсчётчиковая машина. |
Доказательство: |
Пусть | — значения счётчиков -счётчиковой машины. Тогда состояние -счётчиковой машины можно охарактеризовать одним числом , где — -е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулём осуществляются на двухсчётчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счётчика простое число. Для этих вычислений и будет использоваться второй счётчик. Таким образом, для любого и для любой -счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
Теорема: |
Для любого перечислимого языка существует двухсчётчиковая машина, которая распознает этот язык. |
Доказательство: |
Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и эквивалентности двухстековой машины машине Тьюринга. |
Источники
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.