Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
 Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Привет Котаны-Бротаны!

В уже сложившейся традиции четверговых-пятничных топиков я публикую логическую
задачу-головоломку.

Задача

Написать алгоритм сложения двух двоичных чисел в нотации Нормальных Алгоритмов Маркова (НАМ)

Input:
"1101+111"


Output code example:
 ->
 ->
 ...
 |->


Output result example:
"10100"


+ Под катом я расскажу что такое НАМ своими словами
Нормальные Алгоритмы Маркова (НАМ) - представляют собой совокупность правил (rules)
вида:
a -> b
x -> y

которые последовательно применяются к входящей строке до тех пор пока не будет достигнyто условие
применения terminal rule ( |-> ). Применение - суть строковая замена. Выражение слева от стрелки заменятеся на правое.

Пример алгоритма переводящего римскую цифру в десятичное число.
IX -> 9
VIII -> 8
VII -> 7
VI -> 6
V -> 5
IV -> 4
III -> 3
II -> 2
I -> 1
|->


Еще некоторы дополнения.

1) За 1 раз выполняется только 1 строкова замена.
2) Если rule сработал - то возвращаемся к самому первому rule по списку.
3) Если левое выражение от стрелки - пустое - то это означает конкатенацию к голове результирующей строки.
4) Правое выражение пустое - просто удаляем подстроку.
5) Никаких if-else,for/do while не существует.

Вот. Надеюсь нормально пояснил.


Что приветстуется:

  • Ваши любые рассуждения и решения как это сделать. Сам я сейчас - не знаю как решить эту задачу. Тоесть нахожусь в одинаковых условиях с вами.
  • Любые реализации машины Маркова. С++/браузерные и теоретические.
  • Новые задачи и головоломки после того как решим эту.

Не приветсвтуется:

  • вопросы из серии "зачем это надо"
  • игнорирование алгоритмов НАМ


+ Некоторые подсказки которые я сам для себя нашел

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

Пример программы которая передвигает букву 'a' в конец слова.
*ab -> b*a
* |-> 
-> *


Input: abbbbb

Output: bbbbba

(обратите внимание. терминальная стрелочка стоит на второй позиции. Это важно. Если ее не там
поставить - мы получим зацикливание)

Некоторый формализм я сознательно скипал. Алфавиты и символы. И поэтому в литературе терминальная
стрелочка может рисоваться не так. Но нам пофиг.

+ Просто некоторые линки
https://en.wikipedia.org/wiki/Markov_algorithm Здесь есть пример перевода двоички в унарный код


Вот так.

Go-go думать!

Об оптимизации - не думаем. Нужно любое работающее решение.

Сообщение было отредактировано: 29 май 20, 07:36
28 май 20, 18:29    [22141543]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Алгоритм: сложение в столбик
28 май 20, 19:50    [22141617]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Ммм... да. Код давай.
28 май 20, 19:53    [22141624]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
exp98
Member

Откуда:
Сообщений: 2438
Может вопрос-таки об умножении?
28 май 20, 20:02    [22141629]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Давайте все таки начнем со сложения.
28 май 20, 20:11    [22141633]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Давайте все таки начнем со сложения.


1. двоичный код - в палки (для обоих слагаемых)
2. убрать плюс
3. палки - в двоичный код
28 май 20, 20:47    [22141655]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
+1

Одна процедура уже есть. Но мне кажется что обратная будет не так проста.
28 май 20, 21:19    [22141681]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Скопипащу с вики сюда. Что б было.

Конвертер с бинарного кода в унарный.

Rule
|0 -> 0||
1 -> 0|
0 ->


Для нашего примера.

Input:
1101+111

Output:
|||||||||||||+|||||||

Далее. Здесь надо аккуратно. Надо выкинуть плюсик но только после того
как оба слагаемых сконверчены в лесенку из палочек.
28 май 20, 22:21    [22141727]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
тут наверное на ассемблере было бы прикольно напрограммировать с побитовыми операциями...
ну типа прописать в память 0 и 1
но я ассемблера не знаю :(

Сообщение было отредактировано: 28 май 20, 22:35
28 май 20, 22:35    [22141743]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Этот топик - вообще не про Ассемблер.
28 май 20, 22:41    [22141753]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
mayton,

Проверил на ограниченном наборе. Правила формирования файла rule.txt: Сначала идут тестовые образцы в формате
Тест -> Ожидаемый результат
Если ожидаемый результат начинается с @ то после него идет функция получения результата от левой части
Образцы собираются до строки <<rules>>, все оставшееся это правила.
комментарии в правилах как в VB, Пустые строки игнорируются.

запуск через run.bat

'Двигаем очередной знак вправо
*0= -> <*=0>
*1= -> <*=1>
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>
'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

=1>e -> =$e1
=0>e -> =$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
=~ -> =1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0

'Забираем очередной знак
0<*=$ -> <*=0>
1<*=$ -> <*=1>
<*=$ -> 

'Двигаем символ конца расчетов
e1 -> 1e
e0 -> 0e
e+ -> @e

'Символ конца на месте, начинаем счет
@ -> <*=$

'правая часть больше левой 
<*=$ -> 

'Конец, терминальное правило так как строка заканчивается на |
e| -> 
'Затравка на первом проходе
 -> e


К сообщению приложен файл (nam.zip - 1Kb) cкачать
28 май 20, 23:17    [22141808]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
Забавная штука....

пример с хабра Нормальный алгоритм Маркова для деления чисел . Список замен немного изменен, так в этой машине символ | - служебный. Так что вместо него следует использовать #

К сообщению приложен файл (Rule.txt - 1Kb) cкачать
29 май 20, 00:13    [22141855]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
1101+111 =
1000 + 100 + 100 + 10 + 1 + 1 =
1000 + 100 + 100 + 10 + 10 =
1000 + 100 + 100 + 100 =
1000 + 1000 + 100 =
10000 + 100 = 10100
29 май 20, 01:30    [22141904]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
Поправил интерпретатор, что бы символ "|" не выпадал из алфавита. Обычные пары разделяются последовательностью " -> ", терминальные пары последовательностью " |-> "

К сообщению приложен файл (nam.zip - 2Kb) cкачать
29 май 20, 07:10    [22141958]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
В интерпретатор добавлена проверка перекрытия правил

К сообщению приложен файл (nam.zip - 2Kb) cкачать
29 май 20, 07:49    [22141963]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1491
mayton,
Зачем нужно terminal rule я не понял.

mayton
Об оптимизации - не думаем. Нужно любое работающее решение.

Так это элементарно. Надо просто перебрать все суммы двоичных чисел в диапазоне байта в лоб.
29 май 20, 08:31    [22141971]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
crutchmaster,

Ну... Я-же не создатель этого языка.

Terminal rule это чтото вроде условия выхода из рекурсии.

Часть алгоритмов без него обходятся. Ну и ладно.
29 май 20, 08:48    [22141975]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1491
mayton,

А, дошло. Если оно срабатывает или достигнут конец списка, то всё заканчивается.
29 май 20, 08:59    [22141976]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Swa111, спасибо. Посмотрю.

Но есть также онлайновые вычислители. Я находил несколько работающих в браузере.
И в Розетта-Код есть имплементации почти под все языки.

https://rosettacode.org/wiki/Execute_a_Markov_algorithm

Я думаю что надо собрать 1 бинарничек на сях под Windows и выложить сюда чтоб желающие пользовались.
29 май 20, 10:04    [22141996]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Swa111, ты гитхабом пользуешся? Ну я имею в виду.. Учетная запись там есть? Свои репозитарии?
29 май 20, 10:06    [22141999]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Щас я расскажу свою идею. Вобщем я сложение заменил на инкремент.

Поскольку НАМ очень удобно дебажить. Весь state программы укладывается в 1 строчку
я просто покажу как я думал это решать. Пока без кода а в виде модификаций строки.


# Наша исходная строка

|||||||||||||+|||||||

# Выкидываем знак плюс. Теперь число засечек уже равно сумме как в древних счётах.

||||||||||||||||||||

# Теперь нам нужен двоичный регистр сумматора. Я завожу два символа ^$ и между ними будет накапливаться 
# наш счетчик 

^$||||||||||||||||||||

# Далее. Тривиальные кейсы. Палочка транформируется сразу в двоичную единичку

^1$|||||||||||||||||||

Rules:
^$| -> ^1$

# Далее 1+1 = 2 мы фиксируем переполнение. Но перенесем чуть позже.

Rules:
^$| -> ^1$
1$| -> 2$

# Теперь перенос 2 в десятичной = 10 в двоичной

Rules:
^$| -> ^1$
1$| -> 2$
^2 -> ^10  # Это самый старший разряд
02 -> 10 # Это если двойка попалась в середине
12 -> 100 # Это если двойка попалась в середине 


Вот. Я это написал в уме сегодня ночью. И еще не проверял. Наверное там где-то есть зацикливание.
29 май 20, 10:17    [22142007]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1491
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.
29 май 20, 10:20    [22142012]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
crutchmaster
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.


Мммм.... чтоб рулы не пересекались - мы служебные символы можем ввести новые.

Например между первой и второй фазой делать

| -> *


И дальше оперировать звездочками.

Мне символов не жалко.
29 май 20, 10:23    [22142016]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Swa111, у меня твой алгоритм не сработал на вот этом эмуляторе http://www.cmcmsu.info/1course/alg.schema.nam.htm

Правильно ли я скопипастил?

*0= -> <*=0>
*1= -> <*=1>
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0
=1>e -> =$e1
=0>e -> =$e0
1~ -> ~0
0~ -> 1
=~ -> =1
1$ -> $1
0$ -> $0
0<*=$ -> <*=0>
1<*=$ -> <*=1>
<*=$ -> 
e1 -> 1e
e0 -> 0e
e+ -> @e
@ -> <*=$
<*=$ -> 
e |-> 
-> e


В пошаговом режиме пишет Ни одно правило не применено, либо выполнено терминальное правило.
29 май 20, 10:32    [22142019]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
mayton
Мне символов не жалко.

Хотя да. Я думаю что Марков пожадничал. Надо было ввести в язык поняти стека и вызва процедуры или функции.
Но он наверное как и все теоретики просто что-то на бумаге хотел доказать. Типа равна ли эта хрень Машинке Тьюринга.
29 май 20, 10:47    [22142039]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
mayton,

да на гите я есть, но пользуюсь редко

на сайте не сработал наверное из за того что там ограничение на число правил, не более 20. Либо там другой синтаксис

Пошаговый расчет можно получить и в моем интерпретаторе, просто в образцах справа задай не верные результат, тогда выдаст пошаговое выполнение.
29 май 20, 11:18    [22142068]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Я возьму с розетты еще одну реализацию чтоб уже работала без ограничений.
Кстати это хорошо что ты добавил каменты в рулы. Я тоже расширю этот убогий
язык для такой возможности.
29 май 20, 11:25    [22142071]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
палки в двоичную

0|| |0
0| 1
|| |0
| 1
29 май 20, 12:26    [22142121]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov,

спасибо Саш. Попробую.
29 май 20, 12:29    [22142126]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1491
mayton,

Да дело не в *|, а в 1/0. Первая часть переводит из в палки, вторая из палок. После первого преобразования из палки в 1/0 число тут же станет палкой.

Сообщение было отредактировано: 29 май 20, 12:54
29 май 20, 12:55    [22142164]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
crutchmaster,

замени палки на слеши
29 май 20, 13:04    [22142179]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1491
Aleksandr Sharahov,

И что?

:start
1->|
...
|->1 //goto :start

1/0 не на что заменить они должны быть в выхлопе.

Сообщение было отредактировано: 29 май 20, 13:05
29 май 20, 13:07    [22142181]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
//правила
  ('+','<^>'),
  ('1<','<3'),
  ('0<','<2'),
  ('<',''),
  ('>1','3>'),
  ('>0','2>'),
  ('>',''),
  ('|2','2||'),
  ('3','2|'),
  ('2',''),
  ('^',''),
  ('0||','|0'),
  ('0|','1'),
  ('||','|0'),
  ('|','1')

//выхлоп
101+11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33
2|23^33
22||3^33
22||2|^33
22|2|||^33
222|||||^33
222|||||^2|3
222|||||^2|2|
222|||||^22|||
22|||||^22|||
2|||||^22|||
|||||^22|||
|||||^2|||
|||||^|||
||||||||
|0||||||
||0||||
|||0||
||||0
|0||0
||00
|000
1000
29 май 20, 13:37    [22142210]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Еще мысли. Утилитарные задачи. Не связанные с вычислениями а скорре так. Проблемы.

Например

1) Априорное знание алфавита. Если делать swap или движение какого-то символа в какую-то сторону
мы должны в левой части rules предусмотреть этот символ в сочетании со всеми возможными комбинациями.
Описать регулярку или мета-символ мы не можем. Господин Марков этого не предусмотрел. Следовательно
надо как-то опираться на область входных значений.

2) Утилитарные функции которые могут пригодится. Одну из них мы уже почти сделали. Это перевод
из двоички в унарность и обратно. Для комплекта хорошо-бы сделать тоже самое для десятичной.
Шестнадцатеричная из двоичной переводится тривиально. Плюс четыре базовых арифметических
операции.

Я думаю гуглёж всегда помогает - но прошу тех кто уже нагуглил - не спойлерите а дайте ребятам
возможность самим подумать. Я думаю 1-2 недели - это нормальный строк для этого топика.
29 май 20, 14:55    [22142271]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton,

мое умножение и вычитание под спойлером, насчет деления не ясно, куда девать остаток
+

//умножение
('*','<^>'),
('1<','<3'),
('0<','<2'),
('<',''),
('>1','3>'),
('>0','2>'),
('>',''),
('|2','2||'),
('3','2|'),
('2',''),
('|^','^='),
('^',''),
('=|','|/='),
('=/','/='),
('|',''),
('=',''),
('0//','/0'),
('0/','1'),
('//','/0'),
('/','1')

//пример умножения
101*11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33
2|23^33
22||3^33
22||2|^33
22|2|||^33
222|||||^33
222|||||^2|3
222|||||^2|2|
222|||||^22|||
22|||||^22|||
2|||||^22|||
|||||^22|||
|||||^2|||
|||||^|||
||||^=|||
|||^==|||
||^===|||
|^====|||
^=====|||
=====|||
====|/=||
===|/=/=||
==|/=/=/=||
=|/=/=/=/=||
|/=/=/=/=/=||
|/=/=/=/=/|/=|
|/=/=/=/=/|/|/=
|//==/=/=/|/|/=
|//=/==/=/|/|/=
|///===/=/|/|/=
|///==/==/|/|/=
|///=/===/|/|/=
|////====/|/|/=
|////===/=|/|/=
|////===/|/=/|/=
|////==/=|/=/|/=
|////==/|/=/=/|/=
|////=/=|/=/=/|/=
|////=/|/=/=/=/|/=
|/////=|/=/=/=/|/=
|/////|/=/=/=/=/|/=
|/////|//==/=/=/|/=
|/////|//=/==/=/|/=
|/////|///===/=/|/=
|/////|///==/==/|/=
|/////|///=/===/|/=
|/////|////====/|/=
|/////|////===/=|/=
|/////|////===/|/=/=
|/////|////==/=|/=/=
|/////|////==/|/=/=/=
|/////|////=/=|/=/=/=
|/////|////=/|/=/=/=/=
|/////|/////=|/=/=/=/=
|/////|/////|/=/=/=/=/=
|/////|/////|//==/=/=/=
|/////|/////|//=/==/=/=
|/////|/////|///===/=/=
|/////|/////|///==/==/=
|/////|/////|///=/===/=
|/////|/////|////====/=
|/////|/////|////===/==
|/////|/////|////==/===
|/////|/////|////=/====
|/////|/////|/////=====
/////|/////|/////=====
//////////|/////=====
///////////////=====
///////////////====
///////////////===
///////////////==
///////////////=
///////////////
/0/////////////
//0///////////
///0/////////
////0///////
/////0/////
//////0///
///////0/
///////1
/0/////1
//0///1
///0/1
///11
/0/11
/111
1111


//вычитание
('-','<^>'),
('1<','<3'),
('0<','<2'),
('<',''),
('>1','3>'),
('>0','2>'),
('>',''),
('|2','2||'),
('3','2|'),
('2',''),
('|^|','^'),
('|^','|'),
('0||','|0'),
('0|','1'),
('||','|0'),
('|','1'),
('^1','.-1'), //точка означает терминальную операцию
('^','0')

//пример вычитания
101-111
101<^>111
10<3^>111
1<23^>111
<323^>111
323^>111
323^3>11
323^33>1
323^333>
323^333
2|23^333
22||3^333
22||2|^333
22|2|||^333
222|||||^333
222|||||^2|33
222|||||^2|2|3
222|||||^22|||3
222|||||^22|||2|
222|||||^22||2|||
222|||||^22|2|||||
222|||||^222|||||||
22|||||^222|||||||
2|||||^222|||||||
|||||^222|||||||
|||||^22|||||||
|||||^2|||||||
|||||^|||||||
||||^||||||
|||^|||||
||^||||
|^|||
^||
^|0
^10
-10
29 май 20, 16:42    [22142346]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov,

ого
29 май 20, 16:49    [22142351]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
Измененный алгоритм, число слагаемых может быть любым. На больших числах выигрывает по скорости счету на "счетных палочках".

+
'Закидываем сразу символ конца расчета за +
+ -> ?e

'Двигаем очередной знак вправо
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>

'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

#1>e -> #$e1
#0>e -> #$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
#~ -> #1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0

'Забираем очередной знак
0#$ -> #0>
1#$ -> #1>

#$e |-> 

e#$ -> #$

'правая часть больше левой 
#$ -> 

'Двигаем символ конца расчетов
e1 -> 1e
e0 -> 0e

'Символ конца на месте, начинаем счет
? -> #$

'Конец
e |-> 


Пример 1+11+100+10 ==> 1010
+

+ -> ?e      : 1?e11+100+10
+ -> ?e : 1?e11?e100+10
+ -> ?e : 1?e11?e100?e10
e1 -> 1e : 1?1e1?e100?e10
e1 -> 1e : 1?11e?e100?e10
e1 -> 1e : 1?11e?1e00?e10
e1 -> 1e : 1?11e?1e00?1e0
e0 -> 0e : 1?11e?10e0?1e0
e0 -> 0e : 1?11e?100e?1e0
e0 -> 0e : 1?11e?100e?10e
? -> #$ : 1#$11e?100e?10e
1#$ -> #1> : #1>11e?100e?10e
1>1 -> 11> : #11>1e?100e?10e
1>1 -> 11> : #111>e?100e?10e
11>e -> ~$e0 : #1~$e0?100e?10e
1~ -> ~0 : #~0$e0?100e?10e
#~ -> #1 : #10$e0?100e?10e
0$ -> $0 : #1$0e0?100e?10e
1$ -> $1 : #$10e0?100e?10e
#$ -> : 10e0?100e?10e
e0 -> 0e : 100e?100e?10e
? -> #$ : 100e#$100e?10e
e#$ -> #$ : 100#$100e?10e
0#$ -> #0> : 10#0>100e?10e
0>1 -> 10> : 10#10>00e?10e
0>0 -> 00> : 10#100>0e?10e
0>0 -> 00> : 10#1000>e?10e
00>e -> $e0 : 10#10$e0?10e
0$ -> $0 : 10#1$0e0?10e
1$ -> $1 : 10#$10e0?10e
0#$ -> #0> : 1#0>10e0?10e
0>1 -> 10> : 1#10>0e0?10e
0>0 -> 00> : 1#100>e0?10e
00>e -> $e0 : 1#1$e00?10e
1$ -> $1 : 1#$1e00?10e
1#$ -> #1> : #1>1e00?10e
1>1 -> 11> : #11>e00?10e
11>e -> ~$e0 : #~$e000?10e
#~ -> #1 : #1$e000?10e
1$ -> $1 : #$1e000?10e
#$ -> : 1e000?10e
e0 -> 0e : 10e00?10e
e0 -> 0e : 100e0?10e
e0 -> 0e : 1000e?10e
? -> #$ : 1000e#$10e
e#$ -> #$ : 1000#$10e
0#$ -> #0> : 100#0>10e
0>1 -> 10> : 100#10>0e
0>0 -> 00> : 100#100>e
00>e -> $e0 : 100#1$e0
1$ -> $1 : 100#$1e0
0#$ -> #0> : 10#0>1e0
0>1 -> 10> : 10#10>e0
10>e -> $e1 : 10#$e10
0#$ -> #0> : 1#0>e10
#0>e -> #$e0 : 1#$e010
1#$ -> #1> : #1>e010
#1>e -> #$e1 : #$e1010
#$e -> : 1010


110101+110 ==> 111011
+
+ -> ?e      : 110101?e110
e1 -> 1e : 110101?1e10
e1 -> 1e : 110101?11e0
e0 -> 0e : 110101?110e
? -> #$ : 110101#$110e
1#$ -> #1> : 11010#1>110e
1>1 -> 11> : 11010#11>10e
1>1 -> 11> : 11010#111>0e
1>0 -> 01> : 11010#1101>e
01>e -> $e1 : 11010#11$e1
1$ -> $1 : 11010#1$1e1
1$ -> $1 : 11010#$11e1
0#$ -> #0> : 1101#0>11e1
0>1 -> 10> : 1101#10>1e1
0>1 -> 10> : 1101#110>e1
10>e -> $e1 : 1101#1$e11
1$ -> $1 : 1101#$1e11
1#$ -> #1> : 110#1>1e11
1>1 -> 11> : 110#11>e11
11>e -> ~$e0 : 110#~$e011
#~ -> #1 : 110#1$e011
1$ -> $1 : 110#$1e011
0#$ -> #0> : 11#0>1e011
0>1 -> 10> : 11#10>e011
10>e -> $e1 : 11#$e1011
1#$ -> #1> : 1#1>e1011
#1>e -> #$e1 : 1#$e11011
1#$ -> #1> : #1>e11011
#1>e -> #$e1 : #$e111011
#$e -> : 111011
29 май 20, 17:36    [22142376]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov

101*11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33



Хм.. Это преобразование со стороны выглядит странно. Оно как будто-бы ничего не делает. Просто заменяет
одни цифры на другие. И знак * наверное можно было сохранить.
29 май 20, 18:26    [22142397]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Aleksandr Sharahov

101*11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33



Хм.. Это преобразование со стороны выглядит странно. Оно как будто-бы ничего не делает. Просто заменяет
одни цифры на другие. И знак * наверное можно было сохранить.


Дык это легко поверить, достаточно убрать "ненужное" )
29 май 20, 18:49    [22142410]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111,

правильно ли я понял, что в твоей реализации
количество правил зависит от количества бит в наибольшем слагаемом?
29 май 20, 19:01    [22142413]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov
mayton
пропущено...


Хм.. Это преобразование со стороны выглядит странно. Оно как будто-бы ничего не делает. Просто заменяет
одни цифры на другие. И знак * наверное можно было сохранить.


Дык это легко поверить, достаточно убрать "ненужное" )

Нет. Я понимаю что мы подготавливаем почву для других расчетов. Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".
29 май 20, 19:28    [22142426]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Aleksandr Sharahov
пропущено...


Дык это легко поверить, достаточно убрать "ненужное" )

Нет. Я понимаю что мы подготавливаем почву для других расчетов. Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".


Ну, мне так проще конструировать алгоритм:
мы таким образом гарантируем, что входные символы не пересекаются с выходными,
и, тем самым, при формировании результата не будет срабатываний замен из начала списка,
которые испортят всю малину.
29 май 20, 20:14    [22142458]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
Aleksandr Sharahov,

Нет, число правил одинаковое для чисел любой разрядности.

Алгоритм умножения чисел в столбик. Отчасти полагается на предыдущий алгоритм сложения нескольких чисел.
всего за каких то 9949 замен может перемножить числа 1000100111111000 на 1000110101111101
+
* -> ME

'E всегда идет в конце слова
E0 -> 0E
E1 -> 1E
'где потом мельчает
E -> e

'Гонцы тоже идут в конец слова
p0 -> 0p
p1 -> 1p
P0 -> 0P
P1 -> 1P

'Мутация гонца
1Pe -> |c1e1eA
0Pe -> |c0e0eA

'грузчик тащит копию цифры на право
1|c -> |11g
0|c -> |00g

0g0 -> 00g
0g1 -> 10g
1g0 -> 01g
1g1 -> 11g

'Сбрасывает свою цыфру и идет за следующей
0ge -> ce0
1ge -> ce1
0c -> c0
1c -> c1

'передает следующему
m|c -> mp

'Гонцы
'Умножить число слева на 2
0M -> mp
1M -> mP

'Умножение на 2
pe -> w0e

'Умножитель возвращается обратно
0w -> w0
1w -> w1
mw -> M

'Стираем последнее слагаемое оно больше не нужно
q1 -> q
q0 -> q
qe -> 
M -> q


'Двигаем очередной знак вправо для сложения
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>

'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

A1>e -> A$e1
A0>e -> A$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
A~ -> A1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0


'Забираем очередной знак
0A$ -> A0>
1A$ -> A1>


'Набор правил что бы подчистить за собой
A$e0 -> A$e
A$e -> 
eA$ -> A
A1> -> 1
A0> -> 0
A -> A$


Обновил интерпретатор, исправлена ошибка с зависанием если ни одно правило не сработало.
Добавлено:
  • вывод статистики: шагов / замен.
  • "говорливый" режим выполнения, когда каждый шаг выводится в консоль
  • поддержка комментариев с символа #.
  • вывод правил, которые ни разу не использовались.

В архиве 2 батника. Использование: в проводнике перетащить файл с правилами на батник.

К сообщению приложен файл (nam.zip - 4Kb) cкачать
29 май 20, 20:39    [22142472]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
незамутненное преобразованиями систем счисления деление на палках
+
//деление 
  ('>|',  '|>'),
  ('>/',  '|-='),
  ('=|',  'i|='),
  ('=#',  '#|'),
  ('=',   '#|'),
  ('|i',  'i|'),
  ('|-i', '-'),
  ('|-|', '|-=|'),
  ('-|',  '-'),
  ('-i',  '-'),
  ('-#||', '.|'), //exit
  ('-#|',  '.0'), //exit
  ('',    '>')

//делим 7 на 3
|||||||/|||
>|||||||/|||
|>||||||/|||
||>|||||/|||
|||>||||/|||
||||>|||/|||
|||||>||/|||
||||||>|/|||
|||||||>/|||
||||||||-=|||
||||||||-i|=||
||||||||-i|i|=|
||||||||-i|i|i|=
||||||||-i|i|i|#|
||||||||-ii||i|#|
||||||||-ii|i||#|
||||||||-iii|||#|
|||||||-ii|||#|
||||||-i|||#|
|||||-|||#|
|||||-=|||#|
|||||-i|=||#|
|||||-i|i|=|#|
|||||-i|i|i|=#|
|||||-i|i|i|#||
|||||-ii||i|#||
|||||-ii|i||#||
|||||-iii|||#||
||||-ii|||#||
|||-i|||#||
||-|||#||
||-=|||#||
||-i|=||#||
||-i|i|=|#||
||-i|i|i|=#||
||-i|i|i|#|||
||-ii||i|#|||
||-ii|i||#|||
||-iii|||#|||
|-ii|||#|||
-i|||#|||
-|||#|||
-||#|||
-|#|||
-#|||
||
29 май 20, 22:07    [22142502]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
немного сократил
+
//деление 
  ('/',   '|-='),
  ('=|',  'i|='),
  ('=#',  '#|'),
  ('=',   '#'),
  ('|i',  'i|'),
  ('|-i', '-'),
  ('|-|', '|-=|'),
  ('-|',  '-'),
  ('-i',  '-'),
  ('-#|', '|'),
  ('-#',  '0')
29 май 20, 22:26    [22142507]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".


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

Поэтому достаточно реализовать НАМы для унарной системы счисления,
т.к. у нас есть функции перевода в нее и обратно.
29 май 20, 23:21    [22142525]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Унарное вычитание
1-1 -> -
- -> 


Input: 11111-111

Output: 11
29 май 20, 23:46    [22142533]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov
mayton
Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".


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

Поэтому достаточно реализовать НАМы для унарной системы счисления,
т.к. у нас есть функции перевода в нее и обратно.


Я вот щас какраз думаю над композицией функций. У нас есть универсальный
аппарат. И есть уже кодовая база.

В функциональщине есть такая штука если есть f(x), g(x) функции то
f(g(x)) это некая новая функция которая последовательно применяет g а потом f.

Если бы не было терминального оператора |-> то мы могли-бы просто
копи-пастой формировать композиции алгоритмов Маркова просто
как плоский текст.

И если-бы не было пересечений алфавитов левых выражений rules.
30 май 20, 00:08    [22142536]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
перевод из десятичной в унарную
+

r1e -> ei
r0e -> eo

E0 -> 0E
E1 -> 1E
E2 -> 2E
E3 -> 3E
E4 -> 4E
E5 -> 5E
E6 -> 6E
E7 -> 7E
E8 -> 8E
E9 -> 9E

E -> e$

r00 -> 0r0
r01 -> 0r1
r0 -> r
r2 -> 1r0
r3 -> 1r1
r4 -> 2r0
r5 -> 2r1
r6 -> 3r0
r7 -> 3r1
r8 -> 4r0
r9 -> 4r1
r10 -> 5r0
r11 -> 5r1
r12 -> 6r0
r13 -> 6r1
r14 -> 7r0
r15 -> 7r1
r16 -> 8r0
r17 -> 8r1
r18 -> 9r0
r19 -> 9r1

G0e -> o
G1e -> i
G2 -> G1r0
G3 -> G1r1
G4 -> G2r0
G5 -> G2r1
G6 -> G3r0
G7 -> G3r1
G8 -> G4r0
G9 -> G4r1
G10 -> G5r0
G11 -> G5r1
G12 -> G6r0
G13 -> G6r1
G14 -> G7r0
G15 -> G7r1
G16 -> G8r0
G17 -> G8r1
G18 -> G9r0
G19 -> G9r1

i -> o|
|o -> o||
o -> 

$ |-> 

 -> GE


30 май 20, 00:11    [22142539]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
Aleksandr Sharahov,

в делении наверное это правило лишнее
 ('-#',  '0')
30 май 20, 00:38    [22142547]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111
Aleksandr Sharahov,

в делении наверное это правило лишнее
 ('-#',  '0')


так сделано по двум причинам:
1. для отладки, чтобы видеть пустой результат в мемо
2. для упрощения перевода результата в двоичную

если не требуется ни то, ни другое, то две последних строки можно заменить одной
('-#', '')

Сообщение было отредактировано: 30 май 20, 00:57
30 май 20, 00:57    [22142555]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111
перевод из десятичной в унарную


а мы не гонимся за скоростью )
+
  ('|0','0||||||||||'),
  ('1', '0|'),
  ('2', '0||'),
  ('3', '0|||'),
  ('4', '0||||'),
  ('5', '0|||||'),
  ('6', '0||||||'),
  ('7', '0|||||||'),
  ('8', '0||||||||'),
  ('9', '0|||||||||'),
  ('0', '')
30 май 20, 01:13    [22142560]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
в десятичную
+
  
  ('#9|', '#10'),
  ('9|',  '|0'),
  ('8|',  '9'),
  ('7|',  '8'),
  ('6|',  '7'),
  ('5|',  '6'),
  ('4|',  '5'),
  ('3|',  '4'),
  ('2|',  '3'),
  ('1|',  '2'),
  ('0|',  '1'),
  ('#',   '.'), //exit
  ('',    '#0')
30 май 20, 01:35    [22142567]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
пусть дано: "1111+111"

решение:
1) преобразовываем строку на входе к виду #00#10#11#11#11#
2) далее на преобразованной строке применяем правила
"00" -> "0"
"01" -> "1"
"10" -> "1"
"#0#11#" -> "#1#0#"
"#1#11#" -> "#11#0#"

если не получилось применить ни одного из правил, то выходим из цикла

3) стираем "#" и получаем результат
10110
30 май 20, 03:08    [22142581]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
mini.weblab,

Это что? Сложение в четверичной системе?

Мне кажется - первый шаг слабо обоснован.
30 май 20, 09:02    [22142602]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov
Swa111
перевод из десятичной в унарную


а мы не гонимся за скоростью )
+
  ('|0','0||||||||||'),
  ('1', '0|'),
  ('2', '0||'),
  ('3', '0|||'),
  ('4', '0||||'),
  ('5', '0|||||'),
  ('6', '0||||||'),
  ('7', '0|||||||'),
  ('8', '0||||||||'),
  ('9', '0|||||||||'),
  ('0', '')

Это шикарно
30 май 20, 10:25    [22142622]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
пусть дано: "1111+111"

решение:
1) преобразовываем строку на входе к виду #00#10#11#11#11#
2) далее на преобразованной строке применяем правила
"00" -> "0"
"01" -> "1"
"10" -> "1"
"#0#11#" -> "#1#0#"
"#1#11#" -> "#11#0#"

если не получилось применить ни одного из правил, то выходим из цикла

3) стираем "#" и получаем результат
10110


непосредственное сложение в двоичной системе достаточно очевидно,
но реализаций могут быть десятки,
вот, например, моя реализация
+
//двоичное сложение
  ('+',   '^>'),
  ('>0',  '0>'),
  ('>1',  '1>'),
  ('>',   '#'),
  ('o#',  '#0'),
  ('o0#', '#0'),
  ('o1#', '#1'),
  ('o0',  '0o'),
  ('o1',  '1o'),
  ('i#',  '#1'),
  ('i0#', '#1'),
  ('i1#', '#2'),
  ('i0',  '0i'),
  ('i1',  '1i'),
  ('0^',  '^o'),
  ('1^',  '^i'),
  ('#', ''),
  ('02',  '10'),
  ('12',  '20'),
  ('^2',  '10'),
  ('^', '')

//пример
11+1010
11^>1010
11^1>010
11^10>10
11^101>0
11^1010>
11^1010#
1^i1010#
1^1i010#
1^10i10#
1^101i0#
1^101#1
^i101#1
^1i01#1
^10i1#1
^10#21
^1021
^1101
1101
30 май 20, 10:40    [22142626]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Из всех систем счисления - десятичная самая неудобная для этих операций.
30 май 20, 12:14    [22142645]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Саша как тебе такая идея?

F = 8 + 8
8 = 4 + 4
4 = 2 + 2
2 = 1 + 1 = | + | = ||
1 = |
30 май 20, 12:15    [22142647]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Саша как тебе такая идея?

F = 8 + 8
8 = 4 + 4
4 = 2 + 2
2 = 1 + 1 = | + | = ||
1 = |


идея применительно к чему?
а то у нас уже тут до фига всего.
30 май 20, 12:50    [22142655]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Мне почему-то всмомнилась идея Египетского Умножения.

Тоесть взять любую систему счисления. И заменить умножение
сложением. С небольшим числом слагаемых.
30 май 20, 12:54    [22142656]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Например (в десятичной)

731 * 13 = 731 * (1 + 4 + 8) = 731 + (( 731 + 731 ) + ( 731 + 731 )) + .... и т.д.

Получается как-бы такое бинарное дерево сложений. И здесь 4 * 731 разваливается на две частичные слагаемые
которые в императивных языках хорошо оптимизируются.

Вобщем в императивных языках у нас будет не 13 сложений а нечто логарифмическое.
30 май 20, 13:00    [22142658]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Сделал двоичное умножение, вышло достаточно быстро:
1000100111111000*1000110101111101 = 5190 замен
1000110101111101*1000100111111000 = 6006 замен

+
//двоичное умножение
  '*',   '^>',
  '>0',  '0>',
  '>1',  '1>',
  '>',   '+0#',
  '^0',  '^',
  'o0',  '0o',
  'o1',  '1o',
  'o+',  '0+',
  'i0',  '0i',
  'i1',  '1i',
  'i+',  '<0+',
  'z0#', '=0#',
  'z1#', '=1#',
  'z=',  '=0',
  'z0=', '=0',
  'z1=', '=1',
  'z0',  '0z',
  'z1',  '1z',
  'j0#', '=1#',
  'j1#', '=2#',
  'j=',  '=1',
  'j0=', '=1',
  'j1=', '=2',
  'j0',  '0j',
  'j1',  '1j',
  'O0',  '0O',
  'O1',  '1O',
  'O+',  '+z',
  'I0',  '0I',
  'I1',  '1I',
  'I+',  '+j',
  '0<',  '<0O',
  '1<',  '<1I',
  '0^<',  '0^',
  '1^<',  '1^',
  '=',   '',
  '02',  '10',
  '12',  '20',
  '+2',  '+10',
  'x0',  'x',
  'x1',  'x',
  'x+',  '',
  '0^',  '^o',
  '1^',  '^i',
  '^<',  'x',
  '^',   'x',
  '#',   ''

//двоичное умножение, пример
       шаг  прав  формула
         0    -1  11*11
         1     0  11^>11
         2     2  11^1>1
         3     2  11^11>
         4     3  11^11+0#
         5    43  1^i11+0#
         6     9  1^1i1+0#
         7     9  1^11i+0#
         8    10  1^11<0+0#
         9    32  1^1<1I0+0#
        10    28  1^1<10I+0#
        11    30  1^1<10+j0#
        12    18  1^1<10+=1#
        13    32  1^<1I10+=1#
        14    29  1^<11I0+=1#
        15    28  1^<110I+=1#
        16    30  1^<110+j=1#
        17    20  1^<110+=11#
        18    34  1^110+=11#
        19    35  1^110+11#
        20    43  ^i110+11#
        21     9  ^1i10+11#
        22     9  ^11i0+11#
        23     8  ^110i+11#
        24    10  ^110<0+11#
        25    31  ^11<0O0+11#
        26    25  ^11<00O+11#
        27    27  ^11<00+z11#
        28    17  ^11<00+1z1#
        29    12  ^11<00+1=1#
        30    32  ^1<1I00+1=1#
        31    28  ^1<10I0+1=1#
        32    28  ^1<100I+1=1#
        33    30  ^1<100+j1=1#
        34    22  ^1<100+=21#
        35    32  ^<1I100+=21#
        36    29  ^<11I00+=21#
        37    28  ^<110I0+=21#
        38    28  ^<1100I+=21#
        39    30  ^<1100+j=21#
        40    20  ^<1100+=121#
        41    35  ^<1100+121#
        42    37  ^<1100+201#
        43    38  ^<1100+1001#
        44    44  x1100+1001#
        45    40  x100+1001#
        46    40  x00+1001#
        47    39  x0+1001#
        48    39  x+1001#
        49    41  1001#
        50    46  1001

//статистика
количество  прав    замена
         1     0     *  ^>
         0     1    >0  0>
         2     2    >1  1>
         1     3     >  +0#
         0     4    ^0  ^
         0     5    o0  0o
         0     6    o1  1o
         0     7    o+  0+
         1     8    i0  0i
         4     9    i1  1i
         2    10    i+  <0+
         0    11   z0#  =0#
         1    12   z1#  =1#
         0    13    z=  =0
         0    14   z0=  =0
         0    15   z1=  =1
         0    16    z0  0z
         1    17    z1  1z
         1    18   j0#  =1#
         0    19   j1#  =2#
         2    20    j=  =1
         0    21   j0=  =1
         1    22   j1=  =2
         0    23    j0  0j
         0    24    j1  1j
         1    25    O0  0O
         0    26    O1  1O
         1    27    O+  +z
         6    28    I0  0I
         2    29    I1  1I
         4    30    I+  +j
         1    31    0<  <0O
         4    32    1<  <1I
         0    33   0^<  0^
         1    34   1^<  1^
         2    35     =  
         0    36    02  10
         1    37    12  20
         1    38    +2  +10
         2    39    x0  x
         2    40    x1  x
         1    41    x+  
         0    42    0^  ^o
         2    43    1^  ^i
         1    44    ^<  x
         0    45     ^  x
         1    46     #  
30 май 20, 16:35    [22142743]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Например (в десятичной)

731 * 13 = 731 * (1 + 4 + 8) = 731 + (( 731 + 731 ) + ( 731 + 731 )) + .... и т.д.

Получается как-бы такое бинарное дерево сложений. И здесь 4 * 731 разваливается на две частичные слагаемые
которые в императивных языках хорошо оптимизируются.

Вобщем в императивных языках у нас будет не 13 сложений а нечто логарифмическое.


для двоичной системы как раз и получится умножение в столбик
30 май 20, 16:48    [22142748]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Практическое применение алгоритма Маркова: сложение в столбик
Code link:
https://repl.it/repls/RepulsiveRowdyCareware

Сообщение было отредактировано: 30 май 20, 17:16
30 май 20, 17:12    [22142754]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab,

Во-первых, там не умножение, а сложение.
Во-вторых, совсем не по Маркову.
30 май 20, 17:18    [22142756]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм
30 май 20, 17:22    [22142760]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм


Перенос переполнения в старший разряд - он не Марковский, а общечеловеческий )
Марковость - это (то, чего там вовсе нет):
1. задать таблицу замен,
2. взять строку с исходной формулой,
3. по Марковкому алгоритму применять замены к формуле до тех пор, пока алгоритм не остановится.
30 май 20, 17:30    [22142761]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
mini.weblab
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм

Как-то... переусложнено всё. Ты-же понимаешь что НАМ - это чистейшая теория.
Мозговой эксперимент. И если ты вводишь императивный язык как подпорку или
костыль что-бы НАМ улучшить то это уже совсем другой метод.
30 май 20, 17:32    [22142762]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
ммм... нет, я перехожу от абстракции к конкретному примеру,
и дальше показываю, что умножение в столбик тоже относится к группе алгоритмов Маркова
для этого я переписываю начальную строку, так, как мне нужно для примера, и применяю серию правил (их у меня 5)
30 май 20, 17:56    [22142782]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
ммм... нет, я перехожу от абстракции к конкретному примеру,
и дальше показываю, что умножение в столбик тоже относится к группе алгоритмов Маркова
для этого я переписываю начальную строку, так, как мне нужно для примера, и применяю серию правил (их у меня 5)


Давай, рассмотрим сложение двоичных чисел на примере выражения '101+11'.

Какие правила нам надо применить, чтобы последовательными
преобразованиями исходного выражения получить результирующую строку '1000' ?
30 май 20, 18:18    [22142794]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Aleksandr Sharahov,

Input string: #00#10#01#11#
00->0: #0#10#01#11#
01->1: #0#10#1#11#
10->1: #0#1#1#11#
#1#11#->#11#0#: #0#1#11#0#
#1#11#->#11#0#: #0#11#0#0#
#0#11#->#1#0#: #1#0#0#0#
Exit string: #1#0#0#0#
30 май 20, 18:29    [22142802]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,

Input string: #00#10#01#11#
00->0: #0#10#01#11#
01->1: #0#10#1#11#
10->1: #0#1#1#11#
#1#11#->#11#0#: #0#1#11#0#
#1#11#->#11#0#: #0#11#0#0#
#0#11#->#1#0#: #1#0#0#0#
Exit string: #1#0#0#0#


Давай разбираться с самого начала.
Откуда взялось это выражение '#00#10#01#11#' ?
Какое правило было применено к исходному выражению '101+11' ?
30 май 20, 18:33    [22142804]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Aleksandr Sharahov,

мы решаем разные задачи, в самом первом посте, я сказала, что покажу, что сложение в столбик выполняется по алгоритму Маркова.
и дальше просто идет proof of concept. :-)
я хочу сказать, а почему бы не посмотреть на проблему под другим углом. :-)
30 май 20, 18:55    [22142813]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,

мы решаем разные задачи, в самом первом посте, я сказала, что покажу, что сложение в столбик выполняется по алгоритму Маркова.
и дальше просто идет proof of concept. :-)
я хочу сказать, а почему бы не посмотреть на проблему под другим углом. :-)


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

От того, что некоторые правила записаны стрелочками, весь алгоритм сложения не становится Марковским,
т.к. не соблюдены *все* необходимые требования.
30 май 20, 19:08    [22142818]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Aleksandr Sharahov
м,
т.к. не соблюдены *все* необходимые требования.

1) и какие же требования не соблюдены?
а) строка есть
б) правила есть
в) все шаги алгоритма выполнены
г) конечный ответ получен
2) сложение в столбик может быть приведено к Марковскому алгоритму, нужно лишь записать строку нужным нам образом
30 май 20, 20:47    [22142853]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Aleksandr Sharahov,
я знаю, что решетки # это чит, но идея состоит в том, чтобы воспроизвести сложение в столбик
:-)

PS
а если число преобразовывать, и решетки убирать, то остаются 2 правила (как в твоем решении)
12->20
02->10


111111 + 111
0111222

12->20: 0112022
02->10: 0112102
02->10: 0112110
12->20: 0120110
12->20: 0200110
02->10: 1000110

Res: 1000110
30 май 20, 21:40    [22142877]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,
я знаю, что решетки # это чит, но идея состоит в том, чтобы воспроизвести сложение в столбик
:-)

PS
а если число преобразовывать, и решетки убирать, то остаются 2 правила (как в твоем решении)
12->20
02->10


111111 + 111
0111222

12->20: 0112022
02->10: 0112102
02->10: 0112110
12->20: 0120110
12->20: 0200110
02->10: 1000110


Res: 1000110


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

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

Речь о том, что этого всего не хватает.
30 май 20, 22:17    [22142888]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
Aleksandr Sharahov,

я знаю, что формально для решения задачи as is этого не хватает, но у меня были другие цели
30 май 20, 22:40    [22142893]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
более шустрый алгоритм сложения и умножения в столбик

1000100111111000*1000110101111101 = 4049 замен
1000110101111101*1000100111111000 = 4386 замен

+
0t10 -> 100t
0t1 -> 10t
1g00 -> 001g
0g1 -> 10g
1g1 -> 11g
E1 -> 1E
E0 -> 0E
E -> e
s0t0t -> 00
s1t0t -> 10
1t0 -> 01t
s1t1t -> 11
1t1 -> 11t
c0 -> 0c
1g0 -> 01g
0g0000 -> 00000g
0gDe -> De0
00teS -> e0eS
00te -> e0
10teS -> e1eS
10te -> e1
11te -> ~e0
0t0000 -> 00000t
0t00 -> 000t
d0 -> 0d
0t0 -> 00t
0g00 -> 000g
0g0 -> 00g
c1 -> 1c
1gDe -> De1
0p -> p00g
1p -> p11g
d1 -> 1d
1~ -> ~0
m0 -> m
01te -> e1
0~ -> 1
s~ -> s1
D -> 0
p -> 
0ce -> p0De0eS
de -> 0e
1ce -> p1De1eS
1m -> mc
0m -> md
m1 -> m
se -> 
0s -> s0t
1s -> s1t
0eS -> s0t
me -> 
s1e -> 1
1* -> mcE
0+ -> s0tE
1+ -> s1tE
0* -> mdE
s1 -> 1
1eS -> s1t
e -> 
s0 -> s

В интерпретатор добавлен оптимизатор порядка правил. Для этого в командной строке запустите с ключам /o и /s или используйте DropAtMe(Opt).bat.
В файле все образцы должны быть с верными эталонными значениями. Образцы нужно подобрать таким образом что бы использовались все правила. Оптимизатор только переставляет правила местами для того что бы уменьшить число итераций (не замен). Если перестановка увеличила число шагов или какой либо из образцов перестал быть равным эталону то она отклоняется.

К сообщению приложен файл (nam.zip - 2Kb) cкачать
31 май 20, 00:58    [22142924]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?
31 май 20, 03:22    [22142939]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?


Это противоречит определению НАМ:

1. НАМ - это упорядоченный набор строковых замен (некоторые замены могут иметь флаг останова).

2. НАМ начинает работу с единственной входной строки, последовательно выполняя шаги.

3. На очередном шаге НАМ просматривает список замен с самого начала и выполняет первую подходящую замену.
При этом замена в текущей строке выполняется 1 раз для первого подходящего фрагмента строки.

4. НАМ останавливается, если на очередном шаге не найдена подходящая замена
или если выполненная замена имела флаг останова.

5. Результатом работы НАМ является текущая строка в момент прекращения его работы.
31 май 20, 10:28    [22142961]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab,

поэтому когда вас просят разработать НАМ для сложения чисел в двоичной записи,
это означает, что нужно просто указать список замен.
31 май 20, 10:39    [22142963]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
mini.weblab
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?

Давай мы этот вопрос адресуем новому топику который ты сама создашь.
31 май 20, 11:21    [22142967]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111,

правильно ли я понял, что последний более быстрый вариант реализации бинарного умножения
отличается от предыдущего перестановкой замен и добавлением ускорителей, например:
0g0000 -> 00000g
0g00 -> 000g
0g0 -> 00g


P.S.
НАМы и без оптимизаций довольно трудны для понимания,
а после перестановок и вовсе теряют читаемость,
поэтому, проявляя заботу о читателях,
хочется попросить наряду с оптимизированной версией
также публиковать неоптимизированную версию алгоритма.
31 май 20, 13:12    [22143037]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1013
mayton,
нет, спасибо, думаю, не стоит
31 май 20, 14:16    [22143082]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 199
Aleksandr Sharahov,

Да весь выигрыш как раз в ускорителях. При этом если считать именно число шагов по правилам то реальную помощь дает только
0t00 -> 000t.

Остальные хоть и уменьшают число замен, но увеличивают число итераций
31 май 20, 16:21    [22143153]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Беря во внимание сугубую ДОКАЗАТЕЛЬНУЮ теоретичность НАМ, я-бы предложил писать чисто-рафинированные
алгоритмы без оптимизаций. Оптимизации всегда можно предложить потом. Ценой какой-то потери читабельности.

Мне нравится вариант когда мы например "сложение" просто заменяем инкрементом с рекурсивным условием.
Это - в духе функциональщины.
31 май 20, 16:41    [22143163]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Следующий вопрос.

Можем-ли мы реализовать ПОЛИЗ.

Пример:

Input:
sqrt(7 * (3 + 1))


Output
7 3 1 + * sqrt



При этом понимаем что плюс и минус - бинарная функция а квадратный корень - унарная.
31 май 20, 17:00    [22143179]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Еще вопрос.

Можем-ли мы реализовать общий случай генерации перестановок (combinations) для любого числа символов?

Input:
123


Output:
123
132
213
231
312
321
31 май 20, 17:02    [22143181]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 1995
mayton,

это не просто "в духе", все эти папагиглеммы и есть существо функциональщины,
доказывающее, что все, что может быть вычислено, вычислимо иммутабельным образом,
если замену видеть как атомарную операцию.
Алгорифм бежит только вперед.
А то, что обычно алгоритмом называется, представлено списком замен, которые, в обычном понимании, просто "данные".
Попом на этом сидит вся функциональщина, одновременно с декларативными прологами и последователями.
Подставив еще одну замену ты внедряешь еще одну первоклассную функцию, по сути.
Я никогда не влезал в эту тему, а на беглый взгляд вот такой вопрос заинтересовал:
В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.
Есть для такого случая формализьма...
31 май 20, 17:11    [22143186]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
booby

В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.
Есть для такого случая формализьма...

Я на самом деле хотел еще сильнее усугубить вопрос формализма НАМ.

Лет 15 назад мне попала в руки Книга Душкина. И она (честно говоря) надолго отбила у меня желание
изучать ФП и Хаскель в том числе. Книга - изобиловала отсылкой к математике. Ну чтобы понять сравнение
это как полезность Дональда Кнута в изучении С++. Вроде и надо. И в тоже время старина Кнут затягивает
тебя как воронка в очень занудные исследования непонятных сущностей как то машина MIX, ленточные
сортировки, и прочие абстракции которые современному разработчику вобщем не нужны. Их просто негде
применить. А если кто-то ищет другой порог вхождения то он его 100% найдет. И это будет не Кнут.

Слава богу мой хороший наставник Саша Немиш и и коммитер в Хаскель сообщество Виталий Брагилевский
немного освежили во мне желание снова посмотреть на этот язык. Я вобщем не планирую особо на нем кодить.
Нет заказов вообще. Но его изучать полезно чтобы просто понять - а зачем собсно в Scala вводили ту или иную
метафору или зачем например Java нужны streams с искусственными ограничителям.

Так вот. В главе 5.1 Основы комбинаторной логики (КЛ) Душкин приводит комбинаторы тождества (I),
канцелятор (K), коннектор (S), композитор (B), пермутатор (С) и дубликатор (W). Меня это заинтересовало.
К сожелению Душкинские примеры с неподвижной точкой и играми с базисами были для меня непонятны
с практической стороны. Я искал за что зацепиться с практики. Не смог.

И данный топик является просто пред-течей или преамбулой для другого топика который я просто обдумываю.
Обычно такой вопрос у меня вызревает долгими годами. И когда я пишу его текст - он на 80 % уже
у меня в голове готов. Я просто дополняю его линками.

Так вот. Какая связь между НАМ и КЛ. Я посчитал что если момедитировать над Марковскими правилами
то возможно я увижу какую-то мысль или связь которая меня подтолкнет к логике комбинаторов.

Сообщение было отредактировано: 31 май 20, 17:27
31 май 20, 17:28    [22143196]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
booby

Попом на этом сидит вся функциональщина, одновременно с декларативными прологами и последователями.
Подставив еще одну замену ты внедряешь еще одну первоклассную функцию, по сути.

Тема пролога мне была интересна прошлой осенью. Я хотел ее применить для поиска фактов
в дата-аналитике крупного бизнеса. Но не вышло по техническим причинам. Я не смог затащить
в проект зависимость от SWI-Prolog.

И моё достижение - это формальное доказательство на Прологе того что Иисус Христос - сын божий.
Только для этого мне пришлось записать порядка несколько сотен библейских фактов о отцовстве
и наследовании.
31 май 20, 17:34    [22143199]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Еще вопрос.

Можем-ли мы реализовать общий случай генерации перестановок (combinations) для любого числа символов?

Input:
123


Output:
123
132
213
231
312
321


результат должен быть строкой с разделителем?
31 май 20, 17:34    [22143200]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov

результат должен быть строкой с разделителем?

Хм... хороший вопрос.

Если у нас будет автомат-преобразователь следующей перестановки - то это будет успех.

Input:
231 

Output:
312


Или если надо будет ввести искусственно код состояния. Или код рекурсии - то давай введем.

Input:
231(0)

Output:
312(1)
31 май 20, 17:45    [22143205]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
booby

В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.

У меня не возникало желания изменять правила. Но очень хотелось разбить их на непересекающиеся
модули. Причем терминалка должна была бы просто переходить в другой модуль.

Пример.

module 1 {
  rule1 -> repl1
  rule2 |-> :goto module_2
}

module 2 {
  rule1 -> repl3
  rule2 |-> :stop
}


Разумеется это не чистый НАМ. Но это моё определённое улучшение в духе Маркова.

Надеюсь госпожа mini.weblab меня здесь поймет и не будет настаивать на имеративных
языках.
31 май 20, 17:58    [22143214]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 1995
mayton,

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

Изменяемый состав правил - это программа пишет сама себя по мере функционирования,
в целях всякого дип лёрнинга и построения прочих нейросетей.
То есть, кроме накопления состава фактов ( в терминах пролога) происходит докидывание/накопление,
а то и замена, правил вывода.
Вот что-то такое я думал, когда предыдущий пост писал.
31 май 20, 18:22    [22143233]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 1995
booby,

мне кажется, японцы чего такого про пролог измышляли,
когда хавтались за него, как язык будущего искусственного интеллекта.
31 май 20, 18:26    [22143236]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Я тебя понял. Нет о таком я не думал. Очень напоминает eval в транслируемых языках.
И вопрос доказательства останова (к примеру) для нас становится еще более неочевидным.

Хотя я не против эксперимента если ты предложишь своё улучшение. NMA-eval.

Сообщение было отредактировано: 31 май 20, 18:24
31 май 20, 18:26    [22143237]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
booby
booby,

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

У меня был еще один мотиватор. Экспертные системы в роли telegram-чят ботов.

Почему я об этом задумался. Когда я посмотрел их исходники в e-commerce.
Я пришел в ужас. Интеллектом там и не пахнет. Все на if-else. И ребята
которые пишут диалоговых ботов даже слыхом не слыхали про Prolog.

Мне это показлось как минимум - обидным. Конечно я не собирался
писать своего чят бота в телеграм. Но я хотел реализовать некое теч-демо
взяв экспертную систему из 80х (ну какую-нибудь по диагностике неполадок
например автомобиля). Взять - я имею в виду "слямзить" готовую. И просто
интегрировать ее с Телеграм-Ботом и показать.

- Ребята! Вот как надо! Вот как родные!
31 май 20, 18:32    [22143243]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton,

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

И это будет проблемой при генерации перестановок,
т.к. правила зависят от исходного алфавита и, в частности, от его мощности.

А других препятствий для генерации перестановок в алфавитном порядке вроде нет.

Сообщение было отредактировано: 31 май 20, 19:23
31 май 20, 19:24    [22143275]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov, согласен. Мне вот еще не хватало символа конец строки. Типа "$" в регулярках.
31 май 20, 19:29    [22143276]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Aleksandr Sharahov, согласен. Мне вот еще не хватало символа конец строки. Типа "$" в регулярках.


неудобно, да, но его всегда можно самому присобачить - это все-таки решаемо
31 май 20, 19:32    [22143277]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
По поводу Пролога. Ну вот фрагмент.

+
% Eden chronicles.

parent(god, lucifer).
parent(god, adam).
parent(god, eve).
wife(eve,adam).

parent(adam, kain).
parent(eve, kain).
parent(adam, abel).
parent(adam, sif).

% Sif genealogy

parent(sif, enos).
parent(enos, kainan).
parent(kainan,maleleil).
parent(maleleil,iared).
parent(iared,enoh2).     % TODO: Duplicate enoh?
parent(enoh2, mafusail).
parent(mafusail, lameh).
parent(lameh, noah).

.....

predecessor(X,Y) :-
   parent(X,Y).

predecessor(X,Z) :-
   parent(X,Y),
   predecessor(Y,Z).


Там где многоточие - ветхий и новый завет в моём кривом изложении. Генеалогия.

Далее остается спросить у системы

?- predecessor(god, jesus).


И она отвечает true.

Идею я дальше не развивал. Просто мало фактов. И они - плоские. Вот если бы взять генеалогию Толкиена
или Игр Престолов то там наверное можно было описать троюродных дядей или шуринов или свояков.

Но уже было не интересно.

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

Например
- Является ли Джон Сноу потомком рода Таргариенов?
31 май 20, 19:43    [22143282]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Aleksandr Sharahov
mayton
Aleksandr Sharahov, согласен. Мне вот еще не хватало символа конец строки. Типа "$" в регулярках.


неудобно, да, но его всегда можно самому присобачить - это все-таки решаемо


А какого еще инструментация нам не хватает чтобы присобачить к НАМ возможности
генератора перестановок и конвертера инфиксной записи в ПОЛИЗ ?

Мне вот кажется не хватает представления исходной строки как дерева. Если-бы
мы могли скобочками так группировать

(1(2(3))


И обращяться к узлам этого дерева.
31 май 20, 19:47    [22143283]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 1995
Aleksandr Sharahov

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

То, что Марков по этому поводу говорит, можно примерно в таком духе изложить:

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

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

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

В общем случае, для не нормальных, алгорифмов, можно и смволы-комбинаторы в правилах придумывать,
каждый из которых, вообще говоря, должен уметь быть представимым в виде нормального алгорифма.
31 май 20, 20:10    [22143291]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
Все форумы / Программирование Ответить