Изменения

'''<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>Q</tex> — {{---}} множество состояний автомата;*<tex>s</tex> — {{---}} стартовое состояние автомата;*<tex>T</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>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>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>-е простое число.

Утверждение теоремы очевидно следует из двух описанных выше лемм, и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]] и тезиса Тьюринга-Черча.

==См. также ==* [[Машина Тьюринга]]* [[Стековые машины, эквивалентность двухстековой машины МТ]] ==Источникиинформации ==