171
правка
Изменения
Нет описания правки
[[Участник:Shevchen|Дмитрий Шевченко]] 17:52, 4 июня 2012 (GST)
: Какая угодно, но конечная. Она ограничена размером машины Тьюринга. Это же как бы недетерминированный переход. Сколько в машине переходов есть, такая и мощность. С поправкой на то, правда, что тут программа, а не машина, и один такой оператор может скрывать в себе несколько переходов аналогичной машины.
:: В том-то и дело, что «несколько переходов» может стать неполиномиальной величиной. К примеру, если в правой части множество мощности <tex>2^{2^n}</tex>, то, считая для простоты, что один переход соответствует одному биту, нам потребуется <tex>2^n</tex> переходов МТ. [[Участник:Shevchen|Дмитрий Шевченко]] 19:12, 4 июня 2012 (GST)
