Машины Тьюринга

[arseniiv]

(2 cool.phenon.)

Не-не, я имел в виду, что с таким отображением было бы, наверно, проще — как строится частично рекурсивная функция, вычисляющая умножение, понятнее, чем построение соответствующей МТ, утопающее в императивных деталях. Но выводить то отображение в явном виде для нахождения МТ, вычисляющих умножение, наверно, как из пушки по воробьям.

[Xaositect]

cool.phenon в сообщении #721948 писал(а):

Xaositect
Кажется, я догадываюсь, как это нужно сделать. Идем вправо по циклу, на каждом шаге возвращаемся в самый конец, дописываем единицу и идём дальше. Но как дописать в нужном месте нуль?

Давайте подумаем.
Раз мы постоянно ходим туда-сюда, нам обязательно надо запоминать, какие единицки мы уже скопировали, а какие еще нет.
Самый простой способ это сделать, если кроме ноликов и единичек у нас ничего нет - это откладывать единички в сторону.
То есть первое копирование одной единички будет выглядеть примерно так (отложили единичку влево, потом записали ее копию в конец):
$11\dots100\dots\mapsto101\dots100\dots\mapsto101\dots1010\dots$.
А каждое следующее - примерно так:
$1\dots1011\dots101\dots10\dots\mapsto1\dots1101\dots101\dots10\dots\mapsto1\dots1101\dots101\dots110\dots$.

[cool.phenon]

(Оффтоп)

arseniiv
Дело в том, что я же не просто так всем этим маюсь - это будет экзамен. А там преподавателю подавай всё именно в таком виде, одних только слов, что вот здесь будет одна функция, а вот там другая, а потом что-то еще, мало. Текстом поддерживаться всё должно. И, желательно, верным.

Xaositect
Ага, значит, нужно все скопированные единицы влево, а еще по одной дописывать справа, я правильно Вас понял?

[Sonic86]

cool.phenon, можно я свой вариант частично напишу (для определения четности)?
Проще сделать так:
$1X_1\to 0RX_2$
$1X_2\to 0RX_1$
Стирая 2 единички идем вправо, причем у МТ всего 2 состояния, одно соответствует четным числам, 2-е - нечетным. Теперь надо закончить обработку - написать что делать, когда встретиться нолик: в этом случае мы возвращаемся назад и пишем ответ. Так мы возвращаемся назад:
$0X_2\to0LX_2$
$0X_1\to0LX_1$
Остается обработать установку головки в нужное состояние + написание ответа, исходя из состояния.

cool.phenon в сообщении #721994 писал(а):

Вначале стрелка стоит в начале строки единиц, поэтому начинаем и двигаем вправо.
$1X_{1}\to 1RX_{2}$.
Далее проверяем следующую единицу. Если там её нет, можно оставаться на месте, можно идти вправо - без разницы. То есть, число нечётное. Если единица - идём вправо. $0X_{2}\to 0SX_{1}$
$1X_{2}\to 1RX_{3}$.
Теперь вытираем 2 нуля.
$1X_{3}\to 1LX_{4}$.
$1X_{4}\to 0LX_{5}$.
$1X_{5}\to 0LX_{6}$.
В состоянии X_{6} двигаемся вправо до первой единицы.
$0X_{6}\to 0RX_{6}$
Если единица встретилась, начинаем всё по новой, переходим в состояние 1.
$1X_{6}\to 1RX_{1}$

Уже больше похоже на работающий вариант. Только у Вас по-прежнему не использовано заключительное состояние и тогда МТ не остановится (или нужно переинтерпетировать работу по инструкциям так: если соответствующей инструкции не найдено (конкретно нет инструкции для $0X_1$, эта комбинация встречается после исполнения команды $0X_{2}\to 0SX_{1}$), то это равносильно инструкции $0X_1\to 0SX_0$. И тогда все хорошо).
И еще технический, но нужный момент: у Вас головка ползет вправо, а когда стирание числа завершается, она встает практически там где была, а ее, по идее, надо передвинуть в начало. А хотя у Вас начала же нет, тогда, наверное, можно не передвигать даже.

[arseniiv]

(Оффтоп)

cool.phenon в сообщении #722018 писал(а):

arseniiv
Дело в том, что я же не просто так всем этим маюсь - это будет экзамен. А там преподавателю подавай всё именно в таком виде, одних только слов, что вот здесь будет одна функция, а вот там другая, а потом что-то еще, мало. Текстом поддерживаться всё должно. И, желательно, верным.

Когда построено то отображение, просто появляется алгоритм получения МТ из «более простых» других, когда понятно, как строится функция, которую машина должна вычислять. Минус в том, что надо будет описать на экзамене получение этого отображения и не забыть используемый его вид, т. к. разных таких отображений можно получить кучу. Так что в вашем случае это не подойдёт, но я и не думал с самого начала, что это тут уместно. Это был, скорее, вопрос к остальным.

[cool.phenon]

Sonic86
Да, конечно.
Только вот я немного не понял в вашей программе, допустим у нас три единички. Первым шагом мы вытерли первую и пошли направо. Вторым шагом мы вытерли еще одну единичку, идём направо и переходим в 1 состояние. Но впереди единица. Значит будет выполняться $1X_{1}$. То есть, мы вытерли третью единицу. Выходит, что у нас вообще единиц не осталось. Поправьте меня, может я где-то ошибаюсь?

[Sonic86]

cool.phenon в сообщении #722025 писал(а):

Только вот я немного не понял, допустим у нас три единички. Первым шагом мы вытерли первую и пошли направо. Вторым шагом мы вытерли еще одну единичку, идём направо и переходим в 1 состояние. Но впереди единица. Значит будет выполняться $1X_{1}$. То есть, мы вытерли третью единицу. Выходит, что у нас вообще единиц не осталось. Поправьте меня, может я где-то ошибаюсь?

Да, моя МТ весь вход в процессе вычисления стирает, а уже потом, в пустую строку пишет ответ в зависимости от своего состояния. Потом, если нам не надо возвращаться, можно просто добавить команды $0X_2\to 1X_0$ и $0X_1\to 0X_0$ и все.
Т.е. запись целиком будет такая:
$1X_1\to 0RX_2$
$1X_2\to 0RX_1$
$0X_2\to 1X_0$
$0X_1\to 0X_0$
(опять же, если у Вас $X_0$ нету - берите $X_3$ вместо $X_0$). У меня она пишет $1$, если число четное, иначе - нечетное. Но можно легко сменить 0 на 1 и 1 на 0.

[Xaositect]

cool.phenon в сообщении #722018 писал(а):

Xaositect
Ага, значит, нужно все скопированные единицы влево, а еще по одной дописывать справа, я правильно Вас понял?

Так можно.
Можно еще стирать по одной слева и дописывать две в разные группы справа.
По-разному можно.