http://david-bakesh.livejournal.com/ ([identity profile] david-bakesh.livejournal.com) wrote in [personal profile] a_shen 2017-04-02 08:29 pm (UTC)

Re: В порядке противорвотно-освежительного

Спасибо.

Ваш ответ дал мне возможность четко выделить как раз то, что меня интересует:

"Размер алфавита и число состояний (если только не ограничивать их обоих, от чего модель перестаёт быть универсальной) меняют сложность в константу раз" (т.е. ничего не меняют, в сущности).

Вопрос такой: как, по-Вашему, могла бы выглядеть "МИНИМАЛЬНАЯ (в плане размера алфавита и числа состояний ) НЕ Универсальная" МТ, всё ещё способная вычислить синус?
При каких ограничениях потеряется полиномиальность (или никогда)?
Сколь отличны ответы на оба эти вопроса для ВТМ?

Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting