Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность двухсчетчиковой машины машине Тьюринга)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<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>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>-счётчиковая машина является [[Стековые машины, эквивалентность двухстековой машины МТ|<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>;
+
*удаление символа из стека: целочисленно разделить значение счётчика на <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>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>-счетчиковой машины существует эквивалентная ей двухсчетчиковая машина.
+
Пусть <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

Определение:
[math]k[/math]-счётчиковой машиной называется набор [math]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[/math], где
  • [math]\Sigma[/math] — входной алфавит на ленте;
  • [math]Q[/math] — множество состояний автомата;
  • [math]s[/math] — стартовое состояние автомата;
  • [math]T[/math] — множество допускающих состояний автомата;
  • [math]\delta[/math] — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счётчиков.

Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить является ли значение счетчика нулем.

Будем считать, что значение нулевых счётчиков уменьшать нельзя.

По сути, [math]k[/math]-счётчиковая машина является [math]k[/math]-стековой машиной с односимвольным алфавитом.

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

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

Так как двухстековая машина эквивалентна машине Тьюринга, то достаточно показать, что трехсчётчиковая машина эквивалентна по вычислительной мощности двухстековой машине. Пусть стековая машина имеет стековый алфавит [math]\Pi[/math]. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием [math]|\Pi|[/math]. Пусть первому стеку соответствует число на первом счётчике трехсчётчиковой машины, второму стеку — второе, а третий счётчик используется для временных вычислений. Тогда операции со стеком можно реализовать на трехсчётчиковой машине:

  • добавление символа в стек: умножить значение счётчика на [math]|\Pi|[/math] и прибавить число, соответствующее символу алфавита (цифре);
  • удаление символа из стека: целочисленно разделить значение счётчика на [math]|\Pi|[/math];
  • проверить верхний символ стека: найти остаток от деления значения счётчика на [math]|\Pi|[/math].

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

 while (первый счётчик не ноль)
 {
    for (i = 0; i < [math]|\Pi|[/math]; ++i)
      увеличить третий счётчик;
    уменьшить первый счётчик;
 }
 for (i = 0; i < номер добавляемого символа в алфавите; ++i)
   увеличить третий счётчик;
 while (третий счётчик не ноль)
 {
    уменьшить третий счётчик;
    увеличить первый счётчик;
 }
Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с трехсчётчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчётчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчётчиковая.
[math]\triangleleft[/math]
Лемма:
Для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
Доказательство:
[math]\triangleright[/math]
Пусть [math]C_1, C_2, ..., C_k[/math] — значения счётчиков [math]k[/math]-счётчиковой машины. Тогда состояние [math]k[/math]-счётчиковой машины можно охарактеризовать одним числом [math]2^{C_1}*3^{C_2}*...*p_k^{C_k}[/math], где [math]p_k[/math][math]k[/math]-е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулём осуществляются на двухсчётчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счётчика простое число. Для этих вычислений и будет использоваться второй счётчик. Таким образом, для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
[math]\triangleleft[/math]
Теорема:
Для любого перечислимого языка [math]L[/math] существует двухсчётчиковая машина, которая распознает этот язык.
Доказательство:
[math]\triangleright[/math]
Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и эквивалентности двухстековой машины машине Тьюринга.
[math]\triangleleft[/math]

Источники

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.