Обсуждение:Недетерминированные вычисления

Какая мощность может быть у правой части оператора [math]\leftarrow ?[/math]? Дмитрий Шевченко 17:52, 4 июня 2012 (GST)

Какая угодно, но конечная. Она ограничена размером машины Тьюринга. Это же как бы недетерминированный переход. Сколько в машине переходов есть, такая и мощность. С поправкой на то, правда, что тут программа, а не машина, и один такой оператор может скрывать в себе несколько переходов аналогичной машины.

В том-то и дело, что «несколько переходов» может стать неполиномиальной величиной. К примеру, если в правой части множество мощности [math]2^{2^n}[/math], то, считая для простоты, что один переход соответствует одному биту, нам потребуется [math]2^n[/math] переходов МТ. Дмитрий Шевченко 19:12, 4 июня 2012 (GST)