[Solved]: Can we represent all computer programs as graphs?

Problem Detail: 

I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an abstract syntax graph.

It occured to me that perhaps any computer program can be represented as one of these graphs + evaluation semantics attached to it. I'm curious if anyone knows if this is universally true for a turing machine (I assume you can get a potentially infinite graph, but this is math so that's OK). I've been pondering on it and a lot of things like strong type systems and such fit well in this abstraction (they impose structural constraints on the graph). You might even be able to consider the type system its own program and represent that as a different graph + evaluation semantics operating on the program graph...

Just curious if this is a known equivalence or not.

Asked By : gct

Answered By : jmite

I don't know if it's a particularly well known equivalence, but it's fairly simple when you think about it.

Turing Machines are known to be equivalent to the (untyped) Lambda Calculus. The Church-Turing thesis proposes that this is they are the most powerful form of computation.

The Lambda Calculus is a syntactically defined term re-writing system. Essentially, it's a very simple programming language. So, it can be parsed into an abstract syntax tree (graph).

So, we have:

1. Every computer program is representable in the untyped lambda calculus.
2. Every lambda calculus program can be parsed into an abstract syntax tree

This means that every computer program can be represented as a Lambda Calculus abstract syntax tree.

These trees might not have much in the way of interesting properties. For example, they're definitely not unique i.e. two different trees can perform identical computations.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24718