Metacomputation: Metasystem transitions plus supercompilation

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

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

1. Объяснена нотация для графов конфигураций: (x → s.1 x)(s.1 → ‘a’) (y‘b’ ← y) – она используется во многих других работах, но у меня часто от нее оставалось ощущение недопонимания. Здесь еще мешает пониманию стремление Турчина написать (x → s.1 x), а не (x → s.1 x1) - то есть повторно использовать ту же самую переменную, экономя на именах.
2. Стало понятно, что же такое walk grammar и почему они лучше получаются для плоского языка (в общем случае walk grammar является context-free, а для плоского языка она regular).

Теперь с новыми силами можно перечитать курантовский отчет.