Построить алгорифм Маркова для функции y = 7x + 2

[qx87]

В единичной системе счисления задача элементарная:

$\\ \#1 &\rightarrow 1111111\# \\ \#\phantom{1} &\mapsto 11 \\ \phantom{\#1} &\rightarrow \# $

Но сделать это требуется в восьмеричной системе счисления. Видел примеры похожих задач, но там требуется в двоичной системе умножить число на 4, то есть просто приписать два нуля. Здесь же аналогичного простого способа не вижу, по-моему, даже просто прибавить 2 -- уже довольно сложная задача. Может кто дать подсказку или ссылку?

[arseniiv]

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

[qx87]

Ну, допустим, я примерно представляю, как сделать конвертацию в единичную сс. Допустим, даже сделаю.
Обратную конвертацию пока затрудняюсь придумать, но допустим, что осилю и её.

Подозреваю, что обе эти задачи довольно нетривиальные и потребуют введение спецзнаков. А команда с пустой правой частью может быть только одна и только в конце списка. Как же я тогда сделаю композицию этих алгорифмов?

[arseniiv]

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

А команда с пустой правой частью может быть только одна и только в конце списка. Как же я тогда сделаю композицию этих алгорифмов?

Вы хотели сказать, с пустой левой?

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

$$r_1,\; \ldots,\; r_m,\; \alpha\#\beta\mapsto\gamma,\; r'_1,\; \ldots,\; r'_n,\; \varepsilon\to\#,$$

где $\alpha,\beta,\gamma$ — какие-то строки, $\gamma$ не содержит $\#$, и $\varepsilon$ обозначает пустую строку. Дополним его, чтобы в конце работы в левом конце строки был символ $\#'$, до алгорифма А2:

$$c_1\flat\to\flat c_1,\; \ldots,\; c_k\flat\to\flat c_k,\; \flat\mapsto\#',\; r_1,\; \ldots,\; r_m,\; \alpha\#\beta\to\flat\gamma,\; r'_1,\; \ldots,\; r'_n,\; \varepsilon\to\#,$$

где $c_1, \ldots, c_k$ — все символы кроме $\#$, использующиеся в правилах алгорифма А1. Если в А1 несколько завершающих правил, избавляющихся от $\#$, их все надо поменять как здесь, а вот если есть правила, избавляющиеся от $\#$, но не завершающие, это надо рассматривать отдельно.

[qx87]

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

Вы хотели сказать, с пустой левой?

Так точно )

Ну хорошо. Допустим, композиция алгорифмов всегда построяема. Будем пока что работать в этом направлении, а там разберёмся. НАМ перевода из восьмеричной в унарную я построил (и он даже не содержит правила с ПЛЧ -- пустой левой частью). НАМ обратного перевода в восьмеричную у меня циклится:

$\\ \#|||||||| &\rightarrow |\# \\ \#||||||| &\rightarrow 7 \\ \#|||||| &\rightarrow 6 \\ \#||||| &\rightarrow 5 \\ \#|||| &\rightarrow 4 \\ \#||| &\rightarrow 3 \\ \#|| &\rightarrow 2 \\ \#| &\rightarrow 1 \\ \# &\rightarrow 0 \\ \phantom{\#} &\rightarrow \# $

Он верно переводит число, но потом бесконечно вставляет в начало слова октоторп и тут же заменяет его на ноль. Что можно тут сделать?

P. S. Что-то я начинаю подозревать, что в НАМах нельзя многократно использовать правило с ПЛЧ... Хотя я тут мало имею опыта, может, и можно как-то орагнизовать.

[arseniiv]

Сейчас подумаю.

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

Будем пока что работать в этом направлении, а там разберёмся.

Вообще я, кстати, как раз надеялся, что кто-нибудь придёт и укажет царский путь. Но пока не пришли…

[qx87]

Ну, царский путь -- это, по идее, сделать всё в восьмеричной системе. То есть приписать к числу его копию, к ней приписать ноль (т. е. умножить на 8), из неё вычесть оригинал, а потом добавить два. Видел я такой царский путь.

(Оффтоп)

... в гробу

[arseniiv]

Кстати, можно найти компромисс: перевести в двоичную (тут уж проще некуда оба раза) и делать арифметику в двоичной. Посмотрите, вдруг это больше понравится.

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

P. S. Что-то я начинаю подозревать, что в НАМах нельзя многократно использовать правило с ПЛЧ... Хотя я тут мало имею опыта, может, и можно как-то орагнизовать.

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

(Ещё не додумал тот ваш вопрос.)

-- Вт май 02, 2017 23:52:48 --

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

Он верно переводит число, но потом бесконечно вставляет в начало слова октоторп и тут же заменяет его на ноль. Что можно тут сделать?

Топорная коррекция вот такая: раз он начинает зацикливаться, когда закончились палочки, надо поймать этот момент:

$$\#|^8\mapsto|\#,\; |\#|^7\to|7,\; \ldots,\; |\#|^0\to|0,\; \#|^7\mapsto7,\; \ldots,\; \#|^0\mapsto0,\; \varepsilon\to\#$$

($|^n$ — $n$ палочек подряд).

[qx87]

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

-- 02.05.2017, 23:14 --

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

Топорная коррекция вот такая: раз он начинает зацикливаться, когда закончились палочки, надо поймать этот момент

Отлично! Спасибо большое, работает!

Все три фазы алгоритма готовы, завтра попробую собрать его.

[arseniiv]

Удачи.

[qx87]

Сделал композицию первых двух шагов. НАМ принимает на вход число $x$ в восьмеричной системе счисления, возвращает число $y = 7x+2$ в унарной системе счисления.

$\\ |0 \rightarrow 0|^8 \\ 1 \rightarrow 0|^{1 \cdot 7} \\ 2 \rightarrow 0|^{2 \cdot 7} \\ 3 \rightarrow 0|^{3 \cdot 7} \\ 4 \rightarrow 0|^{4 \cdot 7} \\ 5 \rightarrow 0|^{5 \cdot 7} \\ 6 \rightarrow 0|^{6 \cdot 7} \\ 7 \rightarrow 0|^{7 \cdot 7} \\ 0 \rightarrow \\ \# \mapsto || \\ \phantom{\#} \rightarrow \# $

[arseniiv]

Хорошо сократили!

[qx87]

Алгорифм готов.

$\\ \mbox{Шаг 2. Замена на близнецовый алфавит} \\ \ast| \to \ast L \\ L| \to LL \\ \\ \mbox{Шаг 3. Перевод из унарной системы обратно в восьмеричную, финал} \\ \ast L^8 \to L \ast \\ L+ \to +L \\ \\ L\ast L^7 \to +L 7 \\ L\ast L^6 \to +L 6 \\ L\ast L^5 \to +L 5 \\ L\ast L^4 \to +L 4 \\ L\ast L^3 \to +L 3 \\ L\ast L^2 \to +L 2 \\ L\ast L\phantom{^1} \to +L 1 \\ L\ast \phantom{L^0} \to +L 0 \\ \\ \ast L^7 \mapsto 7 \\ \ast L^6 \mapsto 6 \\ \ast L^5 \mapsto 5 \\ \ast L^4 \mapsto 4 \\ \ast L^3 \mapsto 3 \\ \ast L^2 \mapsto 2 \\ \ast L\phantom{^1} \mapsto 1 \\ \ast \phantom{L^0} \mapsto 0 \\ \\ + \to \ast \\ \\ \mbox{Шаг 1. Перевод числа } x \mbox{ в восьмеричной системе в число } y = 7x+2 \mbox{ в унарной системе} \\ |0 \to 0|^8 \\ 1 \to 0|^{1 \cdot 7} \\ 2 \to 0|^{2 \cdot 7} \\ 3 \to 0|^{3 \cdot 7} \\ 4 \to 0|^{4 \cdot 7} \\ 5 \to 0|^{5 \cdot 7} \\ 6 \to 0|^{6 \cdot 7} \\ 7 \to 0|^{7 \cdot 7} \\ 0 \to \\ \# \to \ast|| \\ \phantom{\#} \rightarrow \# $

Нашёл в литературе алгоритм композиции НАМов, делал по нему. Однако ввиду специфики задачи и ещё того, что выходной алфавит первого шага состоит из одного символа $\{|\}$, удалось избавиться от тонны вспомогательных правил. В том числе от целой группы правил перевода строки из близнецового алфавита обратно в родной, количество которых равно трижды квадрату мощности расширенного алфавита: $3 \cdot |V \cup V'|^2$, т. е. 300 штук для моего случая :).

Проблема, однако, возникла с тем, что финальный алгоритм перевода обратно в восьмеричную систему многократно использует правило с ПЛЧ, поэтому вашим, arseniiv, методом воспользоваться не удалось. На этот раз проблему решил уже сам, введя новый маркер $+$, который я вставляю вместо $\ast$, когда тот уничтожается на НЕтерминальных правилах, а потом гоню плюс обратно в начало строки, где он сбрасывает личину и перевоплощается обратно в $\ast$. Кажется, я понемногу научиваюсь думать нормальными алгорифмами )

arseniiv, задача решена, огромное спасибо за помощь!!

[arseniiv]

Да тут, в общем, не за что, вы же практически всё сами составляли.