Изменения
→Странное ограничение: Новая тема
Из этой теоремы делаются очень глубокие и важные выводы. Про них тоже обязательно надо написать.
: «который использует операции релятивизации» — чё это за бредятина? [[Участник:Kirelagin|Кирилл Елагин]] 18:40, 7 мая 2012 (GST)
== Странное ограничение ==
Я правильно понимаю, что на <tex>i</tex>-ом шаге <tex>n</tex> не зависит от <tex>M_i</tex>? Тогда я не понимаю: что плохого в том, что машина <tex>M_i</tex> не разрешает слово <tex>1^n</tex> за <tex>2^{n - 1}</tex> шагов, потому как временной полином для этой машины вполне может выглядеть как:
<tex>p(k) = 2^n k </tex>
