https://discopal.ispras.ru/index.php?action=history&feed=atom&title=DSPACE 2026-04-26T20:12:18Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=DSPACE&diff=580&oldid=prev 2008-08-04T09:55:46Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Класс ''DSPACE(s(n))'', означает класс задач, <br /> разрешимых на [[Машина Тьюринга|машине Тьюринга]],<br /> использующей не более ''s(n)'' ячеек.<br /> <br /> Более формально:<br /> Язык &lt;amsmath&gt;L \subset \Sigma^*&lt;/amsmath&gt; принадлежит классу &lt;amsmath&gt;{\cal DSPACE}(s(n))&lt;/amsmath&gt;,<br /> если существует [[машина Тьюринга]] ''T'', разрешающая данный язык, и число используемых ею ячеек ленты на входе длины ''n'' не превышает ''s(n)''.<br /> <br /> [[Category:Классы сложности]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop