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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
== Формулировка ==
 
== Формулировка ==
 
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется '''DSPACE'''(''g''(''n'')) &ne; '''DSPACE'''(''f''(''n'')).
 
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется '''DSPACE'''(''g''(''n'')) &ne; '''DSPACE'''(''f''(''n'')).

Текущая версия на 19:38, 4 сентября 2022

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

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

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

Зафиксируем функции [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 \notin DSPACE(f)[/math] и [math]L \in DSPACE(g)[/math].

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

Рассмотрим выход машины [math]m_0[/math] на входе [math]\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]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]L[/math] можно сопоставить машину Тьюринга [math]m_0[/math], распознающую [math]L[/math] и такую, что на любом входе [math]\langle m_1,x\rangle \in L[/math] [math]m_0[/math] будет работать аналогично [math]m_1[/math]. Если [math]m_1[/math] завершила работу, используя не более [math]f(|\langle m_1,x\rangle|)[/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], поэтому начиная с некоторого [math]n[/math], [math]m_1[/math] будет использовать памяти не более [math]g(|\langle m_1,x\rangle|)[/math].

Таким образом получили, что [math]L \in DSPACE(g(n)) \setminus DSPACE(f(n))[/math]. Следовательно, [math]DSPACE(g(n)) \neq DSPACE(f(n))[/math], что и требовалось доказать.