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