5 ms·

Every computation and/or representation is isomorphic to some (hypothetical) graph.

catnaroek 10y ago
Could you clarify: What are the nodes and edges? May the graph contain cycles? May the graph be infinite? If the graph is infinite, do we need a distinguished initial node? Do non-isomorphic graphs always correspond to different computations, or do you have a coarser notion of equivalence (say, graph homeomorphism)? I've read papers where the space of possible computations for a given (typically, toy, even loop-free) nondeterministic concurrent program is represented as a directed topological space (see “directed algebraic topology” for more information), but these spaces are more general than directed graphs.
- andrewflnr 10y ago
  The point isn't necessarily one graph representation, but simply that any problem can be looked at in a graphy manner if you try hard enough, so "hey, it's a graph" isn't an interesting insight. But to answer your question, data flow graphs are a general representation of function composition, and Turing machines can be looked at as graphs with labeled edges. Yes, we're using "isomorphism" in the pop-compsci, Gödel-Escher-Bach sense.
- jsprogrammer 10y ago
  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.

Could you clarify: What are the nodes and edges? May the graph contain cycles? May the graph be infinite? If the graph is infinite, do we need a distinguished initial node? Do non-isomorphic graphs always correspond to different computations, or do you have a coarser notion of equivalence (say, graph homeomorphism)? I've read papers where the space of possible computations for a given (typically, toy, even loop-free) nondeterministic concurrent program is represented as a directed topological space (see “directed algebraic topology” for more information), but these spaces are more general than directed graphs.

andrewflnr 10y ago
The point isn't necessarily one graph representation, but simply that any problem can be looked at in a graphy manner if you try hard enough, so "hey, it's a graph" isn't an interesting insight. But to answer your question, data flow graphs are a general representation of function composition, and Turing machines can be looked at as graphs with labeled edges. Yes, we're using "isomorphism" in the pop-compsci, Gödel-Escher-Bach sense.
jsprogrammer 10y ago
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.