|
|
| Строка 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>n</tex> шагов машины Тюринга на другой машине Тьюринга за время <tex>t(n)</tex>. | | Пусть можно просимулировать <tex>n</tex> шагов машины Тюринга на другой машине Тьюринга за время <tex>t(n)</tex>. |
Текущая версия на 19:06, 4 сентября 2022
Формулировка
Пусть можно просимулировать [math]n[/math] шагов машины Тюринга на другой машине Тьюринга за время [math]t(n)[/math].
Для любых двух конструируемых по времени функций [math]f\,\![/math] и [math]g\,\![/math] таких, что [math] \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0[/math], выполняется DTIME(g(n)) ≠ DTIME(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 \in DTIME(f)[/math], тогда для него есть машина Тьюринга [math]m_0[/math] такая, что [math]L(m_0)=L\,\![/math].
Рассмотрим [math]m_0( \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]m_0[/math]. Но в [math]L[/math] по определению не может быть пары [math] \langle m_0,x \rangle [/math], которую допускает [math]m_0[/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]L \in DTIME(f)[/math], поэтому [math]m_0[/math] на любом входе [math]x[/math] работает не более [math]f(|x|)[/math] времени. Получаем противоречие.
Следовательно такой машины не существует. Таким образом, [math]L \notin DTIME(f)[/math].
[math]L \in DTIME(g)[/math]. Возьмем такую машину Тьюринга [math]m_1[/math], которой дается на вход пара [math] \langle m_2,x \rangle \in L[/math] и она симулирует [math]f(| \langle m_2,x \rangle |)[/math] шагов машины [math]m_2[/math] на входе [math]x[/math]. Если [math]m_2[/math] завершила работу и не допустила, то [math]m_1[/math] допускает [math] \langle m_2,x \rangle [/math]. В другом случае не допускает. [math]L(m_1) = L[/math] и [math]m_1[/math] будет работать не более [math]g(| \langle m_2,x \rangle |)[/math] времени, так как по условию [math] \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0[/math].
Получается, что [math]L \in DTIME(g(n)) \setminus DTIME(f(n))[/math] и [math]L \neq \emptyset[/math]. Следовательно, [math]DTIME(g(n)) \neq DTIME(f(n))[/math]
Теорема доказана.
