Causal Nets

Causal Nets
The network approach to computation is more direct and "physical" than the one based on some specific computing devices (like Turing machines). However, the size of a usual -- e.g., Boolean -- network does not reflect the complexity of computing the corresponding function, since a small network may be very hard to find even if it exists. A history of the work of a particular computing device can be described as a network satisfying some restrictions. The size of this network reflects the complexity of the problem, but the restrictions are usually somewhat arbitrary and even awkward. Causal nets are restricted only by determinism (causality) and locality of interaction. Their geometrical characteristics do reflect computational complexities. And various imaginary computer devices are easy to express in their terms. The elementarity of this concept may help bringing geometrical and algebraic (and maybe even physical) methods into the theory of computations. This hope is supported by the grouptheoretical criterion given in this paper for computability from symmetrical initial configurations.
The nets of this paper are different from belief nets or Bayesian nets, which are also known under name "causal nets".

No doubt, modeling the history of computation rather than the current state is nothing new, but this paper tries to find new applications for that.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Expressing it in CT language

Reading some of the definitions and theorems, I wonder, if the paper would be more accessible if it used categorial language (look for "isomorphism", for example).

And so...

Andris Birkmanis has shown how far gone he is by suggesting something would be more accessible in categorical language.

Actually, I quite agree with him in the general case (I haven't read this paper). Some papers and concepts really could use at least a dash of the categorical perspective.

Shot with a poisoned arrow?

Shot with a poisoned arrow?

haven't looked at the paper y

haven't looked at the paper yet, but you may be interested in daniel(?) pearl's work - he published a book a while back on (and titled) causality that introduces a lot of graph related concepts.

Pearl's causal nets...

...are a kind of Bayesian net.

ok. thanks.

ok. thanks.