Машина Тьюринга

[kwakush]

Разбираю по учебнику доказательство теоремы, есть там вот такое:

Цитата:

Преобразуем программу машины Тьюринга таким образом, чтобы на каждом шаге машина могла бы выполнять только одно из следующих действий: сдвинуть головку влево; сдвинуть головку вправо; записать новый символ без сдвига головки. Это легко можно сделать, заменив каждую команду $qa \to q'a'd$ на две команды $qa \to q'a'p$ и $q'a' \to q'a'd$.

Здесь $d \in \left\lbrace r, l, p \right\rbrace$ соответственно сдвиг вправо, влево, или стоим на месте.
А что, есть команда типа $q'a' \to ...$ уже существует? Тогда ничего добавить не получится и ничего хорошего не выйдет. Полагая, что здесь нужно ввести новое состояние и заменять на что-то такое $ qa \to q''a'p$ и $q''a' \to q'a'd$. В книге действительно опечатка, или я чего то не понимаю?

[whitefox]

Если МТ недетерминированная, то ошибки нет. В противном случае — вы правы.