Здравствуйте! Учусь на первом курсе, по матлогике, дали такие задачи.
Не подскажете в правильном ли я начинала решать их.
Реализовать машину Тьюринга и алгорифм Маркова:
Добавить в начало слова 1, если разность между количеством нулей и количеством единиц делится на 3.
При реализации машины Тьюринга, я так поняла, разность между количеством

и

можно посчитать по модулю 3. то есть если

, то

, если

, то

т все считается за один проход). Поступала вот так:
Будем следить за количеством 0 минус количество 1 по модулю 3. Остатки 0, 1, 2 от деления на 3 будем запоминать в состояниях q0, q1, q2, соответственно. Рассмотрим функции

и

, определяемые следующим образом.

Рассмотрим такие правила.

для всех

.
Тогда после одного прохода, начиная с состояния

, машина будет снова в состоянии

тогда и только тогда, когда разность между количеством 0 и количеством 1 делится на 3.
А вот алгорифмы Маркова, начала изучать недавно и не понимаю как реализовать правило которое считает разность количества между 0 и 1. Была идея сделать соотношения пар 0 и 1, но все равно не получается.
Буду благодарна любой помощи, спасибо