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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность двухсчетчиковой машины машине Тьюринга)
(не показано 46 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>k</tex>-счетчиковой машиной называется набор A=<tex>\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>\Rightarrow</tex>
Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соответствует число на первом счетчике трехсчетчиковой машины, второму стеку - второе, а третий счетчик используется для временных вычислений.
+
 
Тогда операции со стеком можно реализовать на трехсчетчиковой машине:
+
Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> {{---}} стековый алфавит, <tex>|\Pi|=P</tex>. Пронумеруем символы алфавита от <tex>0</tex> до <tex>P-1</tex>. Тогда стек можно рассматривать как целое число в системе счисления с основанием <tex>P</tex>.
*Добавление символа в стек: умножить значение счетчика на <tex>|\Pi|</tex> и прибавить число, соответствующее символу алфавита (цифре).
+
 
*Удаление символа из стека: целочисленно разделить значение счетчика на <tex>|\Pi|</tex>.
+
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
*Проверить верхний символ стека: найти остаток от деления значения счетчика на <tex>|\Pi|</tex>.
+
*'''Снять символ со стека'''. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток.  
Все эти элементарные операции очевидно реализуются при помощи третьего счетчика. Например, рассмотрим операцию добавления символа в стек. Напишем программу для трехсчетчиковой машины, реализующую эту операцию.
+
*'''Добавить символ в стек'''. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек.
  '''while''' (первый счетчик не ноль)
+
*'''Проверка верхнего символа стека'''. Для этого необходимо найти остаток от деления на <tex>P</tex>.
  {
+
 
    '''for''' (i = 0; i < <tex>|\Pi|</tex>; ++i)
+
Опишем реализацию арифметических операций с счётчиком, использованных при описании имитации работы двухстековой машины, при помощи двух счётчиков и управляющего автомата.
      увеличить третий счетчик;
+
*'''Разделить значение первого счётчика на число <tex>C</tex>, отбросив остаток.''' Пока первый счётчик не равен нулю, будем уменьшать его на один. При этом после каждых <tex>C</tex> успешных уменьшений значения первого счётчика будем увеличивать на один значение второго счётчика. Далее скопируем значение второго счётчика на первый: пока второй счётчик не равен нулю, уменьшаем его значение и увеличиваем значение первого счётчика. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат.
    уменьшить первый счетчик;
+
*'''Умножить значение первого счётчика на число <tex>C</tex>.''' Будем уменьшать первый счётчик на один и увеличивать второй на <tex>C</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат.
  }
+
*'''Увеличить значение счётчика на <tex>C</tex>.''' Последовательно <tex>C</tex> раз увеличиваем значение счётчика на один.
  '''for''' (i = 0; i < номер добавляемого символа в алфавите; ++i)
+
*'''Найти остаток от деления значения первого счётчика на число <tex>C</tex>.''' Рассмотрим автомат из <tex>C</tex> состояний. Пронумеруем состояние от <tex>0</tex> до <tex>C-1</tex>. Пусть <tex>0</tex> {{---}} стартовое состояние автомата. Скопируем значение с первого счётчика на второй. В случае если второй счётчик не нуль, автомат осуществляет переход из состояния <tex>i</tex> в состояние <tex>i+1</tex> (из состояния с номером <tex>C-1</tex> осуществляется переход в состояние с номером <tex>0</tex>), при этом значение второго счётчика уменьшается на один, а первого {{---}} увеличивается на один. Ясно, что в момент, когда третий счётчик станет равен нулю, управляющий автомат окажется в состоянии с номером, равным остатку от деления значения первого счётчика на <tex>C</tex>.
    увеличить третий счетчик;
+
 
  '''while''' (третий счетчик не ноль)
+
Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой.
  {
+
 
    уменьшить третий счетчик;
+
<tex>\Leftarrow</tex>
    увеличить первый счетчик;
+
 
  }
+
Трёхсчётчиковая машина является частным случаем трёхстековой машины, а любая <tex>k</tex>-стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой.  
Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции  с двухстековой машиной существует эквивалентная операция с трехсчетчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчетчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчетчиковая.
 
 
}}
 
}}
  
 +
==Эквивалентность <tex>k</tex>-счётчиковой машины двухсчётчиковой ==
 
{{Лемма
 
{{Лемма
|statement=<tex>\forall 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> - k-е простое число. Тогда любое состояние k-счетчиковой машины можно хранить на одном счетчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулем осуществляются на двухсчетчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счетчика простое число. Для этих вычислений и будет использоваться второй счетчик. Таким образом, <tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковой машины <tex>\exists</tex> эквивалентная ей двухсчетчиковая машина.
+
Для доказательства покажем, как имитировать <tex>k</tex>-счётчиковую машины на двухсчётчиковой. Пусть <tex>C_1, C_2, \ldots, C_k</tex> {{---}} значения счётчиков <tex>k</tex>-счётчиковой машины. Тогда состояние <tex>k</tex>-счётчиковой машины можно охарактеризовать одним числом <tex>2^{C_1}\cdot3^{C_2}\cdot \ldots \cdot p_k^{C_k}</tex>, где <tex>p_k</tex> {{---}} <tex>k</tex>-е простое число.
 +
Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.
 +
 
 +
Тогда элементарные операции на <tex>k</tex>-счётчиковой машине реализуются следующим образом.
 +
*'''Увеличить <tex>i</tex>-й счётчик.''' Для этого необходимо умножить значение счётчика на <tex>p_i</tex>.
 +
*'''Уменьшить <tex>i</tex>-й счётчик.''' Для этого необходимо  поделить значение счётчика на <tex>p_i</tex>.
 +
*'''Сравнить с нулём значение <tex>i</tex>-го счётчика.''' Для этого необходимо найти остаток от деления значения счётчика на <tex>p_i</tex> и сравнить его с нулём.
 +
Операции умножения на константу, деления на константу и нахождения остатка от деления на константу значения счётчика при помощи одного вспомогательного счётчика описаны в предыдущей лемме.
 +
Таким образом, для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
 
}}
 
}}
  
 +
== Эквивалентность двухсчётчиковой машины МТ ==
 
{{Теорема
 
{{Теорема
|statement=Для любого перечислимого языка <tex>L</tex> существует двухсчетчиковая машина, которая распознает этот язык.
+
|statement=Для любого перечислимого языка <tex>L</tex> существует двухсчётчиковая машина, которая распознает этот язык.
 
|proof=
 
|proof=
Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]].
+
Утверждение теоремы очевидно следует из двух описанных выше лемм и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]].
 
}}
 
}}
  
==Источники==
+
==См. также ==
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
+
* [[Машина Тьюринга]]
 +
* [[Стековые машины, эквивалентность двухстековой машины МТ]]
 +
 
 +
== Источники информации ==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 +
 
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Версия 11:50, 21 мая 2020

Определение:
[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]\Rightarrow[/math]

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

Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.

  • Снять символ со стека. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на [math]P[/math], отбросив остаток.
  • Добавить символ в стек. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на [math]P[/math] и прибавить к нему номер символа, который добавляется на стек.
  • Проверка верхнего символа стека. Для этого необходимо найти остаток от деления на [math]P[/math].

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

  • Разделить значение первого счётчика на число [math]C[/math], отбросив остаток. Пока первый счётчик не равен нулю, будем уменьшать его на один. При этом после каждых [math]C[/math] успешных уменьшений значения первого счётчика будем увеличивать на один значение второго счётчика. Далее скопируем значение второго счётчика на первый: пока второй счётчик не равен нулю, уменьшаем его значение и увеличиваем значение первого счётчика. Очевидно, что при фиксированном [math]C[/math] для данной операции может быть построен управляющий автомат.
  • Умножить значение первого счётчика на число [math]C[/math]. Будем уменьшать первый счётчик на один и увеличивать второй на [math]C[/math]. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном [math]C[/math] для данной операции может быть построен управляющий автомат.
  • Увеличить значение счётчика на [math]C[/math]. Последовательно [math]C[/math] раз увеличиваем значение счётчика на один.
  • Найти остаток от деления значения первого счётчика на число [math]C[/math]. Рассмотрим автомат из [math]C[/math] состояний. Пронумеруем состояние от [math]0[/math] до [math]C-1[/math]. Пусть [math]0[/math] — стартовое состояние автомата. Скопируем значение с первого счётчика на второй. В случае если второй счётчик не нуль, автомат осуществляет переход из состояния [math]i[/math] в состояние [math]i+1[/math] (из состояния с номером [math]C-1[/math] осуществляется переход в состояние с номером [math]0[/math]), при этом значение второго счётчика уменьшается на один, а первого — увеличивается на один. Ясно, что в момент, когда третий счётчик станет равен нулю, управляющий автомат окажется в состоянии с номером, равным остатку от деления значения первого счётчика на [math]C[/math].

Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой.

[math]\Leftarrow[/math]

Трёхсчётчиковая машина является частным случаем трёхстековой машины, а любая [math]k[/math]-стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой.
[math]\triangleleft[/math]

Эквивалентность [math]k[/math]-счётчиковой машины двухсчётчиковой

Лемма:
Для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
Доказательство:
[math]\triangleright[/math]

Для доказательства покажем, как имитировать [math]k[/math]-счётчиковую машины на двухсчётчиковой. Пусть [math]C_1, C_2, \ldots, C_k[/math] — значения счётчиков [math]k[/math]-счётчиковой машины. Тогда состояние [math]k[/math]-счётчиковой машины можно охарактеризовать одним числом [math]2^{C_1}\cdot3^{C_2}\cdot \ldots \cdot p_k^{C_k}[/math], где [math]p_k[/math][math]k[/math]-е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.

Тогда элементарные операции на [math]k[/math]-счётчиковой машине реализуются следующим образом.

  • Увеличить [math]i[/math]-й счётчик. Для этого необходимо умножить значение счётчика на [math]p_i[/math].
  • Уменьшить [math]i[/math]-й счётчик. Для этого необходимо поделить значение счётчика на [math]p_i[/math].
  • Сравнить с нулём значение [math]i[/math]-го счётчика. Для этого необходимо найти остаток от деления значения счётчика на [math]p_i[/math] и сравнить его с нулём.

Операции умножения на константу, деления на константу и нахождения остатка от деления на константу значения счётчика при помощи одного вспомогательного счётчика описаны в предыдущей лемме.

Таким образом, для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
[math]\triangleleft[/math]

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

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

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)