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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 11: Строка 11:
 
Рассмотрим <math>m_0(<m_0,x>)</math>. <math>m_0</math> не может допускать <math><m_0,x></math> в силу определения. Если бы она допускала, то <math><m_0,x> \in L</math>. Получили противоречие. Если <math>m_0</math> не допускает <math><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>m_0</math> не допускает <math><m_0,x></math>, то она допускает, используя больше памяти. Следовательно такой машины не существует.
  
<math>L \in DSPACE(g)</math> так как можно проэмулировать <math>m</math>.
+
<math>L \in DSPACE(g)</math>, так как можно проэмулировать <math>m</math>.
  
 
Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>.
 
Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>.
  
 
Теорема доказана.
 
Теорема доказана.

Версия 14:45, 10 марта 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]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]m_0[/math] не допускает [math]\lt m_0,x\gt [/math], то она допускает, используя больше памяти. Следовательно такой машины не существует.

[math]L \in DSPACE(g)[/math], так как можно проэмулировать [math]m[/math].

Получается, что [math]L \in DSPACE(g(n)) \ DSPACE(f(n))[/math].

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