Теорема о ёмкостной иерархии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 3: Строка 3:
  
 
== Доказательство ==
 
== Доказательство ==
Зафиксируем <math>f</math> и <math>g</math>.
+
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.
  
Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)</math> памяти <math>\}</math> .
+
Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)\,\!</math> памяти <math>\}\,\!</math> .
  
Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина тьюринга <math>m_0</math> такая, что <math>L(m_0)=L</math>.
+
Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.
  
Рассмотрим <math>m_0(<m_0,x>)</math>.  
+
Рассмотрим <math>m_0(<m_0,x>)\,\!</math>.  
  
Пусть <math>m_0</math> допускает <math><m_0,x></math>. Тогда <math><m_0,x> \in L</math>, но в  <math>L</math> по определению не может быть пары <math><m,x></math>, которую допускает <math>m</math>. Таким образом, получаем противоречие.
+
Пусть <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>. Тогда <math><m_0,x> \in L</math>, но в  <math>L</math> по определению не может быть пары <math><m,x>\,\!</math>, которую допускает <math>m\,\!</math>. Таким образом, получаем противоречие.
  
Если <math>m_0</math> не допускает <math><m_0,x></math>, то <math><m_0,x></math> не принадлежит языку <math>L</math>. Это значит, что либо <math>m_0</math> допускает <math><m_0,x></math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)</math>. Но  <math>L \in DSPACE(f)</math>, поэтому <math>m_0</math> на любом входе <math>x</math> использует не более <math>f(|x|)</math> памяти. Получаем противоречие.  
+
Если <math>m_0\,\!</math> не допускает <math><m_0,x>\,\!</math>, то <math><m_0,x>\,\!</math> не принадлежит языку <math>L\,\!</math>. Это значит, что либо <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)\,\!</math>. Но  <math>L \in DSPACE(f)</math>, поэтому <math>m_0\,\!</math> на любом входе <math>x\,\!</math> использует не более <math>f(|x|)\,\!</math> памяти. Получаем противоречие.  
  
 
Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.
 
Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.
  
<math>L \in DSPACE(g)</math>, так как можно проэмулировать <math>m</math>.
+
<math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары  <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)\,\!</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1\,\!</math> будет использовать памяти не более <math>g(|<m_3,x>|)\,\!</math>.
  
Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>.
+
 
 +
Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DSPACE(g(n)) \neq DSPACE(f(n))</math>
  
 
Теорема доказана.
 
Теорема доказана.

Версия 23:55, 12 марта 2010

Формулировка

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f[/math] и [math]g[/math] таких, что [math] \lim_{n \rightarrow \infty} f(n)/g(n) = 0[/math], выполняется [math]DSPACE(g(n)) \ne DSPACE(f(n))[/math].

Доказательство

Зафиксируем [math]f\,\![/math] и [math]g\,\![/math].

Рассмотрим язык [math]L = \{ \lt m,x\gt \mid m(\lt m,x\gt )[/math] не допускает, используя не более [math] f(|\lt m,x\gt |)\,\![/math] памяти [math]\}\,\![/math] .

Пусть [math]L \in DSPACE(f)[/math], тогда для него есть машина Тьюринга [math]m_0\,\![/math] такая, что [math]L(m_0)=L\,\![/math].

Рассмотрим [math]m_0(\lt m_0,x\gt )\,\![/math].

Пусть [math]m_0\,\![/math] допускает [math]\lt m_0,x\gt \,\![/math]. Тогда [math]\lt m_0,x\gt \in L[/math], но в [math]L[/math] по определению не может быть пары [math]\lt m,x\gt \,\![/math], которую допускает [math]m\,\![/math]. Таким образом, получаем противоречие.

Если [math]m_0\,\![/math] не допускает [math]\lt m_0,x\gt \,\![/math], то [math]\lt m_0,x\gt \,\![/math] не принадлежит языку [math]L\,\![/math]. Это значит, что либо [math]m_0\,\![/math] допускает [math]\lt m_0,x\gt \,\![/math], либо не допускает, используя памяти больше [math]f(|\lt m_0,x\gt |)\,\![/math]. Но [math]L \in DSPACE(f)[/math], поэтому [math]m_0\,\![/math] на любом входе [math]x\,\![/math] использует не более [math]f(|x|)\,\![/math] памяти. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, [math]L \notin DSPACE(f)[/math].

[math]L \in DSPACE(g)[/math], так как можно проэмулировать машину Тьюринга [math]m_1\,\![/math] такую, что [math]L(m_1)=L\,\![/math]. Для каждой пары [math]\lt m_3,x\gt \in L[/math] рассмотрим [math]m_3(\lt m_3,x\gt )\,\![/math]. Если [math]m_3\,\![/math] завершила работу и не допустила, то [math]m_1\,\![/math] допускает [math]\lt m_3,x\gt \,\![/math]. В другом случае не допускает. Так как любая такая машина использует памяти не более [math]f(|\lt m_3,x\gt |)\,\![/math], а [math] \lim_{n \rightarrow \infty} f(n)/g(n) = 0[/math], [math]m_1\,\![/math] будет использовать памяти не более [math]g(|\lt m_3,x\gt |)\,\![/math].


Получается, что [math]L \in DSPACE(g(n)) \ DSPACE(f(n))[/math] и [math]L \neq \empty[/math]. Следовательно, [math]DSPACE(g(n)) \neq DSPACE(f(n))[/math]

Теорема доказана.