Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ — различия между версиями
(→Эквивалентность k-счётчиковой машины двухсчётчиковой) |
м (rollbackEdits.php mass rollback) |
||
(не показана 21 промежуточная версия 9 участников) | |||
Строка 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> допускается двухстековой машиной тогда и только тогда, когда он допускается трёхсчётчиковой машиной. | ||
Строка 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>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, | + | Для доказательства покажем, как имитировать <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 (рус.) | ||
+ | |||
+ | [[Категория: Теория вычислимости]] | ||
+ | [[Категория: Вычислительные формализмы]] |
Текущая версия на 19:33, 4 сентября 2022
Определение: |
Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить, является ли значение счетчика нулём. Будем считать, что значение нулевых счётчиков уменьшать нельзя. | -счётчиковой машиной называется набор , где
Эквивалентность двухстековой машины трёхсчётчиковой машине
Лемма: |
Язык допускается двухстековой машиной тогда и только тогда, когда он допускается трёхсчётчиковой машиной. |
Доказательство: |
Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть — стековый алфавит, . Пронумеруем символы алфавита от до . Тогда стек можно рассматривать как целое число в системе счисления с основанием .Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
Опишем реализацию арифметических операций с счётчиком, использованных при описании имитации работы двухстековой машины, при помощи двух счётчиков и управляющего автомата.
Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой. Трёхсчётчиковая машина является частным случаем трёхстековой машины, а любая -стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой. |
Эквивалентность -счётчиковой машины двухсчётчиковой
Лемма: |
Для любого и для любой -счётчиковой машины существует эквивалентная ей двухсчётчиковая машина. |
Доказательство: |
Для доказательства покажем, как имитировать -счётчиковую машины на двухсчётчиковой. Пусть — значения счётчиков -счётчиковой машины. Тогда состояние -счётчиковой машины можно охарактеризовать одним числом , где — -е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.Тогда элементарные операции на -счётчиковой машине реализуются следующим образом.
Операции умножения на константу, деления на константу и нахождения остатка от деления на константу значения счётчика при помощи одного вспомогательного счётчика описаны в предыдущей лемме. Таким образом, для любого и для любой -счётчиковой машины существует эквивалентная ей двухсчётчиковая машина. |
Эквивалентность двухсчётчиковой машины МТ
Теорема: |
Для любого перечислимого языка существует двухсчётчиковая машина, которая распознает этот язык. |
Доказательство: |
Утверждение теоремы очевидно следует из двух описанных выше лемм и эквивалентности двухстековой машины машине Тьюринга. |
См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)