Викиконспекты - Вклад участника [ru]

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T22:15:46Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP[1]}</tex>.
Во-первых, очевидно, что число раундов не превосходит трёх. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{8}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:52:25Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP[1]}</tex>.
Во-первых, очевидно, что число раундов не превосходит трёх. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:51:09Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:49:41Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к следующему; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:49:12Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к следующему; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:47:29Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол действий для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к следующему; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что такой протокол удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:46:08Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и завершает доказательство теоремы.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол действий для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к следующему; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что такой протокол удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:45:08Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> убеждает <tex>V</tex> в том, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и завершает доказательство теоремы.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол действий для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё два раза и перейдём к следующему; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что такой протокол удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет три раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до трёх раундов протокола, вероятность того, что <tex>V</tex> примет слово <tex>x</tex> когда оно не принадлежит языку (т.е. <tex>P</tex> три раза пройдёт проверки <tex>V</tex>) равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:26:07Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> убеждает <tex>V</tex> в том, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и завершает доказательство теоремы.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол:
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; 
# <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен; 
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:24:17Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> убеждает <tex>V</tex> в том, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и завершает доказательство теоремы.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол:
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>π</tex> с вероятностной ленты; 
# <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>π</tex>; 
# <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен; 
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T21:23:01Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> убеждает <tex>V</tex> в том, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex> ;
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex> ;
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex> .
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex> ;
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex> ;
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex> .
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и завершает доказательство теоремы.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол:
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>π</tex> с вероятностной ленты;
# <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>π</tex>;
# <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен;
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T20:51:02Z

Воронов:

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T20:40:34Z

Воронов:

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T20:21:36Z

Воронов:

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T20:03:38Z

Воронов:

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T20:03:15Z

Воронов:

Файл:IPS.png

2012-05-31T19:33:50Z

Воронов: загружена новая версия «Файл:IPS.png»

Файл:IPS.png

2012-05-31T19:29:48Z

Воронов:

Интерактивные протоколы. Класс IP. Класс AM

2012-05-31T18:00:53Z

Воронов:

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом называется абстрактная машина, моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>), такими, что
# <tex>Prover</tex> убеждает <tex>Verifier</tex> в том, что слово <tex>x</tex> принадлежит языку
# <tex>Prover</tex> не ограничен в вычислительной мощности
# <tex>Verifier</tex> — вероятностная машина Тьюринга
# <tex>Verifier</tex> ограничен полиномиальным временем работы
}}

Далее <tex>Prover</tex> обозначается <tex>P</tex>, а <tex>Verifier</tex> — <tex>V</tex>.

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex> (см. рис. 1).

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex> 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex> 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex> 
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
Это очевидным образом следует из определений <tex>\mathrm{BPP}</tex> и <tex>V</tex> в <tex>\mathrm{IP}</tex>; <tex>V</tex> даже не требуется общаться с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и доказывает теорему.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-26T16:47:57Z

Воронов:

==Класс IP==
{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
<tex> 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex> 
<tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex> 
<tex> 3) </tex> Число раундов интерактивного протокола <tex> f(n), n = |x| </tex> 
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
Это очевидным образом следует из определений <tex>\mathrm{BPP}</tex> и <tex>V</tex> в <tex>\mathrm{IP}</tex>; <tex>V</tex> даже не требуется общаться с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и доказывает теорему.
}}

Интерактивные протоколы. Класс IP. Класс AM

2012-05-26T15:17:55Z

Воронов: Новая страница: «==Класс IP== {{Определение |definition = <tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <tex> 1) \forall x \in L \Rightarrow P(V(x) ...»

==Класс IP==
{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
<tex> 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex> 
<tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex> 
<tex> 3) </tex> Число раундов интерактивного протокола <tex> f(n), n = |x| </tex> 
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> 
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. 
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> 
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит, степень входа элементов схемы <tex>C_n</tex> — это полином от <tex>n</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом: 
[[Файл:circuit.jpg]]
При замене каждого такого элемента глубина схемы увеличивается не более чем в <tex>log_2 r(n) = O(log(n))</tex>, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов глубина схемы станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>. Так как при замене элемента мы добавляем не более <tex>r(n)</tex> элементов, а изначально размер схемы был полиномиальным и каждый ее элемент мы заменили на полином элементов, то после всех замен размер схемы остался полиномиальным.
}}

Разрешимые (рекурсивные) языки

2012-01-23T20:39:15Z

Воронов:

{{Определение
|definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным'''), если существует такая программа <tex> p </tex>, что <tex> \forall w \in L: p(w) = 1</tex>, а <tex> \forall w \notin L: p(w) = 0</tex>.
}}

==Пример разрешимого множества==
{{Лемма
|id=st1
|statement=
Язык чётных чисел разрешим.
|proof=
Приведём программу, разрешающую язык чётных чисел:
<tex>p(i):</tex>
'''if''' <tex> i \ mod \ 2 == 0 </tex>
'''return''' <tex> 1 </tex>
'''else'''
'''return''' <tex> 0 </tex>
Заметим, что программа нигде не может зависнуть.
}}

==Пример неразрешимого множества==

{{Определение
|definition=Язык <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex> называется '''универсальным'''.
}}

{{Лемма
|id=st1
|statement=
Универсальный язык неразрешим.
|proof=
Приведём доказательство от противного. 
Пусть язык <tex> U </tex> разрешим. Тогда существует такая программа <tex> u </tex>, что <tex> \forall \langle p, x \rangle \in U: u(\langle p, x \rangle) = 1</tex>, а <tex> \forall \langle p, x \rangle \notin U: u(\langle p, x \rangle) = 0</tex>. 
Составим следующую программу:

<tex>r(x):</tex>
'''if''' <tex> u(\langle x, x \rangle) == 1 </tex>
'''while''' <tex> true </tex>
'''else'''
'''return''' <tex> 1 </tex>

Теперь рассмотрим вызов <tex> r(r) </tex>:
* если <tex> u(\langle r, r \rangle) = 1 </tex>, то условие '''if''' выполнится и программа зависнет. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>;
* если <tex> u(\langle r, r \rangle) = 0 </tex>, то условие '''if''' не выполнится и программа вернет <tex>1</tex>. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.

Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
}}

== Литература ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T23:29:34Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|center|Рис. 1. k-стековая машина]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). В каждом стеке с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>. Возможен также и <tex>\varepsilon\</tex>-переход.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow \cal P </tex> <tex> (Q \times (\Gamma^*)^k)\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. 
[[Изображение:SM.png|400px|thumb|center|Рис. 2. Представление ленты МТ двумя стеками и наоборот]]
<tex>\Rightarrow</tex> 
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow</tex> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ также, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}

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

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T18:38:23Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. k-стековая машина]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). В каждом стеке с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>. Возможен также и <tex>\varepsilon\</tex>-переход.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow \cal P </tex> <tex> (Q \times (\Gamma^*)^k)\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками и наоборот]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ также, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}

==Источники==
*Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер. с англ. — М. : Издательский дом "Вильямс", 2002.

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T18:29:15Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. k-стековая машина]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). В каждом стеке с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>. Возможен также и <tex>\varepsilon\</tex>-переход.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками и наоборот]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ также, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}

Файл:SM.png

2011-12-28T18:20:27Z

Воронов: загружена новая версия «Файл:SM.png»: Возврат к версии от 09:47, 28 декабря 2011

Представление ленты МТ двумя стеками

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T17:57:50Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. k-стековая машина]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). В каждом стеке с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>. Возможен также и <tex>\varepsilon\</tex>-переход.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Очевидно.
}}

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T17:23:24Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. k-стековая машина]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Очевидно.
}}

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T17:22:39Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Очевидно.
}}

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T17:21:30Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ). 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Очевидно.
}}

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T10:34:24Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ). 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Исходя из необходимости инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитировался добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

<tex>\Leftarrow)</tex> Очевидно.
}}

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T10:20:15Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ). 
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. 
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. 
Исходя из необходимости инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. 
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. 
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитировался добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть головку вправо" и "остаться на месте". После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. 
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. 
Таким образом, мы с помощью двухстековой машины сымитировали МТ.

[[Изображение:SMM.png|400px|thumb|left|Рис. 3. Представление двух стеков лентой МТ]]
<tex>\Leftarrow)</tex> Докажем, что если язык <tex>L</tex> допускается двухстековой машиной, то он допускается машиной Тьюринга. 
Двухстековую машину можно сымитировать трехленточной МТ (Рис. 3). На первой ленте будет записан вход, вторая лента будет имитировать первый стек, третья — второй. 
Стеки имитируются Конечный автомат для МТ получим из двухстековой машины следующей заменой действия на переходе:
}}

Файл:SMM.png

2011-12-28T10:17:43Z

Воронов: Представление двух стеков лентой МТ.

Представление двух стеков лентой МТ.

Файл:SM.png

2011-12-28T09:57:02Z

Воронов: загружена новая версия «Файл:SM.png»

Представление ленты МТ двумя стеками

Файл:SM.png

2011-12-28T09:53:53Z

Воронов: загружена новая версия «Файл:SM.png»

Представление ленты МТ двумя стеками

Файл:SM.png

2011-12-28T09:47:43Z

Воронов: загружена новая версия «Файл:SM.png»

Представление ленты МТ двумя стеками

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T09:32:07Z

Воронов:

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T09:23:36Z

Воронов:

Файл:SM.png

2011-12-28T09:07:35Z

Воронов: Представление ленты МТ двумя стеками

Представление ленты МТ двумя стеками

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T08:50:46Z

Воронов:

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T08:47:01Z

Воронов:

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T08:44:30Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|500px|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека.
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык L допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
sdf
}}

Файл:PDAk.png

2011-12-28T08:43:04Z

Воронов:

k-стековая машина.

Стековые машины, эквивалентность двухстековой машины МТ

2011-12-28T08:37:54Z

Воронов:

== Стековая машина ==
[[Изображение:PDAk.png|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. 
На рис. 1 изображена '''стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека.
{{Определение
|definition=
Стековой машиной с <tex>k</tex> магазинами называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow Q \times (\Gamma^*)^k\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
*<tex>Q</tex> — множество состояний автомата;
*<tex>s</tex> — стартовое состояние автомата;
*<tex>T</tex> — множество допускающих состояний автомата;
*<tex>z_0</tex> — маркер дна стека;
*<tex>\delta</tex> — функция переходов.
}}

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

Файл:PDAk.png

2011-12-28T08:37:28Z

Воронов: загружена новая версия «Файл:PDAk.png»

Стековая машина с k стеками.

Файл:PDAk.png

2011-12-28T08:35:21Z

Воронов: Стековая машина с k стеками.

Стековая машина с k стеками.