помогите разобраться с машиной тьюринга...

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

Val Crazy в сообщении #221405 писал(а):

поправьте, если я ошибаюсь - при переходе в состояние 0 МТ останавливает работу

Более-менее стандартным соглашением считается, что машина Тьюринга останавливается, когда переходит в состояние $q_0$ (то есть $q(0)$ в Ваших обозначениях). Если это то, что Вы имели в виду, то да, Вы правы. А если под нулём Вы понимали символ, записанный в ячейке ленты, на которую указывает головка, то нет.

Обозначение $\Lambda$ для символа пустой ячейки тоже более-менее стандартно. Но здесь, похоже, специальных символов пустых ячеек не предусмотрено и ячейка считается "пустой", если в ней записан $0$. В таком разе /\ --- это, скорее всего, буква "Л", дающая машине команду двигать головку влево (хотя стандартно пишут не Л, а L).

Я бы переписал Вашу программу (если я её правильно понял) так:

$q_10 \to q_20$
$q_11 \to q_21$
$q_20 \to q_01$
$q_21 \to q_11L$

Стартуем мы из состояния $q_1$, головка указывает на первую единицу в слове $1110001$, остальные ячейки ленты (вероятно, бесконечной в оба конца), заполнены нулями. Если всё это верно, то будет происходить следующее.

1) После первого шага работы головка перейдёт из состояния $q_1$ в состояние $q_2$, никуда не сдвигаясь и ничего не меняя на ленте.

2) После второго шага мы перейдём в состояние $q_1$, сдвинувшись на одну ячейку влево. На ленте ничего не поменяется. После этого действия головка будет указывать на ячейку, в которой записан $0$.

3) После третьего шага состояние поменяется с $q_1$ на $q_2$, головка никуда не сдвинется и на ленте ничего не изменится.

4) Наконец, на четвёртом шаге машина переписывает $0$, содержащийся в ячейке, на которую указывает головка, на $1$, и переходит в состояние $q_0$, то есть останавливается. На ленте в результате оказывается записанным слово $11110001$.

[Val Crazy]

Цитата:

4) Наконец, на четвёртом шаге машина переписывает $0$, содержащийся в ячейке, на которую указывает головка, на $1$, и переходит в состояние $q_0$, то есть останавливается. На ленте в результате оказывается записанным слово $11110001$.

а почему именно так?
у меня при таком раскладе получалось слово: 1110011

AKM:

Набор формул!

[Val Crazy]

Профессор Снэйп
я кажется поняла почему Вы написали итоговое слово 11110001, но разве стандартное положение головки крайнее левое, а не крайнее правое?

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

Val Crazy в сообщении #221819 писал(а):

Профессор Снэйп
я кажется поняла почему Вы написали итоговое слово 11110001, но разве стандартное положение головки крайнее левое, а не крайнее правое?

Честно говоря, общепринятых стандартов тут вообще не существует. Но крайне левое всё же встречается чаще.

[Val Crazy]

Цитата:

Честно говоря, общепринятых стандартов тут вообще не существует. Но крайне левое всё же встречается чаще.

понятно, спасибо!