В этой статье изложен алгоритм
Описание алгоритма
Описание алгоритма выполнено в самодельном математизированном формализме по принципу «сверху вниз», то есть сначала дается окончательная, абстрактная запись, а после этого идет разбор алгоритма на запчасти в порядке осуществления вызовов и даются комментарии. Итак, алгоритм “в сборе” представляет собой рекурсивную функцию следующего вида:
tn+1 = composition[abstraction[deduction[tn]]]; t0 = s; tn, s ∈ S; n ∈ N
Вычисление этой функции есть
composition[], abstraction[], deduction[]; имеются так же: затравочная переменная s ∈ S, множество строк специального вида S и номер шага n ∈ N. Далее рассмотрим подробно каждую запчасть. Начнем с множества S и его элементов.
Для того чтобы задать множество S необходимо определить синтаксис в котором будут записываться элементы этого множества. Элементы множества S будем называть строками. Любая строка из S состоит из иерархии скобок “(“, ”)”, а внутри скобок записываются произвольные символьные идентификаторы. Для того чтобы избежать употребления термина “идентификатор”, так как он может потребоваться для других целей, символьные идентификаторы внутри скобок дальше будут называться “мнемоники”. Каждая мнемоника записывается символами латинского алфавита “A — z”. Мнемоники внутри скобок могут разделяться запятой “,”. Если длина мнемоник фиксирована, что оговаривается отдельно, разделитель не ставится. Мнемоники записываются только внутри скобок. В строке могут быть вложенные скобки. Иерархия скобок в строке произвольна, но на каждую открывающую скобку должна быть закрывающая. В этой статье для записи мнемоник я буду использовать только маленькие буквы латинского алфавита, а длина мнемоник будет фиксированной, одна буква соответствует одной мнемонике, символ разделитель не ставлю. Примеры строк:
() ≡ ∅ — пустая строка.
(a) — строка содержащая одну мнемонику “a”.
(aa) — строка содержащая два экземпляра мнемоники “a”.
(ab) — строка содержащая две мнемоники “a” и “b”.
((a)(a)) — строка содержит два экземпляра мнемоники “a” и вложенные уровни скобок.
Вложенные скобки, вместе с их содержимым, а так же отдельные мнемоники иногда буду называть “компоненты строки”, в тех случаях где требуется соответствующее обобщение. Например, строка ((a)ab) содержит четыре компонента, среди них: два компонента “a”, один компонент “(a)” и один компонент “b”.
Записи строк которые совпадают с точностью до перестановки компонентов внутри строки считаются тождественными. Примеры тождественных строк:
(ab) ≡ (ba).
((a)(b)) ≡ ((b)(a)).
(abc) ≡ (bac) ≡ (cba) ≡ (acb) ≡ (bca) ≡ (cab).
((a)(ab)) ≡ ((a)(ba)) ≡ ((ab)(a)) ≡ ((ba)(a)).
Строки могут содержать сколько угодно одинаковых, повторяющихся компонентов, и в этом случае допустима сокращенная запись при помощи индекса повторения, который ставится перед компонентом слева, без разделителя. Примеры:
(aa) ≡ (2a).
(aabb) ≡ (2a2b).
((a)(a)) ≡ (2(a)).
((aa)(aa)) ≡ (2(2a)).
(aa(bb)(bb)(ccc)(ccc)(ccc)) ≡ (2a2(2b)3(3c)).
В тех случаях, когда строка содержит пустые компоненты, например, (a()), (a()()(b)) имеют место тождества: (a()) ≡ (a), (a()()(b)) ≡ (a(b)), то есть пустые компоненты выбрасываются.
Определение. Множество S состоит из всех возможных строк которые удовлетворяют указанным выше синтаксическим критериям, включая пустую строку.
Операторы дедукции, абстракции и композиции определены на множестве S. Аргументы операторов указываются в квадратных скобках [], поскольку круглые скобки зарезервированы для синтаксиса строк. Термин “оператор” является синонимом термина “функция”.
Оператор дедукции. Определение. ∀s ∈ S, deductionk[s] ∈ S, k ∈ N, k > 1, deduction[s] ≝ deduction2[s]. В качестве аргумента принимает строку s из S. В результате возвращает строку из S. Действие. Оператор k раз дублирует каждый компонент строки и всю строку целиком. Результирующая конструкция обрамляется общими наружными скобками. Дублирование начинается с самых глубоких, по уровню вложенности, компонент. Вся строка целиком дублируется в последнюю очередь. Для ближайших практических целей достаточно чтобы k=2, поэтому я определил специальный случай deduction[s] ≝ deduction2[s]. Употребление deduction[] подразумевает что k=2, то есть в результате действия оператора deduction[s] все компоненты строки s удваиваются. Примеры:
deduction[(a)] = ((aa)(aa)).
deduction[(aa)] = ((aaaa)(aaaa))
deduction[(ab)] = ((aabb)(aabb)).
deduction[(a(b))] = ((aa(bb)(bb))(aa(bb)(bb))).
deduction[((a)(b))] = (((aa)(aa)(bb)(bb))((aa)(aa)(bb)(bb))).
deduction[((a)(b(cc)))] = (((aa)(aa)(bb(cccc)(cccc))(bb(cccc)(cccc)))((aa)(aa)(bb(cccc)(cccc))(bb(cccc)(cccc)))).
Оператор абстракции. Определение. ∀s ∈ S, abstraction[s] ⊂ S. В качестве аргумента принимает строку s из S. В результате возвращает множество строк. Принцип действия. Из исходной строки оператор абстракции создает множество строк при помощи специальной операции — вынесение за скобки одинаковых компонент. Операция вынесения за скобки применяется только для вложенных скобок которые находятся на одинаковом уровне вложенности. Общий принцип вынесения за скобки. Если в каком-либо сочетании расположенных на одном уровне скобок, внутри скобок имеются одинаковые компоненты, тогда любой набор из одинаковых компонентов можно вынести за скобки, а компоненты которые остались нетронутыми должны объединиться под одни общие скобки того же уровня. Рассмотрим пример. Строка ((ab)(ac)). В этой строке на одном уровне находятся две подстроки: (ab) и (ac), внутри которых есть одинаковая мнемоника "a", эту мнемонику можно вынести за скобки и в результате получится (a(bc)). Как видно, оставшиеся мнемоники "b" и "c" объединились в общих скобках. Рассмотрим менее очевидный пример. Строка ((aa)(aa)) содержит подстроки (aa) и (aa), в данном случае возможны два различных варианта вынесения за скобки. В первом варианте из каждой подстроки можно вынести за скобки только одну мнемонику "a", а во втором варианте можно вынести группу мнемоник "aa". Рассмотрим оба варианта подробнее.
Первый вариант, демонстрация по шагам:
- Шаг первый, выбираем(красным) что выносить ((aa)(aa)).
- Шаг второй, выносим выбранное (a(...a)(...a)).
- Шаг третий, объединяем остатки в общих скобках (a(...a...a)).
- Результат (a(aa)).
Второй вариант, по шагам:
- Шаг первый, выбираем что выносить ((aa)(aa)).
- Шаг второй, выносим выбранное (aa(...)(...)).
- Шаг третий, объединяем остатки в общих скобках (aa(...)).
- Шаг четвертый, выбрасываем пустые компоненты (aa).
- Результат (aa).
Усложним пример. Пускай дана строка ((aa)(aab)(aab)), в ней имеются три подстроки расположенные на одном уровне: (aa), (aab), (aab), во всех трех есть одинаковый контент. Правило вынесения за скобки не обязывает нас осуществлять операцию сразу для всех трех подстрок. Для операции вынесения можно выбрать любую группу подстрок.
В данном случае есть три нетождественных варианта группировки подстрок:
- (aa), (aab).
- (aab), (aab).
- (aa), (aab), (aab).
Осуществим все возможные вынесения для каждого из вариантов группировки, пошагово.
Группировка (aa), (aab). Строка ((aa)(aab)(aab)).
Первый вариант:
- Выбираем контент ( (aa)(aab) (aab)).
- Выносим ( a(...a)(...ab) (aab)).
- Объединяем ( a(...a...ab) (aab)).
- Результат №1 (a(aab)(aab)).
Второй вариант:
- Выбираем контент ( (aa)(aab) (aab)).
- Выносим ( aa(...)(...b) (aab)).
- Объединяем ( aa(...b) (aab)).
- Результат №2 (a(b)(aab)).
Группировка (aab), (aab). Строка ((aa)(aab)(aab)).
Первый вариант:
- Выбираем контент ((aa) (aab)(aab) ).
- Выносим ((aa) a(...ab)(...ab) ).
- Объединяем ((aa) a(...ab...ab) ).
- Результат №3 (a(aa)(aabb)).
Второй вариант:
- Выбираем контент ((aa) (aab)(aab) ).
- Выносим ((aa) aa(...b)(...b) ).
- Объединяем ((aa) aa(...b...b) ).
- Результат №4 (aa(aa)(bb)).
Третий вариант:
- Выбираем контент ((aa) (aab)(aab) ).
- Выносим ((aa) ab(...a)(...a) ).
- Объединяем ((aa) ab(...a...a) ).
- Результат №5 (ab(aa)(aa)).
Четвертый вариант:
- Выбираем контент ((aa) (aab)(aab) ).
- Выносим ((aa) b(...aa)(...aa) ).
- Объединяем ((aa) b(...aa...aa) ).
- Результат №6 (b(aa)(aaaa)).
Пятый вариант:
- Выбираем контент ((aa) (aab)(aab) ).
- Выносим ((aa) aab(...)(...) ).
- Объединяем ((aa) aab(...) ).
- Результат №7 (aab(aa)).
Группировка (aa), (aab), (aab). Строка ((aa)(aab)(aab)).
Первый вариант:
- Выбираем контент ((aa)(aab)(aab)).
- Выносим (a(...a)(...ab)(...ab)).
- Объединяем (a(...a...ab...ab)).
- Результат №8 (a(aaabb)).
Второй вариант:
- Выбираем контент ((aa)(aab)(aab)).
- Выносим (aa(...)(...b)(...b)).
- Объединяем (aa(...b...b)).
- Результат №9 (aa(bb)).
Действие оператора абстракции. Как видно из примера, для исходной строки ((aa)(aab)(aab)) существует девять различных вариантов вынести что-то за скобки и этим вариантам соответствуют девять результирующих строк. Так действует оператор абстракции, — перебирает все возможные варианты вынесения за скобки и строит соответствующее множество результирующих строк. Причем оператор абстракции ищет варианты вынесения не только в исходной строке, но, в том числе и во всех полученных результирующих строках. Иными словами оператор абстракции рекурсивно применяется к своим результатам, и так до тех пор пока не будут исчерпаны все возможные варианты. По очевидным причинам для любой конечной строки количество возможных вариантов вынесения тоже конечно.
Вернемся к предыдущему примеру. В рассмотренном примере я выписал не все возможные варианты, а лишь девять штук первого уровня. Чтобы проиллюстрировать полное действие оператора абстракции необходимо построить так же все варианты вынесения за скобки для каждого из девяти ранее полученных результатов. Выпишем все варианты, но уже в более сжатом виде.
Результат №1 (a(aab)(aab)):
1.1. (a(aab)(aab)) => (aa(aabb)).
1.2. (a(aab)(aab)) => (aaa(bb)).
1.3. (a(aab)(aab)) => (aab(aa)). *№7
1.4. (a(aab)(aab)) => (aaab).
1.5. (a(aab)(aab)) => (ab(aaaa)).
Результат №2 (a(b)(aab)):
2.1. (a(b)(aab)) => (ab(aa)).
Результат №3 (a(aa)(aabb)):
3.1. (a(aa)(aabb)) => (aa(aabb)). *№1.1
3.2. (a(aa)(aabb)) => (aaa(bb)). *№1.2
Результат №4 (aa(aa)(bb)).
Результат №5 (ab(aa)(aa)):
5.1. (ab(aa)(aa)) => (aab(aa)). *№7, *№1.3
5.2. (ab(aa)(aa)) => (aaab). *№1.4
Результат №6 (b(aa)(aaaa)):
6.1. (b(aa)(aaaa)) => (ab(aaaa)). *№1.5
6.2. (b(aa)(aaaa)) => (aab(aa)). *№7, *№1.3, *№5.1
Результат №7 (aab(aa)).
Результат №8 (a(aaabb)).
Результат №9 (aa(bb)).
Звездочкой отмечены варианты которые повторяются. В результат абстракции включаются только уникальные варианты. В разобранном примере есть четырнадцать уникальных результирующих строк. Итого:
abstraction[((aa)(aab)(aab))] =
{
(a(aab)(aab)), (aa(aabb)), (aaa(bb)), (aaab), (a(b)(aab)), (ab(aa)), (a(aa)(aabb)), (aa(aa)(bb)), (ab(aa)(aa)), (b(aa)(aaaa)), (ab(aaaa)), (aab(aa)), (a(aaabb)), (aa(bb))
}
Для большей ясности рассмотрим еще пару примеров.
Строка ((a(b))(a(b))). Варианты вынесения за скобки. Первая итерация:
((a(b))(a(b))) => (a((b)(b))), результат №1.
((a(b))(a(b))) => ((b)(aa)), результат №2.
((a(b))(a(b))) => (a(b)), результат №3.
В первом результате можно совершить еще одно вынесение. Вторая итерация:
(a((b)(b))) => (a(b)), результат №1.2 совпадает с результатом №3.
Итого: abstraction[((a(b))(a(b)))] = {(a((b)(b))), ((b)(aa)), (a(b))}
1. ( (aa(bb)(bb)) (aa(bb)(bb)) ) => ( (aab(b)) (aa(bb)(bb)) ).
1.1. ( (aab(b))(aa(bb)(bb)) ) => ( a(aab(b)(bb)(bb)) ).
1.1.1. ( a(aab(b)(bb)(bb)) ) => ( a(aabb(b)(bb)) ).
1.1.1.1. ( a(aabb(b)(bb)) ) => ( a(aabbb(b)) ).
1.1.2. ( a(aab(b)(bb)(bb)) ) => ( a(aabb(bb)) ).
1.1.3. ( a(aab(b)(bb)(bb)) ) => ( a(aabb(b)(bb)) ).
1.1.3.1. ( a(aabb(b)(bb)) ) => ( a(aabbb(b)) ).
1.1.4. ( a(aab(b)(bb)(bb)) ) => ( a(aabbb(b)) ).
1.2. ( (aab(b))(aa(bb)(bb)) ) => ( aa(b(b)(bb)(bb)) ).
1.2.1. ( aa(b(b)(bb)(bb)) ) => ( aa(bb(b)(bb)) ).
1.2.1.1. ( aa(bb(b)(bb)) ) => ( aa(bbb(b)) ).
1.2.2. ( aa(b(b)(bb)(bb)) ) => ( aa(bb(bb)) ).
1.2.3. ( aa(b(b)(bb)(bb)) ) => ( aa(bb(b)(bb)) ).
1.2.3.1. ( aa(bb(b)(bb)) ) => ( aa(bbb(b)) ).
1.2.4. ( aa(b(b)(bb)(bb)) ) => ( aa(bbb(b)) ).
1.3. ( (aab(b)) (aa(bb)(bb)) ) => ( (aab(b)) (aab(bb)) ).
1.3.1. ( (aab(b)) (aab(bb)) ) => ( a(aabb(b)(bb)) ).
1.3.1.1. ( a(aabb(b)(bb)) ) => ( a(aabbb(b)) ).
1.3.2. ( (aab(b)) (aab(bb)) ) => ( aa(bb(b)(bb)) ).
1.3.2.1. ( aa(bb(b)(bb)) ) => ( aa(bbb(b)) ).
1.3.3. ( (aab(b)) (aab(bb)) ) => ( aab((b)(bb)) ).
1.3.3.1. ( aab((b)(bb)) ) => ( aab(b(b)) ).
1.3.4. ( (aab(b)) (aab(bb)) ) => ( ab(aa(b)(bb)) ).
1.3.4.1. ( ab(aa(b)(bb)) ) => ( ab(aab(b)) ).
1.3.5. ( (aab(b)) (aab(bb)) ) => ( b(aaaa(b)(bb)) ).
1.3.5.1. ( b(aaaa(b)(bb)) ) => ( b(aaaab(b)) ).
1.4. ( (aab(b)) (aa(bb)(bb)) ) => ( (aab(b)) (aabb) ).
1.4.1. ( (aab(b)) (aabb) ) => ( a(aabbb(b)) ).
1.4.2. ( (aab(b)) (aabb) ) => ( aa(bbb(b)) ).
1.4.3. ( (aab(b)) (aabb) ) => ( aab(b(b)) ).
1.4.4. ( (aab(b)) (aabb) ) => ( ab(aab(b)) ).
1.4.5. ( (aab(b)) (aabb) ) => ( b(aaaab(b)) ).
2. ( (aa(bb)(bb)) (aa(bb)(bb)) ) => ( (aabb) (aa(bb)(bb)) ).
2.1. ( (aabb)(aa(bb)(bb)) ) => ( (aabb)(aab(bb)) ).
2.1.1. ( (aabb)(aab(bb)) ) => ( a(aabbb(bb)) ).
2.1.2. ( (aabb)(aab(bb)) ) => ( aa(bbb(bb)) ).
2.1.3. ( (aabb)(aab(bb)) ) => ( aab(b(bb)) ).
2.1.4. ( (aabb)(aab(bb)) ) => ( ab(aab(bb)) ).
2.1.5. ( (aabb)(aab(bb)) ) => ( b(aaaab(bb)) ).
2.2. ( (aabb)(aa(bb)(bb)) ) => ( (aabb)(aabb) ).
2.2.1. ( (aabb)(aabb) ) => ( a(aabbbb) ).
2.2.2. ( (aabb)(aabb) ) => ( aa(bbbb) ).
2.2.3. ( (aabb)(aabb) ) => ( aab(bb) ).
2.2.4. ( (aabb)(aabb) ) => ( abb(aa) ).
2.2.5. ( (aabb)(aabb) ) => ( aabb ).
2.2.6. ( (aabb)(aabb) ) => ( ab(aabb) ).
2.2.7. ( (aabb)(aabb) ) => ( b(aaaabb) ).
2.2.8. ( (aabb)(aabb) ) => ( bb(aaaa) ).
2.3. ( (aabb)(aa(bb)(bb)) ) => ( a(aabb(bb)(bb)) ).
2.3.1. ( a(aabb(bb)(bb)) ) => ( a(aabbb(bb)) ).
2.3.2. ( a(aabb(bb)(bb)) ) => ( a(aabbbb) ).
2.4. ( (aabb)(aa(bb)(bb)) ) => ( aa(bb(bb)(bb)) ).
2.4.1. ( aa(bb(bb)(bb)) ) => ( aa(bbb(bb)) ).
2.4.2. ( aa(bb(bb)(bb)) ) => ( aa(bbbb) ).
3. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( a(aa(bb)(bb)(bb)(bb)) ).
3.1. ( a(aa(bb)(bb)(bb)(bb)) ) => ( a(aab(bb)(bb)(bb)) ).
3.1.1. ( a(aab(bb)(bb)(bb)) ) => ( a(aabb(bb)(bb)) ).
3.1.1.1. ( a(aabb(bb)(bb)) ) => ( a(aabbb(bb)) ).
3.1.1.2. ( a(aabb(bb)(bb)) ) => ( a(aabbbb) ).
3.1.2. ( a(aab(bb)(bb)(bb)) ) => ( a(aabb(bbb)) ).
3.1.3. ( a(aab(bb)(bb)(bb)) ) => ( a(aabbb(bb)) ).
3.1.4. ( a(aab(bb)(bb)(bb)) ) => ( a(aabbb) ).
3.2. ( a(aa(bb)(bb)(bb)(bb)) ) => ( a(aabb(bb)(bb)) ).
3.2.1. ( a(aabb(bb)(bb)) ) => ( a(aabbb(bb)) ).
3.2.2. ( a(aabb(bb)(bb)) ) => ( a(aabbbb) ).
3.3. ( a(aa(bb)(bb)(bb)(bb)) ) => ( a(aab(bbb)(bb)) ).
3.3.1. ( a(aab(bbb)(bb)) ) => ( a(aabb(bbb)) ).
3.3.2. ( a(aab(bbb)(bb)) ) => ( a(aabbb(b)) ).
3.4. ( a(aa(bb)(bb)(bb)(bb)) ) => ( a(aab(bbbb)) ).
3.5. ( a(aa(bb)(bb)(bb)(bb)) ) => ( a(aabb(bb)) ).
3.6. ( a(aa(bb)(bb)(bb)(bb)) ) => ( a(aabb) ).
4. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( aa((bb)(bb)(bb)(bb)) ).
4.1. ( aa((bb)(bb)(bb)(bb)) ) => ( aa(b(bb)(bb)(bb)) ).
4.1.1. ( aa(b(bb)(bb)(bb)) ) => ( aa(bb(bb)(bb)) ).
4.1.1.1. ( aa(bb(bb)(bb)) ) => ( aa(bbb(bb)) ).
4.1.1.2. ( aa(bb(bb)(bb)) ) => ( aa(bbbb) ).
4.1.2. ( aa(b(bb)(bb)(bb)) ) => ( aa(bb(bbb)) ).
4.1.3. ( aa(b(bb)(bb)(bb)) ) => ( aa(bbb(bb)) ).
4.1.4. ( aa(b(bb)(bb)(bb)) ) => ( aa(bbb) ).
4.2. ( aa((bb)(bb)(bb)(bb)) ) => ( aa(bb(bb)(bb)) ).
4.2.1. ( aa(bb(bb)(bb)) ) => ( aa(bbb(bb)) ).
4.2.2. ( aa(bb(bb)(bb)) ) => ( aa(bbbb) ).
4.3. ( aa((bb)(bb)(bb)(bb)) ) => ( aa(b(bbb)(bb)) ).
4.3.1. ( aa(b(bbb)(bb)) ) => ( aa(bb(bbb)) ).
4.3.2. ( aa(b(bbb)(bb)) ) => ( aa(bbb(b)) ).
4.4. ( aa((bb)(bb)(bb)(bb)) ) => ( aa(b(bbbb)) ).
4.5. ( aa((bb)(bb)(bb)(bb)) ) => ( aa(bb(bb)) ).
4.6. ( aa((bb)(bb)(bb)(bb)) ) => ( aa(bb) ).
5. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( (bb)(aaaa(bb)(bb)) ).
5.1. ( (bb)(aaaa(bb)(bb)) ) => ( (bb)(aaaab(bb)) ).
5.1.1. ( (bb)(aaaab(bb)) ) => ( b(aaaab(bb)) ).
5.2. ( (bb)(aaaa(bb)(bb)) ) => ( (bb)(aaaabb) ).
5.2.1. ( (bb)(aaaabb) ) => ( b(aaaabb) ).
5.2.2. ( (bb)(aaaabb) ) => ( bb(aaaa) ).
6. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( (bb)(bb)(aaaa) ).
6.1. ( (bb)(bb)(aaaa) ) => ( b(bb)(aaaa) ).
6.2. ( (bb)(bb)(aaaa) ) => ( bb(aaaa) ).
7. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( a(bb)(aa(bb)(bb)) ).
7.1. ( a(bb)(aa(bb)(bb)) ) => ( a(bb)(aab(bb)) ).
7.1.1. ( a(bb)(aab(bb)) ) => ( ab(aab(bb)) ).
7.2. ( a(bb)(aa(bb)(bb)) ) => ( a(bb)(aabb) ).
7.2.1. ( a(bb)(aabb) ) => ( ab(aabb) ).
7.2.2. ( a(bb)(aabb) ) => ( abb(aa) ).
8. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( aa(bb)((bb)(bb)) ).
8.1. ( aa(bb) ((bb)(bb)) ) => ( aa(bb)(b(bb)) ).
8.1.1. ( aa(bb)(b(bb)) ) => ( aab(b(bb)) ).
8.2. ( aa(bb) ((bb)(bb)) ) => ( aa(bb)(bb) ).
8.2.1. ( aa(bb)(bb) ) => ( aab(bb) ).
8.2.2. ( aa(bb)(bb) ) => ( aabb ).
9. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( a(bb)(bb)(aa) ).
9.1. ( a(aa)(bb)(bb) ) => ( ab(aa)(bb) ).
9.2. ( a(aa)(bb)(bb) ) => ( abb(aa) ).
10. ( (aa(bb)(bb))(aa(bb)(bb)) ) => ( a(bb)(bb) ).
10.1. ( a(bb)(bb) ) => ( ab(bb) ).
10.2. ( a(bb)(bb) ) => ( abb ).
Из представленного выше списка результирующих(справа от стрелки) строк нужно выбрать все уникальные, и это множество уникальных строк будет результатом работы abstraction[((aa(bb)(bb))(aa(bb)(bb)))]. Выписывать уникальные строки не стану, так как это ничего не добавит объяснению. Ниже, при рассмотрении вопроса оптимизации и практического использования алгоритма, я буду ссылаться на этот пример.
Оператор композиции. Определение. ∀U ⊂ S, U ≠ ∅, composition[U] ≠ ∅, composition[U] ∈ S. На вход принимает множество строк, а возвращает одну строку. Действие. Оператор готовит контент для следующей итерации алгоритма. После действия оператора абстракции появляется множество строк, а на стадии композиции происходит отбор и конкатенация строк для следующей итерации алгоритма. Более подробно я рассмотрю этот вопрос в разделах оптимизации и практического использования. В простейшем случае оператор композиции осуществляет простую конкатенацию всех результатов абстракции. Так его и определим. Пример: composition[abstraction[((a(b))(a(b)))]] = composition[{(a((b)(b))), ((b)(aa)), (a(b))}] = ((a((b)(b)))((b)(aa))(a(b))).
Свойства алгоритма
Алгоритм производит строки. Множество всех строк которые образуются в результате итеративной работы алгоритма буду называть “вывод алгоритма” или просто “вывод”. Определение вывода. Ts ≝ {tn|tn+1 = composition[abstraction[deduction[tn]]]; t0 = s; tn, s ∈ S; n ∈ N}. Ts — вывод для затравки s. В тех случаях когда T без параметра, речь идет о выводе безотносительно затравки. Свойство вывода: ∀s, e ∈ S, s ≠ ∅, e ≠ ∅, s ≠ e, Ts ∩ Te = ∅. Это значит, что каждый элемент вывода уникально соответствует затравке. Как следствие, для каждой затравки вывод уникален.
Содержательная интерпретация дедукции и абстракции. Физический смысл оператора дедукции заключается в следующем. Из исходной строки, универсальным способом, оператор дедукции создает принципиально новый в конструктивном отношении объект, с принципиально новыми и более сложными внутренними свойствами. В интуитивном приближении можно сказать, что дедукция добавляет качественно новую информацию. В свою очередь оператор абстракции разбирает новый объект на запчасти и таким образом в конструктивном эквиваленте выражает информацию добавленную на стадии дедукции. Можно заметить, что в результате процедуры вынесения за скобки происходит потеря информации. Причем для данного синтаксиса, вынесение за скобки — это универсальный способ осмысленно потерять информацию в отсутствии каких-либо априорных данных о значении строк. То есть с точки зрения алгоритма все возможные варианты потери информации, которые вычисляются на этапе абстракции, собственно, и являются значением строк. Таким образом, на каждом шаге алгоритм создает новую, уникальную синтаксическую эвристику. И каждая следующая эвристика является принципиально более сложной и более содержательной чем предыдущая. На каждой итерации алгоритма появляется новое знание.
Практическое применение
Алгоритм является “вещью в себе”. Он мыслит, но это
Рассмотрим идеальный случай. Предположим, что в нашем распоряжении имеется неограниченная вычислительная мощность и можно себе позволить вычислять любое количество итераций
- Цифровая модель интерактивной среды смысл активности которой известен.
- Цифровая модель инструмента которым можно воздействовать на среду.
- Кодирующий алгоритм, чтобы кодировать сигналы от среды строками из S.
- Декодирующий алгоритм, который будет каким-то нечетким, но рационально обоснованным образом декодировать ранее неизвестные строки из S и преобразовывать их в сигналы для инструмента.
Имея такие компоненты можно организовать универсальную схему обучения с неизвестной мотивацией, что позволит адаптировать
S NextThought(S prevThought, S ExternalSignal, int exposure = 1)
{
S t = composition[prevThought, ExternalSignal];
for (int i = 0; i < exposure; i++)
t = composition[abstraction[deduction[t]]];
return t;
}
EnvironmentModel e;
S s = encode(e.GetState());
S o = ∅;
while (0)
{
S o = NextThought(o, s);
e.ImpactTool.perform(decode(o));
s = encode(e.GetState());
}
Схема с обратной связью. В начале у Коли нет мыслей. Первая мысль Коли — это закодированное исходное состояние среды. На каждой итерации в мысли Коли заливается внешний сигнал. После чего Коля думает в течение времени экспозиции. Результаты думания декодируются и отправляются в инструмент. В свою очередь, действие инструмента как-то изменяет состояние среды. И все повторяется снова. В течение какого-то времени
Проблема декодирования. Необходимо декодировать мысли Коли с целью синтеза сигнала для инструмента. Трудность состоит в том, что каждая мысль, как я уже отмечал в предыдущем разделе, представляет собой принципиально новую конструкцию. То есть гипотетический исследователь никогда не сможет полностью разобраться в содержании мыслей Коли. Часть контента производимого
1. Фрагменты с неизвестной лексикой.
2. Неизвестный синтаксис.
3. Неизвестная семантика.
4. Грамматически и семантически корректные фрагменты.
Контент всех указанных категорий по способу возникновения произволен. То есть даже в случае грамматически верных фрагментов — это случайность и неизвестно какой смысл вкладывает в них Коля, поскольку его внутренний смысл доступен только ему самому. Априори нет критериев чтобы правильно связать мысли Коли и соответствующие действия инструмента. И в этом вопросе остается полагаться исключительно на самого Колю. Его поведение произвольно и только он сам может осмыслить свою мотивацию по мере того как степень организации его
Проблема ограниченной вычислительной мощности. С точки зрения объема вычислений алгоритм является тяжелым. Наглядно — несколько десятков итераций исчерпают всю вычислительную мощность планеты. Можно надеяться на квантовые устройства и на то что найдется квантовый аналог алгоритма, но пока этого не произошло выход только один: вместо одной колоссально сложной мысли, параллельно думать много маленьких и простых мыслей. Для этого есть несколько технических трюков:
1. На этапе композиции необязательно включать в результат все множество абстракции. Для того чтобы алгоритм сохранил свои принципиальные свойства достаточно выбрать из множества только две независимые результирующие строки. Критерием независимости является ненулевая разница первых цифр в иерархической нумерации результатов абстракции. Обратимся к большому примеру, который выше под спойлером. Все строки занумерованы по принципу a.b.c.d... Пара строк с индексами a1.b1.c1.d1..., a2.b2.c2.d2... называется независимой, если a1 ≠ a2. А это значит, что есть возможность разбить весь результат абстракции на независимые пары и для каждой пары на следующем шаге запустить свою вычислительную ветку. Более того, нет необходимости использовать все результаты абстракции. В минимальном случае можно выбрать только одну пару строк, а все остальные отбросить(безвозвратно потерять) и все принципы
2. Второй трюк основан на том предположении, что чем более глубоко расположены скобки в строке тем менее организованный контент они содержат. Соответственно, контент “всплывающий вверх” в результате вынесения за скобки является более организованным и абстрактным с точки зрения внутренних смыслов Коли, а значит глубокие уровни вложенности можно удалить. Тем самым объем вычислений на следующей итерации экспоненциально сокращается. В интуитивном понимании эта процедура позволяет аппроксимировать только самую абстрактную часть
3. В результате распараллеливания на множество более мелких веток, вычисления будут разрастаться “в ширину”. Эту ширину можно абсолютно ограничить селекцией не только на уровне отдельных вычислительных веток, но и целиком во всем массиве параллельных веток. Это можно сделать через общий пул фиксированного размера откуда каждая ветка будет черпать строки для следующей итерации, и, соответственно, куда будет сбрасывать результаты. А для строк можно абсолютно ограничить допустимый уровень вложенности скобок. Такой комбинированный подход позволит сдерживать и регулировать рост объема вычислений.
Интерпретация и комментарии
Доказательства. Доказательств нет и быть не может. Любая теория
Неконструктивное определение
Дополнительные точки зрения на алгоритм. Алгоритм
1. Конструктивная реализация метафоры.
2. Модель самоорганизации абсолютного хаоса. Модель концептуальной спонтанности.
3. Модель абсолютно независимого, субъективно мотивированного поведения. Модель творчества.
4. Самоорганизующийся язык.
5. Модель конструктивной аппроксимации, для неконструктивной, чисто возможной семантики.
Сознание. Вопрос сознания тоже решается на уровне определения. Сознание — это то что лежит за пределами любых концептуальных ограничений. В свете такого определения, о сознании можно лишь травить более или менее сложные байки, каждая из которых будет отражать какие-то возможности сознания, но ни одна из них не будет правдой. Вместе с тем, байки про сознание имеют различный эвристический потенциал. Из всех баек полезнее те которые сложнее. С точки зрения алгоритмов, сознание — это транс-алгоритмический, бесконечно сложный(или просто — сложный) объект. Байку о сознании можно записать при помощи алгоритма. Она звучит так:
limn→∞[tn+1 = composition[abstraction[deduction[tn]]]]; t0 = s; tn, s ∈ S; n ∈ N
Автор: MabajanMabajanovich