4 ms·

I don't mean directed graphs, only vertices and edges. I don't think you would need to deal with infinite graphs, as "arbitrarily large" should be able to cove

I don't mean directed graphs, only vertices and edges. I don't think you would need to deal with infinite graphs, as "arbitrarily large" should be able to cover all (finite) possible computations and/or representations. My guess is that every graph may correspond to an infinite number (though, not necessarily every) of possible computations and/or representations, depending on which "correspondence function" is being used to analyze the graph (though there may be additional "correspondences" between those functions and/or their results).

catnaroek 10y ago
At the very least, answer this: What are the nodes and edges in your graph? What information is associated to them?
- jsprogrammer 10y ago
  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.
- grblovrflowerrr 10y ago
  Broadly speaking, in graph reduction the nodes are functions and values and the edges are steps in the computation that can be taken to apply functions to those values. After application that node becomes a new value, etc. until the program is evaluated or terminated. https://en.wikipedia.org/wiki/Graph_reduction https://en.wikipedia.org/wiki/Graph_reduction https://en.wikipedia.org/wiki/Abstract_semantic_graph https://en.wikipedia.org/wiki/Abstract_semantic_graph Generally they're acyclic but some types of ASGs can represent recursive functions as cycles, so they are distinct from trees.
  - catnaroek 10y ago
    Thanks for your actually useful answer.
    - jsprogrammer 10y ago
      What did you not find useful about my numerous answers? Basically, everything is in some way equivalent to some graph. Since anything is an example, it's difficult to say much without using an example, which then necessarily constrains the discussion. It would be more useful if you presented an example computation or representation, then I could show you how to make and reverse an equivalent graph. (Which then might show you what information might be associated with nodes and edges.)
    - grblovrflowerrr 10y ago
      I don't think there's any reason to be judgy about the other commenter. I understand you wanted a rigorous definition but there are better ways to ask for it than making unilateral demands and using negative terms like "disappointing" and "annoying". You may be well versed in these subjects but it is possible to be technically correct and gracious at the same time. I think you're capable of doing so and you would probably find more fruitful discussions by taking that path.

catnaroek 10y ago

At the very least, answer this: What are the nodes and edges in your graph? What information is associated to them?

jsprogrammer 10y ago
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.
grblovrflowerrr 10y ago
Broadly speaking, in graph reduction the nodes are functions and values and the edges are steps in the computation that can be taken to apply functions to those values. After application that node becomes a new value, etc. until the program is evaluated or terminated. https://en.wikipedia.org/wiki/Graph_reduction https://en.wikipedia.org/wiki/Graph_reduction https://en.wikipedia.org/wiki/Abstract_semantic_graph https://en.wikipedia.org/wiki/Abstract_semantic_graph Generally they're acyclic but some types of ASGs can represent recursive functions as cycles, so they are distinct from trees.
- catnaroek 10y ago
  Thanks for your actually useful answer.
  - jsprogrammer 10y ago
    What did you not find useful about my numerous answers? Basically, everything is in some way equivalent to some graph. Since anything is an example, it's difficult to say much without using an example, which then necessarily constrains the discussion. It would be more useful if you presented an example computation or representation, then I could show you how to make and reverse an equivalent graph. (Which then might show you what information might be associated with nodes and edges.)
  - grblovrflowerrr 10y ago
    I don't think there's any reason to be judgy about the other commenter. I understand you wanted a rigorous definition but there are better ways to ask for it than making unilateral demands and using negative terms like "disappointing" and "annoying". You may be well versed in these subjects but it is possible to be technically correct and gracious at the same time. I think you're capable of doing so and you would probably find more fruitful discussions by taking that path.