Anton Salikhmetov

Early this year, I made a post on LtU about the experimental "abstract" algorithm in MLC. Soon after that, Gabriel Scherer suggested doing exhaustive search through all possible inputs up to a particular size. Recently, I decided to conduct such an experiment. Here are

Some results

I managed to collect some results [1]. First of all, I had to pick a particular definition for "size" of a λ-term, because there are many. I chose the one that is used in A220894 [2]:

size(x) = 0;
size(λx.M) = 1 + size(M);
size(M N) = 1 + size(M) + size(N).

For sizes from 1 to 9, inclusively, there exist 5663121 closed λ-terms. I tested all of them against both "abstract" [3] and "optimal" [4] algorithms in MLC, with up to 250 interactions per term. The process took almost a day of CPU time. Then, I automatically compared them [5] using a simple awk(1) script (also available in [1]), looking for terms for which normal form or number of β-reductions using "abstract" would deviate from "optimal".

No such terms have been found this way. Surprisingly, there have been identified apparent Lambdascope counterexamples instead, the shortest of which is λx.(λy.y y) (λy.x (λz.y)) resulting in a fan that reaches the interaction net interface. I plan to look into this in near future.

As for sizes higher than 9, testing quickly becomes unfeasible. For example, there are 69445532 closed terms of sizes from 1 to 10, inclusively, which takes a lot of time and space just to generate and save them. [6] is a 200MB gzip(1)'ed tarball (4GB unpacked) with all these terms split into 52 files with 1335491 terms each. In my current setting, it is unfeasible to test them.

I may come up with optimizations at some point to make it possible to process terms of sizes up to 10, but 11 and higher look completely hopeless to me.

[1] https://gist.github.com/codedot/3b99edd504678e160999f12cf30da420
[2] http://oeis.org/A220894
[3] https://drive.google.com/open?id=1O2aTULUXuLIl3LArehMtwmoQiIGB62-A
[4] https://drive.google.com/open?id=16W_HSmwlRB6EAW5XxwVb4MqvkEZPf9HN
[5] https://drive.google.com/open?id=1ldxxnbzdxZDk5-9VMDzLvS7BouxwbCfH
[6] https://drive.google.com/open?id=1XjEa-N40wSqmSWnesahnxz6SXVUzzBig

Так называемые жесткие комбинаторы принадлежат более узкому классу graph relabeling systems, чем graph rewriting systems, к которым относятся сети взаимодействия в общем случае. По научным меркам, они введены буквально вчера - в нулевых. По их поводу написано полторы статьи, а наивная реализация в современных FPGA/ASIC и для жестких комбинаторов не очень многообещающая, так как агенты одновременно служат и для вычисления и для хранения данных, что слишком затратно для FPGA/ASIC, где суммарный объем памяти регистров всегда на порядок, если не на два, меньше доступной на той же доске встроенной RAM. У последнего неизбежно оказывается бутылочное горлышко.

В определенной перспективе жесткие сети взаимодействия - логичное продолжение развития процессоров. Но на данном этапе этот подход кажется слишком далеким от практики, - возможно, им потребуется еще несколько лет побыть в академических кругах. Впрочем, коммерческие компании типа ARM и сами метят в ту же сторону. К сожалению, пока это только пресс-релизы и провалившиеся проекты, тем не менее, ключевые слова правильные - "clockless computation".

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

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

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

Если пойти этим путем, естественным образом возникает проблема синхронизации. В случае BOINC она решается наличием серверов, проверяющих корректность работы. В случае Bitcoin проверка работы тривиальна и не отнимает у всех нод никакого существенного времени ценой дублирования десятков гигабайт информации на всех нодах. Заметим, что в обоих упомянутых случаях работа заранее выбрана так, что ее можно легко проверить, а также строго выполняется единая последовательность событий.

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

What's your status?

Issue 735 Resolved and Accepted.

Issue 736 Needs an Interpretation and Accepted as Marked by Don Cragun:

Interpretation response
------------------------
The standard is unclear on this issue, and no conformance
distinction can be made between alternative implementations
based on this.  This is being referred to the sponsor.

Rationale:
-------------
The following changes make the grammar and text reflect existing
practice.

Notes to the Editor (not part of this interpretation):
-------------------------------------------------------
On page 2350, lines 74801-74808, change

%start  complete_command
%%
complete_command : list separator
                 | list
                 ;

to:

%start program
%%
program          : linebreak complete_commands linebreak
                 | linebreak
                 ;
complete_commands: complete_commands newline_list complete_command
                 |                                complete_command
                 ;
complete_command : list separator_op
                 | list
                 ;

Cross-volume change to XRAT...

At page 3700 line 126612 section C.2.10 delete:

The start symbol of the grammar (complete_command) represents
either input from the command line or a shell script.  It is
repeatedly applied by the interpreter to its input and represents
a single "chunk" of that input as seen by the interpreter.

Issue 737 Resolved and Accepted.

http://austingroupbugs.net/view.php?id=736

An empty Shell program and a program consisting of two or more commands separated with NEWLINE tokens are valid Shell scripts. However, Shell Grammar Rules only accept exactly one single command which results in a syntax error against zero commands and two or more commands separated with NEWLINE tokens.

Desired Action

On page 2350, lines 74801-74808, change

%start  complete_command
%%
complete_command : list separator
                 | list
                 ;

to

%start script
%%
script           : commands linebreak
                 | /* empty */
                 ;
commands         : commands newline_list complete_command
                 |                       complete_command
                 ;
complete_command : list separator_op
                 | list
                 ;

http://www.cims.nyu.edu/~eve2/predprey.pdf

Prime number selection of cycles in a predator-prey model
Eric Goles, Oliver Schulz, Mario Markus

The fact that some species of cicadas appear every 7, 13, or 17 years and that these periods are prime numbers has been regarded as a coincidence. We found a simple evolutionary predator-prey model that yields prime-periodic preys having cycles predominantly around the observed values. An evolutionary game on a spatial array leads to travelling waves reminiscent of those observed in excitable systems. The model marks an encounter of two seemingly unrelated disciplines: biology and number theory. A restriction to the latter, provides an evolutionary generator of arbitrarily large prime numbers.

Via udod's post and Wikipedia.

In theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the Random access machine.

Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM). The SMM seems to be the most common.

This should definitely help to answer two questions on MathOverflow, regarding Turing-complete primitive blind automata and Universality of blind graph rewriting.

IEEE 1003.1-2008, C.4.3 Exclusion of Utilities:

emacs

The community of emacs editing enthusiasts was adamant that the full emacs editor not be included in the base documents because they were concerned that an attempt to standardize this very powerful environment would encourage vendors to ship versions conforming strictly to the standard, but lacking the extensibility required by the community. The author of the original emacs program also expressed his desire to omit the program. Furthermore, there were a number of historical UNIX systems that did not include emacs, or included it without supporting it, but there were very few that did not include and support vi.

Это музыкой навеяло:

alexo@euromake:/tmp/and$ cat and.c
void *
true_(x, y)
void *x, *y;
{
        return x;
}

void *
false_(x, y)
void *x, *y;
{
        return y;
}

void *
bool_[] = {false_, true_};

void *
and(x, y)
void *(*x)(), *y;
{
        return x(y, x);
}

main(argc, argv)
char *argv[];
{
        int x = argv[1][0] - '0';
        int y = argv[2][0] - '0';

        return (true_ == and(bool_[x], bool_[y]));
}
alexo@euromake:/tmp/and$ cat Makefile
all: and
        ./and 0 0; echo $$?
        ./and 0 1; echo $$?
        ./and 1 0; echo $$?
        ./and 1 1; echo $$?

clean:
        -rm -f and
alexo@euromake:/tmp/and$ make
cc     and.c   -o and
./and 0 0; echo $?
0
./and 0 1; echo $?
0
./and 1 0; echo $?
0
./and 1 1; echo $?
1
alexo@euromake:/tmp/and$ 

Только что понял, что именно мне напоминает схема вычисления с четырьмя списками L, A, D, R и алгоритмом сортировки "мусора" aord. Она во многом похожа на механизм транскрипции в биологии (процесс синтеза РНК с использованием ДНК в качестве матрицы).

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

Произведя нехитрый поиск, я немедленно натолкнулся на книгу Maribel Fernandez под названием "Models of Computation: An Introduction to Computability Theory" и теперь жду не дождусь заполучить ее в руки:



http://www.amazon.co.uk/dp/1848824335

P. S. Получил, наконец-то. Оказалось неплохим вводным учебником по CS в его современном виде.