Едва заметным прошел момент, когда в нашем распоряжении оказалось достаточно материала, чтобы более явно показать, что системы слепой перезаписи графов действительно обладают полнотой по Тьюрингу. Как и предполагалось ранее, достаточно элегантным способом является симуляция направленных комбинаторов взаимодействия, которые сами обладают Тьюринг-полнотой (см. статью Lafont "Interaction Combinators" 1997 года). И хотя по общим соображениям этот факт был понятен еще полгода назад (см. "Логические операции без сравнений"), на данный момент доказательство можно построить из нескольких пунктов.
Мы будем опираться на предыдущие описания наших конструкций. Напомним, что первым шагом был выбор представления направленных комбинаторов γ, γ*, δ и δ*, а также двух видов связей между агентами: между двумя главными портами и между дополнительным и главным (см. "Слепые комбинаторы взаимодействия"). Затем мы получили представление для недостающего третьего вида связей, то есть между двумя дополнительными портами (см. "Слепые двунаправленные соединения"). Наконец, мы добились того, чтобы за один цикл работы системы количество используемых ячеек оставалось постоянным (см. "Баланс освобождаемой и выделяемой памяти"). В заключение мы пояснили выбор алгоритмов работы системы (см. "Трюки в синтаксическом сахаре λ-исчисления").
Итак, во-первых, заметим, что участие ε не влияет на ход вычислений. Поэтому мы можем заменить ε и ε* на свободные порты, которые, в свою очередь, симулируем парами ξ и ξ*, не связанными с чем-либо на противоположной стороне.
Во-вторых, дополним списки A, D, L и R неограниченным количеством фиктивных активных пар. (На практике это реализуемо через большое число процессов, в среднем дающих баланс выделяемой и освобождаемой памяти.)
В-третьих, по аналогии с
Тогда в порядке обработки списков, диктуемом балансом освобождаемой и выделямой памяти, то есть за цикл по паре элементов из списков L и R и по одному элементу из списков A и D, машина слепой перезаписи симулирует взаимодействие направленных комбинаторов.
P. S. Как правильно заметил![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
nivanych, полученная нами система имеет прямое отношение к конкатенационным языкам программирования. А именно, о списках A, D, L и R можно думать как о четырех стеках. Как мы видим, симуляция направленных комбинаторов взаимодействия с помощью слепой перезаписи графов в данном случае действительно породила стековую машину, имеющую одну кучу и четыре стека.
Мы будем опираться на предыдущие описания наших конструкций. Напомним, что первым шагом был выбор представления направленных комбинаторов γ, γ*, δ и δ*, а также двух видов связей между агентами: между двумя главными портами и между дополнительным и главным (см. "Слепые комбинаторы взаимодействия"). Затем мы получили представление для недостающего третьего вида связей, то есть между двумя дополнительными портами (см. "Слепые двунаправленные соединения"). Наконец, мы добились того, чтобы за один цикл работы системы количество используемых ячеек оставалось постоянным (см. "Баланс освобождаемой и выделяемой памяти"). В заключение мы пояснили выбор алгоритмов работы системы (см. "Трюки в синтаксическом сахаре λ-исчисления").
Итак, во-первых, заметим, что участие ε не влияет на ход вычислений. Поэтому мы можем заменить ε и ε* на свободные порты, которые, в свою очередь, симулируем парами ξ и ξ*, не связанными с чем-либо на противоположной стороне.
Во-вторых, дополним списки A, D, L и R неограниченным количеством фиктивных активных пар. (На практике это реализуемо через большое число процессов, в среднем дающих баланс выделяемой и освобождаемой памяти.)
В-третьих, по аналогии с
aord построим алгоритм слепого копирования агентов, такой, что для данных α, β из набора {γ, δ} на месте β оказывается тот же тип агента, что и у агента α (пусть данная задача послужит несложным упражнением читателю). Копирование агентов γ* и δ* тривиально. Поясним, что копирование необходимо при дублировании (элемент списка D), для чего требуется преобразовать оба освобождаемых после аннигиляции агента (элемент списка A) неизвестных типов, в общем случае, в неизвестные типы.Тогда в порядке обработки списков, диктуемом балансом освобождаемой и выделямой памяти, то есть за цикл по паре элементов из списков L и R и по одному элементу из списков A и D, машина слепой перезаписи симулирует взаимодействие направленных комбинаторов.
P. S. Как правильно заметил
nivanych, полученная нами система имеет прямое отношение к конкатенационным языкам программирования. А именно, о списках A, D, L и R можно думать как о четырех стеках. Как мы видим, симуляция направленных комбинаторов взаимодействия с помощью слепой перезаписи графов в данном случае действительно породила стековую машину, имеющую одну кучу и четыре стека.
