Among many of the fascinating things that we computer scientists do with graphs
is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see what’s going on can make a huge difference. Graphs are, generally, the preferred metaphor for most computing tasks. For example, think of finite state machines, flowcharts, UML diagrams, etc.
One of the most interesting cases of this for one of the biggest programming problems today is visual representations of concurrency. Concurrent program is incredibly hard, and making a concurrency regime correct is a serious challenge – communicating that regime and its properties to another developer is even harder.
Which brings us to todays topic, Petri nets. Actually, I’m probably going to spend a couple of days writing about Petri nets, because they’re fun, and there are a lot of interesting variations. The use of Petri nets really isn’t just an academic exercise – they are seriously used by people in a lot of real, significant fields – for one example, they’re very commonly used to specify behaviors of network communication protocols.
As pointed out by a commenter, there are some really surprising places where fractal patterns can
appear. For example, there was a recent post on the Wolfram mathematica blog by the engineer who writes
the unlimited precision integer arithmetic code.
In the course of the series of posts I’ve been writing on fractals, several people have either emailed or commented, saying something along the lines of “Yeah, that fractal stuff is cool – but what is it good for? Does it do anything other than make pretty pictures?”
That’s a very good question. So today, I’m going to show you an example of a real fractal that
has meaningful applications as a model of real phenomena. It’s called the logistic map.
Yet another example of how graphs can be used as models to solve real problems comes from the world of project management. I tend to cringe at anything that involves management; as a former IBMer, I’ve dealt with my share of paper-pushing pinheaded project managers. But used well, this demonstrates using graphs as a model for a valuable planning tool, and a really good example of how to apply math to real-world problems.
Project managers often define something called PERT charts for planning and scheduling a project and its milestones. A PERT chart is nothing but a labeled, directed graph. I’m going to talk about the simplest form of PERT, which considers only time, but not resources. More advanced versions of PERT exist that also include things like required resources, equipment, etc.
There’s a kind of graph which is very commonly used by people like me for analysis applications, called a lattice. A lattice is a graph with special properties that make it
extremely useful for representing information in an analysis system.
Last time, I showed a way of using a graph to model a particular kind of puzzle via
a search graph. Games and puzzles provide a lot of examples of how we can use graphs
to model problems. Another example of this is the most basic state-space search that we do in computer science problems.
As I’ve mentioned before, the real use of graphs is as models. Many real problems can be
described using graphs as models – that is, to translate the problem into a graph, solve some problem on the graph, and then translate the result back from the graph to the original problem. This kind of
solution is extremely common, and can come up in some unexpected places.
For example, there’s a classic chess puzzle called the Knight’s tour.
In the Knight’s tour, you have a chessboard, completely empty except for a knight on one square. You can
move the knight the way you normally can in chess, and you want to find a sequence of moves in which is
visits every square on the chessboard exactly once. There are variations of the puzzle for non-standard
chessboards – boards larger or smaller than normal, toroidal boards (where you can wrap around the left edge to the right, or the top to the botton), etc. So – given a particular board, how can you
(1) figure out if it’s possible to do a knights tour, and (2) find the sequence of moves in a tour
if one exists?
Of course, just overturning the theory of computer science isn’t grandiose enough. He also claims that this solves the mind body problem, explains how free will works, and provides a potential
grand unified theory of physics. From Anderson’s own introduction on his website:
The Book of Paragon is a web site that offers one solution to the centuries old philosophical conundrum
of how minds relate to bodies. This site shows that the perspective simplex, or perspex, is a simple
physical thing that is both a mind and a body.
The perspex can be understood in many ways. Mathematically, the perspex is a particular kind of matrix; concretely, it is simultaneously a physical shape, a physical motion, an artificial neuron, and an instruction for a machine that is more powerful than the Turing machine. In other words, a perspex is an instruction for a perspex machine that is more powerful than any theoretically possible digital computer.
The perspex machine operates in a 4D space of perspexes called perspex space. This space is related to the 4D spacetime we live in. It is claimed that the perspex machine can describe any aspect of the universe we live in, and can be built from any part of our universe. In other words, the universe can be understood as a perspex machine. And, on the materialistic assumption, our bodies and minds are physical things so they, too, can be understood as perspex machines.
This site contains mathematical formulas for the perspex machine and for properties such as feeling, consciousness, and free will. These things are described in scientific papers, books, and software that you can download and run. The site also contains news items that explain the perspex machine in a non-technical way, and it has links to old research on the perspex machine.
He also claims that the Perspex machine can prove the existence of free will, God, and original sin.
One thing you’ve got to give to Anderson – the guy’s got ambition.
When you mention fractals, one of the things that immediately comes to mind for most people
is fractal landscapes. We’ve all seen amazing images of mountain ranges, planets, lakes, and things
of that sort that were generated by fractals.
Seeing a fractal image of a mountain, like the one in this image (which I found here via a google image search for “fractal mountain”), I expected to find that
it was based on an extremely complicated fractal. But the amazing thing about fractals is how
complexity emerges from simplicity. The basic process for generating a fractal mountain – and many other elements of fractal landscapes – is astonishingly simple.
Suppose you’ve got a huge graph – millions of nodes. And you know that it’s not connected – so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly new vertices and edges being added to the graph, but nothing is ever removed. Some questions you might want to ask about this graph at a particular point in time are:
How many components are there in the graph?
Which component is vertex X in?
Are vertices X and Y in the same component?
How many components are there?
All of these questions are variants of a classic computer science problem, called
union-find, which also comes up in an astonishing number of different contexts. The reason for the name is that in the representation of the solution, there
are two basic operations: union, and find. Basically, the division of the graph into
components is also a partition of the vertices of the graph into disjoint sets: union find
is a problem which focuses on a particular kind of disjoint set problem, where you can modify
the sets over time.
