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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность двухстековой машины трёхсчётчикой машине)
 
(не показаны 22 промежуточные версии 5 участников)
Строка 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> — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счётчиков.
Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить является ли значение счетчика нулём.
+
Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить, является ли значение счетчика нулём.
 
Будем считать, что значение нулевых счётчиков уменьшать нельзя.
 
Будем считать, что значение нулевых счётчиков уменьшать нельзя.
 
}}
 
}}
Строка 19: Строка 18:
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> - стековый алфавит, <tex>|\Pi|=P</tex>. Пронумеруем символы алфавита от <tex>0</tex> до <tex>P-1</tex>. Тогда стек можно рассматривать как целое число в системе счисления с основанием <tex>P</tex>.
+
Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> {{---}} стековый алфавит, <tex>|\Pi|=P</tex>. Пронумеруем символы алфавита от <tex>0</tex> до <tex>P-1</tex>. Тогда стек можно рассматривать как целое число в системе счисления с основанием <tex>P</tex>.
  
 
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
 
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
*'''Снять символ со стека'''. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на <tex>P</tex>, и, если это удалось сделать, третий увеличивать на один. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый: пока третий счётчик не равен нулю, уменьшаем третий счётчик и увеличиваем первый.  
+
*'''Снять символ со стека'''. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток.  
*'''Добавить символ в стек'''. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек. Пусть символ добавляется в первый стек. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на один и увеличивать третий на <tex>P</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый.  
+
*'''Добавить символ в стек'''. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек.
* '''Проверка верхнего символа стека'''. Для этого необходимо найти остаток от деления на <tex>P</tex>. Скопируем значение первого счётчика на третий. Реализуем деление с остатком при помощи введения дополнительных автоматов, входящих в управляющий автомат трехсчётчиковой машины. Этот автомат должен состоять из <tex>P</tex> состояний. Каждое состояние соответствует определенному остатку от деления. В случае, если третий счётчик не нуль, автомат осуществляет переход в состояние, соответствующее следующему остатку от деления. Если третий счётчик нуль, то остаток найден и осуществляется переход в управляющем автомате, соответствующий от деления. Будем уменьшать третий счетчик, каждый раз переходя в следующее состояние автомата.
+
*'''Проверка верхнего символа стека'''. Для этого необходимо найти остаток от деления на <tex>P</tex>.
 +
 
 +
Опишем реализацию арифметических операций с счётчиком, использованных при описании имитации работы двухстековой машины, при помощи двух счётчиков и управляющего автомата.
 +
*'''Разделить значение первого счётчика на число <tex>C</tex>, отбросив остаток.''' Пока первый счётчик не равен нулю, будем уменьшать его на один. При этом после каждых <tex>C</tex> успешных уменьшений значения первого счётчика будем увеличивать на один значение второго счётчика. Далее скопируем значение второго счётчика на первый: пока второй счётчик не равен нулю, уменьшаем его значение и увеличиваем значение первого счётчика. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат.
 +
*'''Умножить значение первого счётчика на число <tex>C</tex>.''' Будем уменьшать первый счётчик на один и увеличивать второй на <tex>C</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат.
 +
*'''Увеличить значение счётчика на <tex>C</tex>.''' Последовательно <tex>C</tex> раз увеличиваем значение счётчика на один.  
 +
*'''Найти остаток от деления значения первого счётчика на число <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>.  
 +
 
 +
Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
Строка 35: Строка 42:
 
|statement=Для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
 
|statement=Для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
 
|proof=
 
|proof=
Для доказательства покажем, как имитировать <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>-е простое число.
+
Для доказательства покажем, как имитировать <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-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.
 
Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.
  
 
Тогда элементарные операции на <tex>k</tex>-счётчиковой машине реализуются следующим образом.
 
Тогда элементарные операции на <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>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>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
 
Таким образом, для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
 
}}
 
}}
Строка 50: Строка 57:
 
|statement=Для любого перечислимого языка <tex>L</tex> существует двухсчётчиковая машина, которая распознает этот язык.
 
|statement=Для любого перечислимого языка <tex>L</tex> существует двухсчётчиковая машина, которая распознает этот язык.
 
|proof=
 
|proof=
Утверждение теоремы очевидно следует из двух описанных выше лемм, [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]] и тезиса Тьюринга-Черча.
+
Утверждение теоремы очевидно следует из двух описанных выше лемм и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]].
 
}}
 
}}
  
==Источники==
+
==См. также ==
 +
* [[Машина Тьюринга]]
 +
* [[Стековые машины, эквивалентность двухстековой машины МТ]]
 +
 
 +
== Источники информации ==
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 +
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Текущая версия на 18:12, 22 марта 2019

Определение:
[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 (рус.)