Re: Коллац на Фрактране - Этюды для программистов

А вот вам этюд для труъ программистов!

"Я хочу сыграть с вами в одну игру..." (Джон Конвей, про свою игру "Жизнь")

Вы задаёте список положительных дробей.
Берём некое натуральное число.
И пытаемся умножить его на первую дробь. Если результат дробный — отменяем, пытаемся умножить на вторую дробь. И так далее...
Короче говоря, находим в списке первую дробь, которая при умножении на число даёт натуральное число.
Повторяем эту процедуру для результата умножения. (Каждый раз начинаем поиск от начала списка).
Ну и так далее.
Если ни одна из дробей не подошла, то процедура останавливается.

Этот список дробей является программой на эзотерическом языке Fractran.

Поскольку, я надеюсь, всем очевидно, что фрактран-машина имеет дело с разложением чисел на степени простых множителей, и сами множители ни на что не влияют, то можем сразу перейти к представлению фрактран-машины над конечными векторами целых чисел.
Программа представляет собой список векторов с произвольными компонентами (и положительными, и отрицательными).
Состояние — вектор со строго неотрицательными.

Пример кода, который делит число с остатком: <x,0,0> --> <0,x/2,x%2>
то есть, на вход подаём 2^x, а в итоге хотим получить 3^d * 5^r

1) < -2, +1, 0 > = 2^-2 * 3 = 3/4
2) < -1, 0, +1 > = 2^-1 * 5 = 5/2

Машина работает так:
— если x >= 2, делаем x-=2, d+=1 — и повторяем
— если x >= 1, делаем x-=1, r+=1 — и тут уже повторять не получится
— на этом и останавливаемся.

А вот пример машины, которая бесконечно прыгает между тремя состояниями
1) < -1, +1, 0 > = 3/2
2) < 0, -1, +1 > = 5/3
3) < +1, 0, -1 > = 2/5
Подаём на вход <1,0,0> = 2 и всё заверте

Предлагаю маленький конкурс: написать программу, реализующую последовательность Коллаца (3x+1).

На входе — некое число, символизирующее x. (Например, 2^x)
На выходе — некое число, символизирующее количество итераций до значения 1. (Например, 3^t)
(Примем за постулат, что 3x+1 всегда сходится к циклу 1-4-2-1).

Чем короче будет программа, тем лучше.

Только давайте сразу договоримся, что код публиковать в виде векторов, а не в виде дробей. Потому что какое-нибудь 1234/567 воспринимать тяжело, это же надо факторизовывать (2^1 * 617^1) / (3^4 * 7^1)

поторопился

Здравствуйте, kov_serg, Вы писали:

_>поторопился

Не хватает дополнительного условия
Если x*y даёт целое, то не x'=x*y а x'=x*y*z (где z доп. целое число) тогда получаются нормальные ветвления

Здравствуйте, kov_serg, Вы писали:

_>Не хватает дополнительного условия
_>Если x*y даёт целое, то не x'=x*y а x'=x*y*z (где z доп. целое число) тогда получаются нормальные ветвления

Если y и z взаимно простые, то замени y на y*z и будет щасте.
Если же у них есть общая часть (метка состояния — что нужно для зацикливания) — то можно сделать, например, следующим способом.

Каждая инструкция у нас выглядит так:
"если (ни одно условие выше не подошло и) x содержит p, то (убрать p) и сделать полезное действие"

Чтобы зациклить инструкцию, удвоим её:
1) "если x содержит метку p, то (убрать p), добавить p' и сделать полезное действие"
2) "если x содержит метку p', то (убрать p'), добавить p и сделать полезное действие"

Получится пинг-понг между состояниями <...,p=1,p'=0,...> и <...,p=0,p'=1,...>

Таким образом, мы можем оснастить программу метками
— для однократных действий — это просто уникальный простой множитель
— для зацикливания — пара уникальных

Здравствуйте, Кодт, Вы писали:

К>Получится пинг-понг между состояниями <...,p=1,p'=0,...> и <...,p=0,p'=1,...>

Не получится. Надо условный цикл. А пин понг приводит к длинным трекам, и ограничениям по максимальному допустимому значению в цикле.
надо именно

[a-b-c][b]

Т.е u=pa/pb/pc если число x делится этим u нацело то умножаем на u и на z=pb

while (x*pa/pb/pc is integer) do x*= (pa/pb/pc) * pb

т.е. переливаем с в a при условии b

без этого будут бесконечные ленты для условий, что не очень здорово.

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, Кодт, Вы писали:

К>>Получится пинг-понг между состояниями <...,p=1,p'=0,...> и <...,p=0,p'=1,...>

_>Не получится. Надо условный цикл. А пин понг приводит к длинным трекам, и ограничениям по максимальному допустимому значению в цикле.
_>надо именно

_>[a-b-c][b]

_>Т.е u=pa/pb/pc если число x делится этим u нацело то умножаем на u и на z=pb

квадрат пропустил, иначе и у тебя не зациклится — надо же восстановить степень pb после деления

_>while (x*pa/pb/pc is integer) do x*= (pa/pb/pc) * pb

Я именно это и имею в виду.

Условие, на самом деле
while (x/pb is integer and x/pc is integer)

давай перепишем:

было

while true:
  if x * pa / pb / pc is integer then x *= pa / pc ( / pb * pb * pb)
  else
  break

стало

while true:
  if x * pa / pb1 * pb2 / pc is integer then x *= pa / pb1 * pb2 / pc
  else
  if x * pa * pb1 / pb2 / pc is integer then x *= pa * pb1 / pb2 / pc
  else
  break

Объяснение этому вот какое:
— очевидно, что мы можем повсеместно заменить фактор pb на pb^2, квадрат простого числа будет по-прежнему взаимно-простым со всеми остальными факторами
— очевидно, что мы можем повсеместно заменить фактор pb на (pb1*pb2), по тем же причинам
— теперь, если мы введём вектор (pb1,pb2), то получим не два состояния (степени множителя) 0 и 1, а 00,01,10,11 — из которых нас интересуют первые три
— теперь, если мы введём класс эквивалентности — 01=10, то у фрактран-машины появится легальное действие: "поделить на фактор и умножить на этот же фактор" — чего не бывает с обычными дробями
— но класс эквивалентности требует расщепления: одна дробь делит на одно число из класса и умножает на другое, вторая — наоборот.

Если мы договариваемся, что степень у фактора метки — всегда 0 или 1, — то проблем не возникает.
Вход в метку — умножение на любое число из класса эквивалентности.
Оставание в метке — пинг-понг. (Удваиваем все инструкции)
Выход из метки — отсутствие умножения. (Удваиваем все инструкции)

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, kov_serg, Вы писали:
К>давай перепишем:

К>было
К>

К>while true:
К>  if x * pa / pb / pc is integer then x *= pa / pc ( / pb * pb * pb)
К>  else
К>  break
К>

нет я же написал совсем не так.
для [a-b-c][b] вот что требуется:

    while x*pa/pb/pc is int:
        x*=pa/pc

[a-b-c][b]
Сначала умножаем если целое, то умножаем на оба числа
те программа состоит из пар чисел (u,v)
если x*u не целое идём дальше иначе умножаем x на u и v.

запись [a-b-c] означает exp(a-b-c)
где a=ln(pa), b=ln(pb), c=ln(pc)
pa,pb,pc — любые взаимно простые числа

----

К>Объяснение этому вот какое:
К>- очевидно, что мы можем повсеместно заменить фактор pb на pb^2, квадрат простого числа будет по-прежнему взаимно-простым со всеми остальными факторами
К>- очевидно, что мы можем повсеместно заменить фактор pb на (pb1*pb2), по тем же причинам
К>- теперь, если мы введём вектор (pb1,pb2), то получим не два состояния (степени множителя) 0 и 1, а 00,01,10,11 — из которых нас интересуют первые три
К>- теперь, если мы введём класс эквивалентности — 01=10, то у фрактран-машины появится легальное действие: "поделить на фактор и умножить на этот же фактор" — чего не бывает с обычными дробями
К>- но класс эквивалентности требует расщепления: одна дробь делит на одно число из класса и умножает на другое, вторая — наоборот.

К>Если мы договариваемся, что степень у фактора метки — всегда 0 или 1, — то проблем не возникает.
К>Вход в метку — умножение на любое число из класса эквивалентности.
К>Оставание в метке — пинг-понг. (Удваиваем все инструкции)
К>Выход из метки — отсутствие умножения. (Удваиваем все инструкции)

Ничего не понял.

мы можем выполнять операции перегонки значений например [ka*a+kb*b-kc*c-d][d] означает
если x не содержит множитель pd операция пропускается
если содержи pd в первой степени, то операция выполняется nc раз если x содержит pc^nc
т.е. запись [ka*a+kb*b-kc*c-d][d]
эквивалентна такой инструкции:

if (nd): na+=ka*floor(nc/kc); nb+=kb*floor(nc/kc); nc=nc%kc

для x=xo*pc^nc*pd^1

Здравствуйте, Кодт, Вы писали:

К>стало
К>

К>while true:
К>  if x * pa / pb1 * pb2 / pc is integer then x *= pa / pb1 * pb2 / pc
К>  else
К>  if x * pa * pb1 / pb2 / pc is integer then x *= pa * pb1 / pb2 / pc
К>  else
К>  break
К>

Вообще-то станет не так а так:

while true:
  if x * pa / pb1 * pb2 / pc is integer then x *= pa / pb1 * pb2 / pc
  else
  break
while true:
  if x * pa * pb1 / pb2 / pc is integer then x *= pa * pb1 / pb2 / pc
  else
  break

Здравствуйте, kov_serg, Вы писали:

_>Вообще-то станет не так а так:
_>

_>while true:
_>  if x * pa / pb1 * pb2 / pc is integer then x *= pa / pb1 * pb2 / pc
_>  else
_>  break
_>while true:
_>  if x * pa * pb1 / pb2 / pc is integer then x *= pa * pb1 / pb2 / pc
_>  else
_>  break
_>

Не забывай, что фрактран-машина гоняет цикл по всем дробям:

while true:
  if x * f1 is integer:
    x *= f1
  elif x * f2 is integer:
    x *= f2
  ...
  else:
    break  # ничего не подошло

Также надо учесть, что показатели при pb1 и pb2 — это 0 или 1
Если мы представим x как словарь: фактор -> показатель
то перепишем это

while x[pb1] >= 1 and x[pc] >= dc:
  x[pb1] -= 1
  x[pb2] += 1

  x[pc] -= dc
  x[pa] += na

и очевидно, что этот твой while выполнится не более 1 раза.

Покажу своё референсное решение.

Заметно неоптимальное. (Специально напихал туда лишнего).

не подглядывать!

Пусть состояние машины — это три переменные (x,t,y) — где x — текущее значение, t — количество итераций, y — промежуточное число x/2
и ровно одна метка из набора меток (я им буду давать говорящие словесные названия).

STATE = 2^x * 3^t * 5^y * {L из L1...Ln}

Изначально метки вообще нет, это стартовое состояние

START = 2^x, x>0

Окончательно мы должны придти к состоянию, когда метки опять нет,

FINISH = 3^t

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

Оформлю программу в табличку

текущая | следующая | dx | dy | dt
--------+-----------+----+----+----
restore | divide1   | +2 |    |       x += 2 после первой проверки в стартовом состоянии (в самом низу)
--------+-----------+----+----+----
divide1 | divide2   | -2 | +1 |       while x>=2 do x-=2, y+=1
divide2 | divide1   | -2 | +1 |       обратите внимание на приём "пинг-понг"
--------+-----------+----+----+----
divide1 | odd1      | -1 |    |       if x==1 then x-=1, goto odd
divide2 | odd1      | -1 |    |
--------+-----------+----+----+----
divide1 | even1     |    |    |       else goto even
divide2 | even1     |    |    |
--------+-----------+----+----+----
even1   | even2     | +1 | -1 |       x' = x/2 = y
even2   | even1     | +1 | -1 |
--------+-----------+----+----+----
even1   | next      |    |    |       всё, переложили x из y полностью, идём дальше
even2   | next      |    |    |
--------+-----------+----+----+----
odd1    | odd2      | +6 | -1 |       x' = 3x+1 = 3(2y+1)+1 = 6y+4
odd2    | odd1      | +6 | -1 |
--------+-----------+----+----+----
odd1    | next      | +4 |    |
odd2    | next      | +4 |    |
--------+-----------+----+----+----
next    |           |    |    | +1    инкрементируем t и переходим на старт
--------+-----------+----+----+----
        | restore   | -2 |    |       стартовая проверка: if x>=2 then x-=2, goto restore
--------+-----------+----+----+----
        |           | -1 |    |       стартовая очистка: if x==1 then x=0, goto finish
--------+-----------+----+----+----

итого, у нас 8 меток (2 одиночных — restore и next — и 6 парных).

Та же фигня в виде векторов — показателей у множителей 2,3,5, restore=7, divide=11,13, even=17,19, next=23, odd=29,31

dx dt dy r dd ee n oo
+2       -            = 4 / 7
-2    +1   -+         = 5*13 / 4*11
-2    +1   +-         = 5*11 / 4*13
-1         -       +  = 29 / 2*11
-1          -      +  = 29 / 2*13
           -  +       = 17 / 11
            - +       = 17 / 13
+1    -1      -+      = 2*19 / 5*17
+1    -1      +-      = 2*17 / 5*19
              -  +    = 23 / 17
               - +    = 23 / 19
+6    -1           -+ = 64*31 / 5*29
+6    -1           +- = 64*29 / 5*31
+4               + -  = 16*23 / 29
+4               +  - = 16*23 / 31
   +1            -    = 3 / 23
-2       +            = 7 / 4
-1                    = 1 / 2

Можете попробовать оптимизировать моё — там есть очевидные вещи для сокращения и параллельного выполнения.
А можете изобрести свои хитрые подходы, будет любопытно посмотреть.

Здравствуйте, kov_serg, Вы писали:

теперь уже я ничего не понял, чего хотелось-то!

Тем не менее, вот тут http://rsdn.org/forum/etude/8560154.1
референсное решение, где я демонстрирую и циклы, и ветвления.

В копилку приёмов для улучшения.

---

Алгоритмический — по самой последовательности.

(x',t') = (3x+1, t+1) если x нечётно, иначе (x/2, t+1)

поскольку 3x+1 заведомо чётно и заведомо не равно 1, то мы можем сразу же сделать ещё одну итерацию:
(x',t') = ((3x+1)/2, t+2) ||| (x/2, t+1)

или, если y=int(x/2),
(x',t') = (3y+2, t+2) ||| (y, t+1)

---

Метки в программе

Вершины графа состояний машины пометим уникальными простыми множителями.
Одновременно в состоянии может быть только одна метка.
Все инструкции машины при этом выглядят как: "поделить на текущую метку, умножить на метку перехода, ну и там поделить-умножить в соответствие с логикой работы"
Это позволяет перестать следить за взаимным порядком инструкций.
Для одной метки порядок важен, между собой метки можно переставлять, как угодно.
Единственное исключение — это стартовое состояние без меток. Его инструкции должны быть в самом конце.

---

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

Либо же мы добавляем в петлевую дугу новую вершину, которая ничего не делает.
Длина кода уменьшается, время работы увеличивается.

\ | ___
 \|/   \
  L____/    L->L закодировать напрямую нельзя...
 /|\
/ | \

\ | ___
 \|/   Le   L->Le содержательный, Le->L ничего не делает (только метку изменяет)
  L____/
 /|\
/ | \


\ |
 \|____
  L____Ld   L->Ld содержательный, Ld->L делает то же самое
 /|\   /|\
/ | \ / | \

---

Умножения можно двигать вперёд-назад по дугам графа, при условии, что на дугах нет соответствующего деления.

A -> B : *x
B -> C : *y
B -> D : *z

эквивалентно

A -> B : ничего
B -> C : *x *y
B -> D : *x *z

Здравствуйте, Кодт, Вы писали:

К>Не забывай, что фрактран-машина гоняет цикл по всем дробям:
Я не понял она бежит по вектору дробей от начала до конца,
а потом опять и так по кругу пока не застрянет?

Здравствуйте, kov_serg, Вы писали:

_>Я не понял она бежит по вектору дробей от начала до конца,
_>а потом опять и так по кругу пока не застрянет?

Он бежит от начала списка до первой подходящей дроби, дающей целое произведение.
И так каждый раз.

Здравствуйте, Кодт, Вы писали:

К>Изначально метки вообще нет, это стартовое состояние

К>START = 2^x, x>0

К>Оформлю программу в табличку
К>

К>текущая | следующая | dx | dy | dt
К>--------+-----------+----+----+----
К>restore | divide1   | +2 |    |       x += 2 после первой проверки в стартовом состоянии (в самом низу)
К>--------+-----------+----+----+----
К>divide1 | divide2   | -2 | +1 |       while x>=2 do x-=2, y+=1
К>divide2 | divide1   | -2 | +1 |       обратите внимание на приём "пинг-понг"
К>--------+-----------+----+----+----
К>divide1 | odd1      | -1 |    |       if x==1 then x-=1, goto odd
К>divide2 | odd1      | -1 |    |
К>--------+-----------+----+----+----
К>divide1 | even1     |    |    |       else goto even
К>divide2 | even1     |    |    |
К>--------+-----------+----+----+----
К>even1   | even2     | +1 | -1 |       x' = x/2 = y
К>even2   | even1     | +1 | -1 |
К>--------+-----------+----+----+----
К>even1   | next      |    |    |       всё, переложили x из y полностью, идём дальше
К>even2   | next      |    |    |
К>--------+-----------+----+----+----
К>odd1    | odd2      | +6 | -1 |       x' = 3x+1 = 3(2y+1)+1 = 6y+4
К>odd2    | odd1      | +6 | -1 |
К>--------+-----------+----+----+----
К>odd1    | next      | +4 |    |
К>odd2    | next      | +4 |    |
К>--------+-----------+----+----+----
К>next    |           |    |    | +1    инкрементируем t и переходим на старт
К>--------+-----------+----+----+----
К>        | restore   | -2 |    |       стартовая проверка: if x>=2 then x-=2, goto restore
К>--------+-----------+----+----+----
К>        |           | -1 |    |       стартовая очистка: if x==1 then x=0, goto finish
К>--------+-----------+----+----+----
К>

К>итого, у нас 8 меток (2 одиночных — restore и next — и 6 парных).

Я видимо не так понимаю постановку задачи.

К>Та же фигня в виде векторов — показателей у множителей 2,3,5, restore=7, divide=11,13, even=17,19, next=23, odd=29,31
К>

К>dx dt dy r dd ee n oo
К>+2       -            = 4 / 7
К>-2    +1   -+         = 5*13 / 4*11
К>-2    +1   +-         = 5*11 / 4*13
К>-1         -       +  = 29 / 2*11
К>-1          -      +  = 29 / 2*13
К>           -  +       = 17 / 11
К>            - +       = 17 / 13
К>+1    -1      -+      = 2*19 / 5*17
К>+1    -1      +-      = 2*17 / 5*19
К>              -  +    = 23 / 17
К>               - +    = 23 / 19
К>+6    -1           -+ = 64*31 / 5*29
К>+6    -1           +- = 64*29 / 5*31
К>+4               + -  = 16*23 / 29
К>+4               +  - = 16*23 / 31
К>   +1            -    = 3 / 23
К>-2       +            = 7 / 4
К>-1                    = 1 / 2
К>

К>[/cut]
А именно:
Из кода выше получаем программу:

2p2-p7
p5+p13-2p2-p11
p5+p11-2p2-p13
p29-p2-p11
p29-p2-p13
p17-p11
p17-p13
p2+p19-p5-p17
p2+p17-p5-p19
p23-p17
p23-p19
6p2+p31-p5-p29
6p2+p29-p5-p31
4p2+p23-p29
4p2+p23-p31
p3-p23
p7-2p2
-p2

(где например 64*31 / 5*29 ==соответствует такой записи логарифмов взаимно простых чисел==> 6p2+p31-p5-p29)

Кладём на вход 27, заускаем

lua fractran machine

function dump(x) for k,v in pairs(x) do print(k,v) end end

function number_tostring(t)
    local r1={}
    for k,v in pairs(t) do table.insert(r1,{k,v}) end
    table.sort(r1,function(a,b) 
        if a[2]>0 and b[2]<0 then return true end
        if a[2]<0 and b[2]>0 then return false end
        return a[1]<b[1] 
    end)
    local r2,p2="",""
    for k,v in pairs(r1) do
        if v2~=0 then
            if v[2]>0 then r2=r2..p2 end
            if v[2]==1 then r2=r2..v[1]
            elseif v[2]==-1 then r2=r2..'-'..v[1]
            else r2=r2..v[2]..v[1] end
            p2="+"
        end
    end
    return r2
end

function attach_tostring(t)
    return setmetatable(t,{__tostring=number_tostring})
end

function number(line)
    local res={}
    line:gsub("([%+%-]?)(%d*)([%a_][%w_]*)",function(sign,k,name)
        if k=="" then k=1 end k=tonumber(k) if sign=='-' then k=-k end
        if res[name] then res[name]=res[name]+k else res[name]=k end
    end)
    return attach_tostring(res)
end

function compile(src,prog)
    prog=prog or {}
    src:gsub("[^\n]+",function(line) table.insert(prog,number(line)) end)
    return setmetatable(prog,{__tostring=function(t)
        local res=""
        for k,v in pairs(t) do res=res..string.format("%3d: %s\n",k,v) end
        return res
    end})
end

local FM={}
function FM:init(x,prog)
    self.pp=1
    self.x=x
    self.prog=prog
    self.ac=0
end
function FM:can(y)
    for k,v in pairs(y) do
        if v<0 then
            local xv=self.x[k] or 0
            if xv+v<0 then return false end
        end
    end
    return true
end
function FM:apply(y)
    for k,v in pairs(y) do
        local xv=self.x[k] or 0
        xv=xv+v
        if xv==0 then xv=nil end
        self.x[k]=xv
    end
end
function FM:step()
    local y=self.prog[self.pp]
    if y==nil then return false end
    if self:can(y) then self:apply(y) self.ac=self.ac+1
    else self.pp=self.pp+1 end
    return true
end
function newFM(x,prog)
    local fm=setmetatable({},{__index=FM})
    fm:init(x,prog)
    return fm
end

prog=compile[[
    2p2-p7
    p5+p13-2p2-p11
    p5+p11-2p2-p13
    p29-p2-p11
    p29-p2-p13
    p17-p11
    p17-p13
    p2+p19-p5-p17
    p2+p17-p5-p19
    p23-p17
    p23-p19
    6p2+p31-p5-p29
    6p2+p29-p5-p31
    4p2+p23-p29
    4p2+p23-p31
    p3-p23
    p7-2p2
    -p2
]]
-- print(prog)

x=attach_tostring{ p2=27 }
print(" 0)",x)
fm=newFM(x,prog)

limit=1000
for round=1,3 do
    fm.pp=1
    it=0
    repeat
        local pp=fm.pp
        local line=("\t%2d\tpp=%2d (%s)*(%s)"):format(it,pp,fm.x,fm.prog[pp])
        local active=fm:step()
        if pp==fm.pp then 
            line=("%s=%s"):format(line,fm.x) 
        else
            line=("\t%2d\tpp=%2d --skip-- (%s)"):format(it,pp,fm.prog[pp])
        end
        if not active then break end
        print(line) it=it+1
    until it>limit
    print(("result=%s of round %d (%d steps)"):format(fm.x,round,it))
end

И чешим репу

 0)    27p2
     0    pp= 1 --skip-- (2p2-p7)
     1    pp= 2 --skip-- (p13+p5-p11-2p2)
     2    pp= 3 --skip-- (p11+p5-p13-2p2)
     3    pp= 4 --skip-- (p29-p11-p2)
     4    pp= 5 --skip-- (p29-p13-p2)
     5    pp= 6 --skip-- (p17-p11)
     6    pp= 7 --skip-- (p17-p13)
     7    pp= 8 --skip-- (p19+p2-p17-p5)
     8    pp= 9 --skip-- (p17+p2-p19-p5)
     9    pp=10 --skip-- (p23-p17)
    10    pp=11 --skip-- (p23-p19)
    11    pp=12 --skip-- (6p2+p31-p29-p5)
    12    pp=13 --skip-- (6p2+p29-p31-p5)
    13    pp=14 --skip-- (4p2+p23-p29)
    14    pp=15 --skip-- (4p2+p23-p31)
    15    pp=16 --skip-- (p3-p23)
    16    pp=17 (27p2)*(p7-2p2)=25p2+p7
    17    pp=17 (25p2+p7)*(p7-2p2)=23p2+2p7
    18    pp=17 (23p2+2p7)*(p7-2p2)=21p2+3p7
    19    pp=17 (21p2+3p7)*(p7-2p2)=19p2+4p7
    20    pp=17 (19p2+4p7)*(p7-2p2)=17p2+5p7
    21    pp=17 (17p2+5p7)*(p7-2p2)=15p2+6p7
    22    pp=17 (15p2+6p7)*(p7-2p2)=13p2+7p7
    23    pp=17 (13p2+7p7)*(p7-2p2)=11p2+8p7
    24    pp=17 (11p2+8p7)*(p7-2p2)=9p2+9p7
    25    pp=17 (9p2+9p7)*(p7-2p2)=7p2+10p7
    26    pp=17 (7p2+10p7)*(p7-2p2)=5p2+11p7
    27    pp=17 (5p2+11p7)*(p7-2p2)=3p2+12p7
    28    pp=17 (3p2+12p7)*(p7-2p2)=p2+13p7
    29    pp=17 --skip-- (p7-2p2)
    30    pp=18 (p2+13p7)*(-p2)=13p7
    31    pp=18 --skip-- (-p2)
result=13p7 of round 1 (32 steps)
     0    pp= 1 (13p7)*(2p2-p7)=2p2+12p7
     1    pp= 1 (2p2+12p7)*(2p2-p7)=4p2+11p7
     2    pp= 1 (4p2+11p7)*(2p2-p7)=6p2+10p7
     3    pp= 1 (6p2+10p7)*(2p2-p7)=8p2+9p7
     4    pp= 1 (8p2+9p7)*(2p2-p7)=10p2+8p7
     5    pp= 1 (10p2+8p7)*(2p2-p7)=12p2+7p7
     6    pp= 1 (12p2+7p7)*(2p2-p7)=14p2+6p7
     7    pp= 1 (14p2+6p7)*(2p2-p7)=16p2+5p7
     8    pp= 1 (16p2+5p7)*(2p2-p7)=18p2+4p7
     9    pp= 1 (18p2+4p7)*(2p2-p7)=20p2+3p7
    10    pp= 1 (20p2+3p7)*(2p2-p7)=22p2+2p7
    11    pp= 1 (22p2+2p7)*(2p2-p7)=24p2+p7
    12    pp= 1 (24p2+p7)*(2p2-p7)=26p2
    13    pp= 1 --skip-- (2p2-p7)
    14    pp= 2 --skip-- (p13+p5-p11-2p2)
    15    pp= 3 --skip-- (p11+p5-p13-2p2)
    16    pp= 4 --skip-- (p29-p11-p2)
    17    pp= 5 --skip-- (p29-p13-p2)
    18    pp= 6 --skip-- (p17-p11)
    19    pp= 7 --skip-- (p17-p13)
    20    pp= 8 --skip-- (p19+p2-p17-p5)
    21    pp= 9 --skip-- (p17+p2-p19-p5)
    22    pp=10 --skip-- (p23-p17)
    23    pp=11 --skip-- (p23-p19)
    24    pp=12 --skip-- (6p2+p31-p29-p5)
    25    pp=13 --skip-- (6p2+p29-p31-p5)
    26    pp=14 --skip-- (4p2+p23-p29)
    27    pp=15 --skip-- (4p2+p23-p31)
    28    pp=16 --skip-- (p3-p23)
    29    pp=17 (26p2)*(p7-2p2)=24p2+p7
    30    pp=17 (24p2+p7)*(p7-2p2)=22p2+2p7
    31    pp=17 (22p2+2p7)*(p7-2p2)=20p2+3p7
    32    pp=17 (20p2+3p7)*(p7-2p2)=18p2+4p7
    33    pp=17 (18p2+4p7)*(p7-2p2)=16p2+5p7
    34    pp=17 (16p2+5p7)*(p7-2p2)=14p2+6p7
    35    pp=17 (14p2+6p7)*(p7-2p2)=12p2+7p7
    36    pp=17 (12p2+7p7)*(p7-2p2)=10p2+8p7
    37    pp=17 (10p2+8p7)*(p7-2p2)=8p2+9p7
    38    pp=17 (8p2+9p7)*(p7-2p2)=6p2+10p7
    39    pp=17 (6p2+10p7)*(p7-2p2)=4p2+11p7
    40    pp=17 (4p2+11p7)*(p7-2p2)=2p2+12p7
    41    pp=17 (2p2+12p7)*(p7-2p2)=13p7
    42    pp=17 --skip-- (p7-2p2)
    43    pp=18 --skip-- (-p2)
result=13p7 of round 2 (44 steps)
     0    pp= 1 (13p7)*(2p2-p7)=2p2+12p7
     1    pp= 1 (2p2+12p7)*(2p2-p7)=4p2+11p7
     2    pp= 1 (4p2+11p7)*(2p2-p7)=6p2+10p7
     3    pp= 1 (6p2+10p7)*(2p2-p7)=8p2+9p7
     4    pp= 1 (8p2+9p7)*(2p2-p7)=10p2+8p7
     5    pp= 1 (10p2+8p7)*(2p2-p7)=12p2+7p7
     6    pp= 1 (12p2+7p7)*(2p2-p7)=14p2+6p7
     7    pp= 1 (14p2+6p7)*(2p2-p7)=16p2+5p7
     8    pp= 1 (16p2+5p7)*(2p2-p7)=18p2+4p7
     9    pp= 1 (18p2+4p7)*(2p2-p7)=20p2+3p7
    10    pp= 1 (20p2+3p7)*(2p2-p7)=22p2+2p7
    11    pp= 1 (22p2+2p7)*(2p2-p7)=24p2+p7
    12    pp= 1 (24p2+p7)*(2p2-p7)=26p2
    13    pp= 1 --skip-- (2p2-p7)
    14    pp= 2 --skip-- (p13+p5-p11-2p2)
    15    pp= 3 --skip-- (p11+p5-p13-2p2)
    16    pp= 4 --skip-- (p29-p11-p2)
    17    pp= 5 --skip-- (p29-p13-p2)
    18    pp= 6 --skip-- (p17-p11)
    19    pp= 7 --skip-- (p17-p13)
    20    pp= 8 --skip-- (p19+p2-p17-p5)
    21    pp= 9 --skip-- (p17+p2-p19-p5)
    22    pp=10 --skip-- (p23-p17)
    23    pp=11 --skip-- (p23-p19)
    24    pp=12 --skip-- (6p2+p31-p29-p5)
    25    pp=13 --skip-- (6p2+p29-p31-p5)
    26    pp=14 --skip-- (4p2+p23-p29)
    27    pp=15 --skip-- (4p2+p23-p31)
    28    pp=16 --skip-- (p3-p23)
    29    pp=17 (26p2)*(p7-2p2)=24p2+p7
    30    pp=17 (24p2+p7)*(p7-2p2)=22p2+2p7
    31    pp=17 (22p2+2p7)*(p7-2p2)=20p2+3p7
    32    pp=17 (20p2+3p7)*(p7-2p2)=18p2+4p7
    33    pp=17 (18p2+4p7)*(p7-2p2)=16p2+5p7
    34    pp=17 (16p2+5p7)*(p7-2p2)=14p2+6p7
    35    pp=17 (14p2+6p7)*(p7-2p2)=12p2+7p7
    36    pp=17 (12p2+7p7)*(p7-2p2)=10p2+8p7
    37    pp=17 (10p2+8p7)*(p7-2p2)=8p2+9p7
    38    pp=17 (8p2+9p7)*(p7-2p2)=6p2+10p7
    39    pp=17 (6p2+10p7)*(p7-2p2)=4p2+11p7
    40    pp=17 (4p2+11p7)*(p7-2p2)=2p2+12p7
    41    pp=17 (2p2+12p7)*(p7-2p2)=13p7
    42    pp=17 --skip-- (p7-2p2)
    43    pp=18 --skip-- (-p2)
result=13p7 of round 3 (44 steps)

Здравствуйте, kov_serg, Вы писали:

_>Я видимо не так понимаю постановку задачи.

(не силён в луа, код поскипал без комментариев)

_>И чешим репу

_> 0)    27p2
_>     0    pp= 1 --skip-- (2p2-p7)
_>     1    pp= 2 --skip-- (p13+p5-p11-2p2)
_>     2    pp= 3 --skip-- (p11+p5-p13-2p2)
_>     3    pp= 4 --skip-- (p29-p11-p2)
_>     4    pp= 5 --skip-- (p29-p13-p2)
_>     5    pp= 6 --skip-- (p17-p11)
_>     6    pp= 7 --skip-- (p17-p13)
_>     7    pp= 8 --skip-- (p19+p2-p17-p5)
_>     8    pp= 9 --skip-- (p17+p2-p19-p5)
_>     9    pp=10 --skip-- (p23-p17)
_>    10    pp=11 --skip-- (p23-p19)
_>    11    pp=12 --skip-- (6p2+p31-p29-p5)
_>    12    pp=13 --skip-- (6p2+p29-p31-p5)
_>    13    pp=14 --skip-- (4p2+p23-p29)
_>    14    pp=15 --skip-- (4p2+p23-p31)
_>    15    pp=16 --skip-- (p3-p23)
_>    16    pp=17 (27p2)*(p7-2p2)=25p2+p7

вот, ура, 17-я дробь подошла. умножили — и надо снова бежать от начала списка

_>    17    pp=17 (25p2+p7)*(p7-2p2)=23p2+2p7
_>    18    pp=17 (23p2+2p7)*(p7-2p2)=21p2+3p7
_>    19    pp=17 (21p2+3p7)*(p7-2p2)=19p2+4p7
_>    20    pp=17 (19p2+4p7)*(p7-2p2)=17p2+5p7
_>    21    pp=17 (17p2+5p7)*(p7-2p2)=15p2+6p7
_>    22    pp=17 (15p2+6p7)*(p7-2p2)=13p2+7p7
_>    23    pp=17 (13p2+7p7)*(p7-2p2)=11p2+8p7
_>    24    pp=17 (11p2+8p7)*(p7-2p2)=9p2+9p7
_>    25    pp=17 (9p2+9p7)*(p7-2p2)=7p2+10p7
_>    26    pp=17 (7p2+10p7)*(p7-2p2)=5p2+11p7
_>    27    pp=17 (5p2+11p7)*(p7-2p2)=3p2+12p7
_>    28    pp=17 (3p2+12p7)*(p7-2p2)=p2+13p7

а вместо этого — мы тупо выполнили умножение до самого упора — применили максимальную степень этой дроби
и закономерно получили какую-то фигню.

Впрочем, даже для такой альтернативной фрактран-машины с политикой стоять-бежать и round robin есть контрмера!

Если мы договоримся, что у нас абсолютно все состояния (кроме финиша) имеют непустую метку.
Тогда стартовое число будет, скажем, 27p2+p37 (37 — метка старта)
а стартовые инструкции — -2p2+p7-p37 и -p2-p37.

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

	От:	Кодт
	Дата:	07.07.23 17:08
	Оценка:

	От:	kov_serg
	Дата:	07.07.23 19:54
	Оценка:

	От:	kov_serg
	Дата:	07.07.23 20:36
	Оценка:

	От:	Кодт
	Дата:	10.07.23 09:11
	Оценка:

	От:	kov_serg
	Дата:	10.07.23 09:24
	Оценка: