Теорема о ёмкостной иерархии - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:44Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:41, 1 сентября 2022

2022-09-01T03:41:30Z

Дмитрий Мурзин: Дмитрий Мурзин переименовал страницу Теорема о емкостной иерархии в Теорема о ёмкостной иерархии: Ёфикация

2019-01-31T20:51:56Z

Дмитрий Мурзин переименовал страницу Теорема о емкостной иерархии в Теорема о ёмкостной иерархии: Ёфикация

Ulyantsev в 15:28, 2 июня 2010

2010-06-02T15:28:56Z

Joshik в 14:35, 23 марта 2010

2010-03-23T14:35:00Z

192.168.0.2: /* Доказательство */

2010-03-18T16:38:36Z

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

192.168.0.2: /* Доказательство */

2010-03-18T16:37:25Z

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

192.168.0.2: /* Доказательство */

2010-03-18T16:33:49Z

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

Perovskaya в 15:53, 18 марта 2010

2010-03-18T15:53:41Z

192.168.0.2: /* Доказательство */

2010-03-18T15:51:51Z

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

← Предыдущая		Версия 16:38, 4 сентября 2022
Строка 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'')) ≠ '''DSPACE'''(''f''(''n'')).		'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция\|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется '''DSPACE'''(''g''(''n'')) ≠ '''DSPACE'''(''f''(''n'')).

← Предыдущая		Версия 03:41, 1 сентября 2022
Строка 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'')) ≠ '''DSPACE'''(''f''(''n'')).		'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция\|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется '''DSPACE'''(''g''(''n'')) ≠ '''DSPACE'''(''f''(''n'')).

@@ Строка 1: / Строка 1: @@
 == Формулировка ==
-'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется <tex>DSPACE(g(n)) \ne DSPACE(f(n))</tex>.
+'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <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'')).
 == Доказательство ==

← Предыдущая		Версия 14:35, 23 марта 2010
Строка 19:		Строка 19:
	<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(\|\langle m_1,x\rangle\|)</tex> памяти, и не допустила, то <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>.		<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(\|\langle m_1,x\rangle\|)</tex> памяти, и не допустила, то <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>.

−	Таким образом получили, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))~~</tex> и <tex>L \neq \emptyset~~</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>, что и требовалось доказать.	+	Таким образом получили, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>, что и требовалось доказать.

@@ Строка 17: / Строка 17: @@
 Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
-<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе  <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <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>.
+<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе  <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <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>.
 Таким образом получили, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>, что и требовалось доказать.

← Предыдущая	Версия 20:51, 31 января 2019
(нет различий)

@@ Строка 5: / Строка 5: @@
 Зафиксируем функции <tex>f</tex> и <tex>g</tex>.
-Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex>.
+Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> и докажем, что <tex>L \notin DSPACE(f)</tex> и <tex>L \in DSPACE(g)</tex>.
 Допустим, что <tex>L \in DSPACE(f)</tex>, тогда существует детерминированная машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
@@ Строка 19: / Строка 19: @@
 <tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе  <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <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>.
-Получается, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>
+Таким образом получили, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>, что и требовалось доказать.

@@ Строка 3: / Строка 3: @@
 == Доказательство ==
-Зафиксируем <tex>f</tex> и <tex>g</tex>.
+Зафиксируем функции <tex>f</tex> и <tex>g</tex>.
-Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> .
+Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex>.
-Пусть <tex>L \in DSPACE(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
+Допустим, что <tex>L \in DSPACE(f)</tex>, тогда существует детерминированная машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
-Рассмотрим <tex>m_0(\langle m_0,x\rangle)</tex>.
+Рассмотрим выход машины <tex>m_0</tex> на входе <tex>\langle m_0,x\rangle</tex>.
-Пусть <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>. Тогда <tex>\langle m_0,x\rangle \in L</tex>, но в  <tex>L</tex> по определению не может быть пары <tex>\langle m,x\rangle</tex>, которую допускает <tex>m</tex>. Таким образом, получаем противоречие.
+Пусть <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>. Тогда <tex>\langle m_0,x\rangle \in L</tex>, но в  <tex>L</tex> по определению не может быть пары <tex>\langle m,x\rangle</tex>, которую допускает <tex>m</tex>. Таким образом, <tex>m_0</tex> не может допускать <tex>\langle m_0,x\rangle</tex>.
-Если <tex>m_0</tex> не допускает <tex>\langle m_0,x\rangle</tex>, то <tex>\langle m_0,x\rangle</tex> не принадлежит языку <tex>L</tex>. Это значит, что либо <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>, либо не допускает, используя памяти больше <tex>f(|\langle m_0,x\rangle|)</tex>. Но  <tex>m_0</tex> выбрана таким образом, что на любом входе <tex>x</tex> она использует не более <tex>f(|x|)</tex> памяти. Получаем противоречие.
+Если <tex>m_0</tex> не допускает <tex>\langle m_0,x\rangle</tex>, то <tex>\langle m_0,x\rangle</tex> не принадлежит языку <tex>L</tex>. Из определения это значит, что либо <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>, либо не допускает, используя памяти больше <tex>f(|\langle m_0,x\rangle|)</tex>. Но <tex>m_0</tex> выбрана таким образом, что на любом входе <tex>x</tex> она использует не более <tex>f(|x|)</tex> памяти. Получаем противоречие.
 Следовательно, такой машины не существует. Таким образом, <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_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <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>.
+<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе  <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <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>.
 Получается, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>
 Теорема доказана.