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