1
$\begingroup$

I've come to understand that programs are graphs on several layers. Call-graphs are an example that come to mind without a textbook handy, another is mutation flow.

So I do understand that code is a graph, and that compilers and interpreters usually end up traversing the graph according to the rules of the language. It's magic, really, but here is my question:

Are all calculations graphs? Are there calculations that cannot be expressed as a state machine?

Improve this question
$\endgroup$
2
$\begingroup$

I wouldn't say that code is a graph. I would say that graphs are a convenient way to represent some aspects of graphs.

There is a sense in which every computation on your computer can be expressed as a state machine: if your computer has 8 billion bits of memory, then there are at most $2^{8,000,000}$ possible states, so it can be considered as a state machine on that state space. However, that probably isn't a very useful point of view. Instead, we usually model computers as Turing machines (or in another way), and those cannot be expressed as a finite state machine.

The question of whether all computations are graphs doesn't seem well-defined to me. Presumably graphs can be used to represent some aspects of computations, but that doesn't mean the calculation is a graph (or that it is nothing more than a graph).

Improve this answer
$\endgroup$
  • $\begingroup$ An Abstract Syntax Tree is a tree, right? So it's a graph, because a tree is a degenerate graph. Then what about the stuff the calculation runs on, a circuit board, ie. a graph of possible electron flows. So yes, all code is a graph, but I was wondering whether all calculation was also a graph. Our brains are a biological circuit. $\endgroup$ – Joshua Moore Feb 29 '20 at 10:58
  • $\begingroup$ I'll have to read up on Turing Machines and Finite State Machines. Maybe they can be written in terms of each other? ... A little reading later: What is the difference between a Turing Machine and a Finite State Machine with arbitrarily large states? $\endgroup$ – Joshua Moore Feb 29 '20 at 11:09
  • $\begingroup$ And isn't unlimited edges the same as arbitrarily large tape, with differences perhaps between the tape mechanism and the edge lookup mechanism? $\endgroup$ – Joshua Moore Feb 29 '20 at 11:20
  • 1
    $\begingroup$ @JoshuaMoore, I'm still going to take the position that code can be represented as a graph or can be modelled with a graph. This is not quite the same thing as saying that code is a graph. (It's not entirely clear to me what the latter would mean, exactly, so I'm not sure whether I'd be prepared to make that claim.) I suggest reading about TMs, FSMs, then if you have any remaining questions, search the site, and if you can't find an answer here or in standard resources, use the 'Ask Question' button to ask a new question. $\endgroup$ – D.W.♦ Feb 29 '20 at 20:04
  • 1
    $\begingroup$ @JoshuaMoore, a finite state machine has a finite set of states (the "memory" of what it has seen, which it uses to decide what to do, is limited). A Turing machine can also store information on it's (unlimited) tape and refer to it later, so it's number of potential states (memory) has no limit. That makes quite a difference in what they are able to do. $\endgroup$ – vonbrand Mar 1 '20 at 20:33
1
$\begingroup$

Graphs are very versatile tools, useful for modelling lots of discrete situations (areas in a map and their frontiers, streets in a city, flight connections between cities, geneologies, friendship among people, ...). No wonder programs, computations, ... can be analyzed in their terms (structure, in which function calls which others, in what order instructions are executed, what values influence which others, ...). They also appear as common data structures.

Improve this answer
$\endgroup$

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.