Дизайн состояний машины Тьюринга

Question

Я хочу разработать машину Тьюринга, которая принимает максимум 3 0. Теперь я разработал один, который принимает сверхурочное состояние, он видит 1, 2 и 3 0 и отклоняет любые дальнейшие 0. Я хотел знать, нормально ли для ТМ переходить в состояние принятия из 3 разных состояний?

Answer 1

Да, это прекрасно. Даже если вам нужна детерминированная машина, несколько переходов в одно и то же состояние вполне подойдут. Если несколько исходящих переходов читают один и тот же символ, машина больше не является детерминированной. Но даже это не проблема для недетерминированных ТМ.