4 ms·

We'd need to be talking about a concrete example to say with much specificity, but a node is basically a "thing" and an edge is a binary relationship between tw

We'd need to be talking about a concrete example to say with much specificity, but a node is basically a "thing" and an edge is a binary relationship between two things. A thing may have relationships with itself. The precise "information" associated to them could be "anything", but would be proscribed by the computation and/or representation being disccussed and the graph in question.

catnaroek 10y ago
How disappointing. I was expecting something more concrete, like “every node is a sequence point and every edge is a possible transition” or “every node is a point at which a nondeterministic event occurs and every edge corresponds to a causal relation between events”. But if you just say “a computation is a graph” and give no further details, then there's no actual benefit to modeling computations as graphs. I'm even more annoyed by your use of the word “isomorphic”, which, FYI, doesn't mean “vaguely similar in some way I can't articulate”. It only makes sense two speak of two mathematical objects being “isomorphic” when they belong in the same category. What category do you have in mind, that includes both computations and graphs as objects, and what are the morphisms between them?
- jsprogrammer 10y ago
  Disappointing? You are the one coming to me expecting an example-oracle that produces them on demand. E.g. Computation / representation: 2 + 2 Graph [+] / \ [2] [2] There is a way to produce the graph from the computation / representation and vice versa. There is a way to do that for every possible computation / representation and every possible graph (though, not necessarily with every pair). This could be described as a compiler or compiler-like. There are many interesting things to do with them, but in this example all that is needed to consider is the construction of an Abstract Syntax Tree from a string and an in-order tree walker that emits the contents of the nodes to an output string.
  - catnaroek 10y ago
    (0) You said “I don't mean directed graphs, only vertices and edges.” But a syntax tree, viewed as a graph, is very much a directed one - the relation between a parent node and its children is asymmetric. (1) A syntax tree isn't the same thing as a computation. Of course, you can produce computations by interpreting syntax trees, but: (a) It's perfectly possible for two distinct syntax trees to produce the same computation. [Say, by renaming all variables.] (b) It's also perfectly possible that interpreting the same syntax tree twice will produce completely different computations! [Say, if your language isn't pure.] Unsurprisingly, a syntax tree is a representation of syntax, not computation. (2) Yes, I'm disappointed, because I expected your observation that “every computation (...) is isomorphic[sic] to some graph” to provide more insight than it turned out to. Edit: Turned paraphrasing into literal quote.
    - jsprogrammer 10y ago
      Placing [sic] into a paraphrasing is just misleading. 0) You asked, "What information is associated to [nodes and edges]?". In this example, one piece of information is the direction of an edge. 1) I don't think I claimed they were the same. In fact, I am claiming that one can be represented by the other and vice versa. a) yes, that is part of the reason I conject that each graph may be associated with an "infinite number" of computations and/or representations b) also a reason -- there are perhaps an infinite number of languages, interpreters, compilers, etc. (some of which may produce the same result) for a given graph. 2) It was only an observation that the comment I responded to claimed only a subset of the truth. Anything done on a computer can be considered as a graph.

catnaroek 10y ago

How disappointing. I was expecting something more concrete, like “every node is a sequence point and every edge is a possible transition” or “every node is a point at which a nondeterministic event occurs and every edge corresponds to a causal relation between events”. But if you just say “a computation is a graph” and give no further details, then there's no actual benefit to modeling computations as graphs. I'm even more annoyed by your use of the word “isomorphic”, which, FYI, doesn't mean “vaguely similar in some way I can't articulate”. It only makes sense two speak of two mathematical objects being “isomorphic” when they belong in the same category. What category do you have in mind, that includes both computations and graphs as objects, and what are the morphisms between them?

jsprogrammer 10y ago
Disappointing? You are the one coming to me expecting an example-oracle that produces them on demand. E.g. Computation / representation: 2 + 2 Graph [+] / \ [2] [2] There is a way to produce the graph from the computation / representation and vice versa. There is a way to do that for every possible computation / representation and every possible graph (though, not necessarily with every pair). This could be described as a compiler or compiler-like. There are many interesting things to do with them, but in this example all that is needed to consider is the construction of an Abstract Syntax Tree from a string and an in-order tree walker that emits the contents of the nodes to an output string.
- catnaroek 10y ago
  (0) You said “I don't mean directed graphs, only vertices and edges.” But a syntax tree, viewed as a graph, is very much a directed one - the relation between a parent node and its children is asymmetric. (1) A syntax tree isn't the same thing as a computation. Of course, you can produce computations by interpreting syntax trees, but: (a) It's perfectly possible for two distinct syntax trees to produce the same computation. [Say, by renaming all variables.] (b) It's also perfectly possible that interpreting the same syntax tree twice will produce completely different computations! [Say, if your language isn't pure.] Unsurprisingly, a syntax tree is a representation of syntax, not computation. (2) Yes, I'm disappointed, because I expected your observation that “every computation (...) is isomorphic[sic] to some graph” to provide more insight than it turned out to. Edit: Turned paraphrasing into literal quote.
  - jsprogrammer 10y ago
    Placing [sic] into a paraphrasing is just misleading. 0) You asked, "What information is associated to [nodes and edges]?". In this example, one piece of information is the direction of an edge. 1) I don't think I claimed they were the same. In fact, I am claiming that one can be represented by the other and vice versa. a) yes, that is part of the reason I conject that each graph may be associated with an "infinite number" of computations and/or representations b) also a reason -- there are perhaps an infinite number of languages, interpreters, compilers, etc. (some of which may produce the same result) for a given graph. 2) It was only an observation that the comment I responded to claimed only a subset of the truth. Anything done on a computer can be considered as a graph.