Машина Тьюринга, узнать какую функцию вычисляет

[nbyte]

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

Цитата:

Какую функцию вычисляет следующая машина Тьюринга

$$\[\begin{array}{l} \delta ({q_0},0) = ({q_1},0,R), \\ \delta ({q_0},1) = ({q_2},1,N), \\ \delta ({q_0},b) = ({q_0},b,R), \\ \\ \delta ({q_1},0) = ({q_2},0,N), \\ \delta ({q_1},0) = ({q_1},1,R), \\ \delta ({q_1},0) = ({q_1},b,R), \\ \\ F = \{ {q_2}\} \\ \end{array}\] $$

Машина Тьюрина у меня:
Состоит из одной ленты.
$\delta$ у меня функция перехода.
Допускаются команды:

• Вправо - R
• Влево - L
• В некуда - N

$q_1, q_2... q_n$ - состояния
$F$ - множество конечных состояний.

[Профессор Снэйп]

nbyte в сообщении #261575 писал(а):

В некуда - N

Это как? Через пятое измерение за пределы Вселенной?

Я Вам уже один раз писал, не понимаю, сколько можно повторять одно и то же... Если хотите, чтобы Вам помогли --- пишите все необходимые определения. Что значит "машина вычисляет функцию"? Каков формат входных данных? Каков формат выходныъх данных?

-- Пт ноя 13, 2009 15:58:36 --

У Вас там, помимо всего прочего, целых три значения $\delta(q_1,0)$. Это опечатка или машина недетерминированная?

[nbyte]

Цитата:

Это опечатка или машина недетерминированная?

Машина прекращает работу при N.

Цитата:

Каков формат выходныъх данных?

Последовательность символов из 1,0 ограниченная с двух сторон бесконечным числом пустых элементов.
При начальном положении каретка смотрит на первый не пустой элемент слева.

[Maslov]

nbyte в сообщении #261598 писал(а):

Цитата:
Это опечатка или машина недетерминированная?

Машина прекращает работу при N.

Запись $\delta({q_0},0) = ({q_1},0,R)$ означает, что если МТ находится в состоянии $q_0$, и символ, на который указывает каретка, равен $0$, то МТ выводит в текущую позицию символ $0$, сдвигает каретку вправо ($R$) и переходит в состояние $q_1$.

Для состояния $q_1$ у Вас заданы 3 команды

nbyte в сообщении #261575 писал(а):

$$\[\begin{array}{l} \delta ({q_1},0) = ({q_2},0,N), \\ \delta ({q_1},0) = ({q_1},1,R), \\ \delta ({q_1},0) = ({q_1},b,R)\} \\ \end{array}\] $$

причём все три - для случая, когда символ под кареткой равен $0$.

Т.о., поведение машины в состоянии $q_1$ является недетерминированным: встретив в этом состоянии символ $0$, она может
1. оставить $0$ в текущей позиции и, не сдвигая каретку ($N$), перейти в состояние $q_2$, либо
2. заменить $0$ на $1$, сдвинуть каретку вправо ($R$) и перейти в состояние $q_1$, либо
3. заменить $0$ на $b$, сдвинуть каретку вправо ($R$) и перейти в состояние $q_1$.
При этом реакция на символы $1$ и $b$ в состоянии $q_1$ не задана.

Вопрос: это действительно недетерминированная машина, или Вы просто условие неверно списали?

[nbyte]

Цитата:

Вопрос: это действительно недетерминированная машина, или Вы просто условие неверно списали?

Пардон, я тут просто на форум не правильно написал.
Тут будет

$$\[\begin{array}{*{20}{c}} {\delta ({q_0},0) = ({q_1},0,R),} \\ {\delta ({q_0},1) = ({q_2},1,N),} \\ {\delta ({q_0},b) = ({q_0},b,R),} \\ {} \\ {\delta ({q_1},0) = ({q_2},0,N),} \\ {\delta ({q_1},1) = ({q_1},1,R),} \\ {\delta ({q_1},b) = ({q_1},b,R),} \\ {} \\ {F = \{ {q_2}\} } \\ \end{array}\] $$

Вроде-бы больше ошибок нет.

[Maslov]

Теперь давайте попробуем разобраться с состояниями. Начнём с $q_0$, которое, судя по всему, является начальным (хотя у Вас про это нигде сказано). Попробуйте на словах объяснить, как МТ ведёт себя в этом состоянии.

Про

nbyte в сообщении #261598 писал(а):

При начальном положении каретка смотрит на первый не пустой элемент слева.

забудьте (это Вы, скорее всего, сами придумали )