Sunday, May 1, 2011

Algebra view point on computation ??

Today I was trying to make a theoretical model for my peer to peer network simulator. Basically its a network of peers which is modified each loop according to certain rules (either random peer sampling or according to similarity-based clustering). The network is modeled as an adjacency matrix and to modify this matrix I may multiply it by a certain matrix; since the network is closed then it is possible to utilize a permutation matrix for that (peers exchange neighbors with each others). I also use a randomization matrix between each two operations to account for randomness in choice. So if we denote the network (adjacency matrix of the network graph) at cycle $n$ as $G(n)$, then the operation that happens in each cycle of the simulation is $$G(n+1) \leftarrow E \times R \times G(n) .$$ Where $R$ is the random permutation matrix and $E$ is the exchange matrix.

Okay, here comes an observation. Matrix multiplication is not commutative, and hence it allows us to express a sequence of operations (operators) and to express an adaptive computation. So it was fair enough to ask my self a question, non-commutativity actually added more power in this case, unlike the view common in algebras where it gets less interesting as you lose properties. So I though, what if I use Cayley-Dickson construction to make a higher algebra that is not even associative ? What would we get ? Well, I am not if this will be clear to you but I can clearly see that this allows us easily to express a tree, not just a sequence, of operations. The nature of operations might be different than a permutation or rotation, I am not sure of that, but the open question now is since a tree resembles recursion (in some sense), then could this allow us to construct a sort of universal recursive function (which would be turing-complete) ? Even more interestingly, can we construct a certain algebra in such a way to express all and only all such computations that can recognize a certain language, i.e. given a class of languages or a turing machine that recognizes them, can we construct an algebra equivalent to this machine ?

Why would this be interesting ? well, one reason that might occur to me is that if we were able to explicitly construct an algebra for $P$ and another for $NP$ then we might have another way to attack the famous $P=NP$ problem, which would then be equivalent to whether the two algebras are equivalent. This might be an interesting research direction for me, and in fact, I wrote this article as a sort of a TODO to remind me of this idea later when I finish my PhD and be able to pursue a research direction of my own. Thanks for reading and any comments or references are welcome!

No comments: