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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 17: Строка 17:
 
Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
 
Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
  
<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>.
+
<tex>L \in DSPACE(g)</tex>, так как можно представить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex>. Для каждой пары  <tex>\langle m_1,x\rangle \in L</tex> запускаем <tex>m_1</tex>. <tex>m_0</tex> на данном входе будет работать аналогично. Если <math>m_1</math> завершила работу и не допустила, то <tex>m_0</tex> допускает <tex>\langle m_1,x\rangle</tex>. В другом случае не допускает. Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>. <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, поэтому начиная с некоторого n <math>m_1</math> будет использовать памяти не более <tex>g(|\langle m_1,x\rangle|)</tex>.
  
  

Версия 18:25, 18 марта 2010

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

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f[/math] и [math]g[/math] таких, что [math] \lim \limits_{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 = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )[/math] не допускает, используя не более [math] f(|\langle m,x\rangle|)[/math] памяти [math]\}[/math] .

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

Рассмотрим [math]m_0(\langle m_0,x\rangle)[/math].

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

Если [math]m_0[/math] не допускает [math]\langle m_0,x\rangle[/math], то [math]\langle m_0,x\rangle[/math] не принадлежит языку [math]L[/math]. Это значит, что либо [math]m_0[/math] допускает [math]\langle m_0,x\rangle[/math], либо не допускает, используя памяти больше [math]f(|\langle m_0,x\rangle|)[/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_0[/math], распознающую [math]L[/math]. Для каждой пары [math]\langle m_1,x\rangle \in L[/math] запускаем [math]m_1[/math]. [math]m_0[/math] на данном входе будет работать аналогично. Если [math]m_1[/math] завершила работу и не допустила, то [math]m_0[/math] допускает [math]\langle m_1,x\rangle[/math]. В другом случае не допускает. Любая такая машина использует памяти не более [math]f(|\langle m_1,x\rangle|)[/math]. [math] \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0[/math], поэтому начиная с некоторого n [math]m_1[/math] будет использовать памяти не более [math]g(|\langle m_1,x\rangle|)[/math].


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

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