Изменения

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

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

Нет изменений в размере, 18:27, 18 марта 2010
Доказательство
Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
<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>, поэтому начиная с некоторого <tex>n<\/tex> <tex>m_1</tex> будет использовать памяти не более <tex>g(|\langle m_1,x\rangle|)</tex>.
83
правки

Навигация