It is known that interaction combinators can implement any interaction net system efficiently. Now, let us define a modification of interaction combinators, which, instead of two types of fan cells, has an infinite number of fan-cells, labelled with unique integers. That system works exactly like the previous: two nodes with identical labels annihilate; two nodes with different labels duplicate. In other words, interaction combinators are a subset of that system, with only 2 possible ids.

How can you compile that new system to the former, without losing efficiency?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.