Машина Тьюринга и алгорифм Маркова

[khammisha]

Здравствуйте! Учусь на первом курсе, по матлогике, дали такие задачи.
Не подскажете в правильном ли я начинала решать их.

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

При реализации машины Тьюринга, я так поняла, разность между количеством $0$ и $1$ можно посчитать по модулю 3. то есть если $1$, то $+1$, если $0$, то $-1$ т все считается за один проход). Поступала вот так:

Будем следить за количеством 0 минус количество 1 по модулю 3. Остатки 0, 1, 2 от деления на 3 будем запоминать в состояниях q0, q1, q2, соответственно. Рассмотрим функции $f(r)$ и $g(r)$, определяемые следующим образом.
$\begin{array}{c|c|c|c}r&0&1&2\\\hline f(r)&1&2&0\\\hline g(r)&2&0&1\end{array}$


Рассмотрим такие правила.
\begin{align*}q_r\;0&\to q_{f(r)}\;0\;R\\q_r\;1&\to q_{g(r)}\;1\;R\end{align*}

для всех $r=0,1,2$.
Тогда после одного прохода, начиная с состояния $q_0$, машина будет снова в состоянии $q_0$ тогда и только тогда, когда разность между количеством 0 и количеством 1 делится на 3.
А вот алгорифмы Маркова, начала изучать недавно и не понимаю как реализовать правило которое считает разность количества между 0 и 1. Была идея сделать соотношения пар 0 и 1, но все равно не получается.

Буду благодарна любой помощи, спасибо

[gevaraweb]

khammisha в сообщении #1501482 писал(а):

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

Задача, по моему, проще, чем кажется на первый взгляд. Не вводите никаких функций, просто распишите матрицу переходов состояний. Например, вы в состоянии $q_0$ (оно же и начальное). И тут вы видите 0. В какое состояние вы перейдете? Если же в состоянии $q_0$ вы видите 1, в какое состояние вы перейдете? И т.д. Это считая, что мы двигаемся справа налево.

Наконец, вы в состоянии $q_0$ видите элемент пусто. Что делаем?
Или вы в состоянии $q_1$ видите элемент пусто. Что делаем?...
Или вы в состоянии $q_2$ видите элемент пусто. Что делаем?...

Единственное замечание, обычно принято обозначать за $q_0$ конечное состояние, и иногда еще именно $q_1$ - начальное состояние. Возможно, придется переобозначить, хотя и немного теряется наглядность.
Решив задачу, можете проверить работы на тренажере . Отличный тренажер, пригодился мне при проведении занятий по матлогике.