Изменения

Перейти к: навигация, поиск

Теорема о ёмкостной иерархии

Нет изменений в размере, 14:45, 10 марта 2010
Доказательство
Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина тьюринга <math>m_0</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>.
23
правки

Навигация