Both programs and simple graphs can be enumerated using natural numbers (positive integers).

However, what languages or ideas most naturally combine the two?

For example enumerating programs using graphs instead of natural numbers.

Or executing graphs, in other words code described by a graphs shape instead of by text, and not just for tree shaped graphs.


migrated from programmers.stackexchange.com Nov 17 '14 at 1:34

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • $\begingroup$ Would state machines count? A state machine is a (very limited) program and it's also a graph (where edge labels are important). $\endgroup$ – svick Nov 16 '14 at 18:29
  • 1
    $\begingroup$ Good thinking, but if this is a Finite State Machine, I'm not sure thats a program as such, although maybe with some context of how to make it so it might be. However there would likely be more involved in the definition of a program than shape of a graph, such as values at the nodes. $\endgroup$ – alan2here Nov 16 '14 at 20:08
  • $\begingroup$ You assume that every two countable sets are connected by a "meaningful" translation. This is (sorry) absurd. The set of all humans and the set of pens on my desk are both countable but (arguably) not related at all. $\endgroup$ – Raphael Nov 17 '14 at 11:23

We can summarize your original findings as follows: there is an effective enumeration for programs and graphs. An effective enumeration of a countable set $S$ is a computable bijection between the natural numbers and $S$, that is, a program $P(n)$ such that $S = \{ P(n) : n \geq 0 \}$ and $P(n) \neq P(m)$ for $n \neq m$.

There are many countable sets which can be effectively enumerated – there is nothing special about programs and graphs. We can generalize and say that if $S_1,S_2$ can be effectively enumerated, then there is a computable bijection between $S_1$ and $S_2$ (why?), but this doesn't say much about any relation between $S_1$ and $S_2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.