This seems very interesting - its like a graph based computation language! OP - it seems to me that executions of programs in this context are kind of orientations through the graph by drawing arrows all in one direction or the other..

So can this run programs in both directions? For example, orienting the NAND gate from "X NAND Y" to X and Y (i.e providing X NAND Y as say, TRUE) would generate the X and Y that could lead to the input? If we added that functionality to the basic gates (i.e allow running OR in reverse and have it return {(X=1,Y=0), (X=0,Y=1)} when given input (X OR Y=1)), and accumulated the possibilities at each step as a tree. Of course, it could take very long to run.

Actually, maybe it would even be possible simply fill in certain nodes and propagate out to all connected nodes, keeping track of possible inputs. So it can complete the whole graph (or connected component to be precise) with possible values given any random nodes filled out. So it can give you all possible executions subject to restrictions on any nodes values. That would be awesome!

OP - Does that make any sense? If it does, I may try to implement it and see what kinds of cool things we can do with it.