Pruning moves

This is part of the Tutorial:Graphic lambda calculus.

Here are described the moves related to the univalent termination gate. There are local and global pruning moves.

  • LOCAL PRUNING.  The local moves which eliminate “dead edges” or “dead nodes” are the following:



These moves go in one direction, compared with the graphic beta move, which is allowed in both directions. In  arXiv:1207.0332v1 [cs.LO], paragraph 2.6, where this moves were introduced, they are allowed in both directions. However, I intend to modify this and to introduce generation moves instead, like CREA and GARB, as explained in Ancient Turing machines posts here and here.

  • GLOBAL PRUNING. Like  the GLOBAL FAN-OUT move, this is a global move. A local version of it, in the spirit of the LOCAL FAN-OUT move, may be introduced.  For any graph A in GRAPH, if A  is connected ONLY to a termination gate, then we may remove it.



Return to Tutorial:Graphic lambda calculus

22 thoughts on “Pruning moves”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s