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

[cool.phenon]

Здравствуйте, уважаемые участники форума.Мне нужно научиться умножать, проверять на чётность,возводить в $n$ степень числа в унарном коде на машине Тьюринга. Идей - 0. Умею разве что добавлять целое число, проверять простейшие условия. Везде уже готовые коды, в которых обозначения меня приводят в ступор - куча решёток, плюсиков, чёрточек. Умею вот в таком виде работать : $1SX_{1}$ и т.д. Остальное мне совершенно непонятно. Прошу помочь разобраться с этой темой.

[Sonic86]

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

Умею вот в таком виде работать : $1SX_{1}$ и т.д.

А что это за вид? Обычно же вид такой: $a_iq_j\to a_kq_rT, T\in\{L,R,S\}$.

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

Мне нужно ... в унарном коде на машине Тьюринга.

Унарный код - это $A=\{1\}$ или $A=\{\epsilon,1\}$, где $\epsilon$ - пустое слово. Первый вариант вроде не бывает, а 2-й более чем стандартен.

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

Мне нужно научиться умножать, проверять на чётность,возводить в $n$ степень числа

В алфавите $A=\{\epsilon,1\}$ проверка на четность ну очень проста: стираем по две единички, пока это возможно, потом смотрим на результат.
Умножение сводится к сложению через соотношение $x\cdot (y+1)=x\cdot y+x$, т.е. умножение сводится к сложению. Возведение в степень аналогично сводится к умножению.

[cool.phenon]

Цитата:

А что это за вид? Обычно же вид такой: .

Этот вид предложил преподаватель, впоследствии такой же я обнаружил в учебнике "Введение в дискретную математику" Яблонского.

Цитата:

или , где - пустое

Ну тут тоже вроде похоже, только вместо $\varepsilon$ использую 0.

Цитата:

проверка на четность ну очень проста: стираем по две единички, пока это возможно, потом смотрим на результат.

А вот тут можно поподробнее? Не очень понятно, как это конкретно делается. Вообще не понятно, как на этом языке реализовать условие. Предполагаю
$X_{1},1 \to 1RX_{2} ;X_{2},1 \to 0LX_{1}; X_{2},0 \to 0SX_{3}$

A вот умножать- что- то совсем глухо. Не могли бы вы поподробнее объяснить?

[Sonic86]

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

Цитата:

А что это за вид? Обычно же вид такой: $a_iq_j\toa_kq_rT, T\in\{L,R,S\}$.

Этот вид предложил преподаватель, впоследствии такой же я обнаружил в учебнике "Введение в дискретную математику" Яблонского.

Так, я домыслю: $A=\{0;1\}$, $X_j$ - состояния МТ, $L,R,S$ - шаги.

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

А вот тут можно поподробнее? Не очень понятно, как это конкретно делается. Вообще не понятно, как на этом языке реализовать условие. Предполагаю
$X_{1},1 \to 1RX_{2} ;X_{2},1 \to 0LX_{1}; X_{2},0 \to 0SX_{3}$

А из $X_3$ никуда не уходим? Или $X_3$ - конечное состояние? (обычно пишут $q_0$).
Воспроизвел работу программы, это больше похоже на вычисление $x\div 1$ (здесь $\div$ - усеченная разность).
Вам надо такую рекурсию воспроизвести: если на входе $0$ или $1$, то $0$ следует интепретировать как четность входа, а $1$ - как нечетность (если задана другая схема кодирования выхода - перекодировать после вычисления). А если на входе $x>1$, то нужно вычислить $x-2$ - просто стереть две единички. (можно проще описать, но полностью решать за Вас не могу).
Еще играют роль технические вещи: у Вас лента потенциально неограниченна в одну сторону или в две? Если в одну, то как определить начало левого края входа? Если он слева ноликом не обрамлен - придется это сначала сделать.
Попытайтесь, это несложно.

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

A вот умножать- что- то совсем глухо. Не могли бы вы поподробнее объяснить?

Рекурсия такая:
$f(x,0)=0$
$f(x,y)=f(x,y-1)+x$,
т.е. пока $y$ ненулевое, выполнять сложение (сначала нужно написать МТ для сложения, а затем ее юзать как подпрограмму в искомой МТ). Вы МТ для сложения можете написать?

[Joker_vD]

(Оффтоп)

Sonic86 в сообщении #721900 писал(а):

Если в одну, то как определить начало левого края входа?

На нем стоит неперезаписываемый черный треугольник $\blacktriangle$. МТ можно вводить очень по-разному, но различия, в целом, технические. Например, можно условиться, что если $A$ — алфавит, то в ячейках стоят символы из $A\cup\{\wedge\}$, где $\wedge$ символизирует пустую ячейку ($\wedge\notin A$, но опять же, это технические детали).

[cool.phenon]

Цитата:

Так, я домыслю: , - состояния МТ, - шаги.

Да, так и есть.

Лента бесконечная в обе стороны, здесь считается, что считывающая головка стоит в начале (на первой единице), то есть, искать начало не нужно, что уже хорошо.

Цитата:

Попытайтесь, это несложно

Вот, попробовал нечто другое.
$1,X_{1}\to 1RX_{2}; 0,X_{2}\to 0SX_{1}; 1,X_{2} \to 1RX_{3}; 1,X_{3}\to 1LX_{4}; 1,X_{4} \to 0X_{5}; 1,X_{5}\to 0LX_{6}; 0,X_{6}\to 0RX_{6}; 1,X_{6}\to 1RX_{1} $

Сложение на 1 бесконечной ленте я знаю, 2 группы единичек разделены нулём, нуль заменяем на 1, идём в самый конец и убираем 1 единицу.

Но вот тут у меня проблема, допустим, сложил один раз, но дальше мне уже нужно знать, сколько именно единиц слева или справа нужно приписать, а этого в машине Тьюринга никак не напишешь. Что здесь можно сделать?

[Xaositect]

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

Что здесь можно сделать?

Сначала разберитесь, как скопировать число, то есть из строки $1^n$ получить $1^n01^n$

[nikvic]

А не элегантнее ли воспользоваться китайским методом умножения?

[cool.phenon]

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

[nikvic]

Один из множителей последовательно делится на два с остатком, второе - удваивается. Из последовательности остатков и удвоений сложением формируется произведение.
Для теории алгоритмов это несущественно.

[Sonic86]

(сущий оффтоп)

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

$1,X_{1}\to 1RX_{2}$

А зачем писать запятые?

Joker_vD в сообщении #721919 писал(а):

На нем стоит неперезаписываемый черный треугольник $\blacktriangle$.

чОрный треугольник был заложен в основание ленты в глубокой древности. ЧОООрный треугольник повергает головку МТ в дикий темный древний ужас и она отказывается ходить влево! Выполнить переход головки влево может сделать лишь Чак Норрис. Или Сталин.

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

Вот, попробовал нечто другое.
$1,X_{1}\to 1RX_{2}; 0,X_{2}\to 0SX_{1}; 1,X_{2} \to 1RX_{3}; 1,X_{3}\to 1LX_{4}; 1,X_{4} \to 0X_{5}; 1,X_{5}\to 0LX_{6}; 0,X_{6}\to 0RX_{6}; 1,X_{6}\to 1RX_{1} $

Не очень понятно, что Вы хотели.
Вообще, ясно, что либо для каждой комбинации $aX_j$ должна быть задана инструкция, либо, если есть команда $aX_i\to bX_j$, то среди инструкций должна быть и команда $bX_j\to ...$ (т.е. у графа комбинаций должны из каждой вершины выходить стрелки). У Вас вот есть команда $1,X_{4} \to 0X_{5}$, а для комбинации $0X_5$ команды нет.
И еще нет команды с заключительным состоянием $X_0$ - машина не остановится.

[nikvic]

(Оффтоп)

Sonic86 в сообщении #721975 писал(а):

Вообще, ясно, что либо для каждой комбинации должна быть задана инструкция

Нужно их заставлять ещё писать симулятор на Паскале

[cool.phenon]

Вначале стрелка стоит в начале строки единиц, поэтому начинаем и двигаем вправо.
$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}$

(Оффтоп)

nikvic
Не судите прям так сразу, я работаю с этими машинами 3 раз за всё моё существование. После 1 лекции и 1 практики. Эта тема полностью предоставлена на самостоятельное изучение. Поэтому прошу понимания.

[arseniiv]

(О структурном подходе.)

Не может быть удобнее сначала нарисовать отображение из частично рекурсивных функций в машины Тьюринга?

[cool.phenon]

(Оффтоп)

arseniiv
Это вы имеете в виду что-то вроде $*A_{5}A_{1}pA_{2}A_{4}pA_{10}w$?