Номенклатура машины Тьюринга

[qx87]

Задача звучит так:

МТ с внешним алфавитом $\{0, 1\}$ и алфавитом внутренних состояний $\{p_1, p_2, \ldots, p_n\}$ определяется следующей функциональной таблицей:



Определите, в какое слово перерабатывает МТ каждое из следующих слов (в начальный момент времени МТ находится в первом состоянии и обозревает крайнюю правую ячейку, в которой записан пустой символ 0, а в следующей слева ячейке уже записана 1).

а) 0111011101110
б) 0110111010
в) 01110110
г) 011011110

======

Видимо, у меня какое-то недопонимание с определением МТ (или у автора задания). Я понял так, что здесь лента полубесконечная, но простирается влево, $d_1$ означает переход влево, $d_{-1}$ -- переход вправо. Ибо если считать $d_1$ переходом вправо, то МТ переходит за крайнюю правую позицию на первом шаге для каждого слова.

Однако тогда получается, что поскольку все данные слова оканчиваются на 10, на каждом из них МТ пройдёт последовательно состояния 1-2-3-4-5, в пятом состоянии будет обозревать крайнюю правую ячейку. За это время последние две цифры 10 она заменит на 01 (на другие даже на посмотрит) и затем попытается перейти в состояние 6 и одновременно сдвинуть головку за крайнюю правую позицию. Получается, что эта МТ неприменима ко всем данным числам. Такое, конечно, возможно, но "меня терзают смутные сомнения".

Я нигде не ошибаюсь?

[Brukvalub]

Как минимум, дико выглядит наличие состояния $p_{15}$ внизу самой последней колонки состояний, поскольку больше нигде это состояние не упоминается.

qx87 в сообщении #1213787 писал(а):

Я понял так, что здесь лента полубесконечная, но простирается влево, $d_1$ означает переход влево, $d_{-1}$ -- переход вправо.

Это вы "по гуглу" учитесь? Ведь иначе вы бы обязательно знали, как обозначается команда перемещения каретки, упомянутая в задании, такие вещи обязательно разъясняются на лекциях и семинарах.

[qx87]

Я в своё время учился вот по этим книгам. Их же в своё время оцифровал и выложил в открытый доступ. Лектор мой по дискретной математике, Алексей Иванович Белоусов, -- автор одноимённого учебника (номер XIX) из этой серии. У меня даже этот учебник есть свой, с его автографом (который он ставит только после пятёрки на экзамене). У нас переходы обозначались буквами S, L, R, что исключало всякую неоднозначность. И как работать с нашими, "бауманскими" машинами Тьюринга я хорошо знаю.

Здесь же в задании всё по-другому, ничего не пояснено, приходится додумывать. В этом и прошу помощи.

Состояние $p_{15}$, как я понимаю, заключительное. Поэтому и не упоминается больше нигде.

[3D Homer]

qx87 в сообщении #1213787 писал(а):

Я понял так, что здесь лента полубесконечная, но простирается влево, $d_1$ означает переход влево, $d_{-1}$ -- переход вправо.

Почему не считать, что лента простирается вправо, $d_1$ означает переход вправо, $d_{-1}$ -- переход влево? Такое соглашение более стандартно.

[arseniiv]

Потому что в задании написано, что

qx87 в сообщении #1213787 писал(а):

в начальный момент времени МТ находится в первом состоянии и обозревает крайнюю правую ячейку

Вообще, конечно (здравствуйте, я К. О.), перво-наперво надо узнать, откуда такое задание, и нет ли там чего-то ещё кроме этого задания. Если нет, а не ну ли его тогда?

[qx87]

3D Homer в сообщении #1213895 писал(а):

Почему не считать, что лента простирается вправо, $d_1$ означает переход вправо, $d_{-1}$ -- переход влево? Такое соглашение более стандартно.

Я ж написал:

qx87 в сообщении #1213787 писал(а):

Ибо если считать $d_1$ переходом вправо, то МТ переходит за крайнюю правую позицию на первом шаге для каждого слова.

-- 03.05.2017, 20:25 --

arseniiv в сообщении #1213923 писал(а):

Вообще, конечно (здравствуйте, я К. О.), перво-наперво надо узнать, откуда такое задание, и нет ли там чего-то ещё кроме этого задания. Если нет, а не ну ли его тогда?

Здравия желаю, товарищ капитан!
Само собой, в этом направлении я тоже работаю. Но в силу специфичности моей ситуации матожидание времени получения ответа с той стороны на $N$ порядков может превосходить оное времени расколупывания истины коллективным разумом. И на $n$ порядков -- собственным :)

[arseniiv]

Не завидую вам.

[Brukvalub]

(Оффтоп)

qx87 в сообщении #1213926 писал(а):

Но в силу специфичности моей ситуации матожидание времени получения ответа с той стороны на $N$ порядков может превосходить оное времени расколупывания истины коллективным разумом. И на $n$ порядков -- собственным :)

Решаете за копейку малую контрольные выдающимся дубкам, которые только и способны, что скопировать и выслать текст своей к.р., но дать пояснения не могут, поскольку "он эти куклы десять минут назад впервые увидел"?

[qx87]

Да. Пишете забесплатно комменты, не имеющие смысла?

[Brukvalub]

(Оффтоп)

qx87 в сообщении #1213968 писал(а):

Да. Пишете забесплатно комменты, не имеющие смысла?

Много среди нас тех, кто дюже не любит жлобов, извращающих смысл высшего образования, решая за деньги дубкам их д.з., поэтому смысл у моего комментария и вашего ответа есть. Вполне недвусмысленный смысл.

[qx87]

Подскажи тогда, как по-твоему вернуть его, этот смысл?

[Lia]

qx87
Замечание за фамильярность. На форуме принято общение на "Вы".

qx87 в сообщении #1213997 писал(а):

как по-твоему вернуть его, этот смысл?

А он никуда не ушел.

[qx87]

Lia в сообщении #1214127 писал(а):

qx87
Замечание за фамильярность. На форуме принято общение на "Вы".

Жлобами людей на форуме тоже принято называть, это не считается фамильярностью? За это участник замечание не получит, я правильно вас понимаю?

[Lia]

qx87
Большая просьба не выяснять проблемы, связанные с модерированием и т.п. в тематических разделах. Для этого есть ЛС и раздел "Работа форума". Вы можете обратиться туда.

[qx87]

Не буду. Я вас понял: жлобами можно, на ты -- нельзя. Всё же просто.

Тему можно закрывать, всё равно стараниями гражданина она скатилась незнамо во что.