Ваш ответ дал мне возможность четко выделить как раз то, что меня интересует:
"Размер алфавита и число состояний (если только не ограничивать их обоих, от чего модель перестаёт быть универсальной) меняют сложность в константу раз" (т.е. ничего не меняют, в сущности).
Вопрос такой: как, по-Вашему, могла бы выглядеть "МИНИМАЛЬНАЯ (в плане размера алфавита и числа состояний ) НЕ Универсальная" МТ, всё ещё способная вычислить синус? При каких ограничениях потеряется полиномиальность (или никогда)? Сколь отличны ответы на оба эти вопроса для ВТМ?
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
Re: В порядке противорвотно-освежительного
Date: 2017-04-02 08:29 pm (UTC)Ваш ответ дал мне возможность четко выделить как раз то, что меня интересует:
"Размер алфавита и число состояний (если только не ограничивать их обоих, от чего модель перестаёт быть универсальной) меняют сложность в константу раз" (т.е. ничего не меняют, в сущности).
Вопрос такой: как, по-Вашему, могла бы выглядеть "МИНИМАЛЬНАЯ (в плане размера алфавита и числа состояний ) НЕ Универсальная" МТ, всё ещё способная вычислить синус?
При каких ограничениях потеряется полиномиальность (или никогда)?
Сколь отличны ответы на оба эти вопроса для ВТМ?