![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
\documentclass{report}
%this is an EasyLatex? source file
\input xy \xyoption{all}
\author{Bayle Shanks} \title{Speculation on graph computation architectures and computing via synchronization}
\begin{document} \maketitle
Note: Updated versions of this document, document source files, and related documents may be available at
http://purl.net/net/bshanks/work/papers/computingWithGraphsAndSynchronization2004/
I recommend that you check that site before reading this; perhaps someday there will be a rewritten, more concise version, or a pointer to a subsequent paper, which could save you time.
\tableofcontents
\part{Main report} \chapter{Introduction}
For this project, I tried to take a step back and explore some ways that the brain might implement simple computations. Rather than being driven by biological constraints, this project was an attempt to think of some unexpected and/or unlikely architectures.
The topic is computing with graphs. Given that computation is being realized via a structure of nodes connected by edges, what sort of mechanisms might be used to compute? More specifically, at each time step there is a graph representing the current state of the network. There is some set of "update rules" which, when given the state of the graph at time $t$, will tell you what its state will be at time $t+1$. See Appendix \ref{appDefn} for a more formal definition of graph computation.
My goal, then, is to explore what types of graphs, graph structures, and update rules might be suitable for computation. Clearly, there are an infinite variety of possible setups that would have Turing-equivalent computational power. It may still be valuable, however, to look at a few exemplars from this infinite set in order to strengthen one's intuition about what might be possible\footnote{Eventually it may be valuable to come up with some mathematical proofs which detail some of the structure of the class of ways that one might compute with graphs. I haven't gotten there yet, though.}.
A Turing machine is a mathematical construct which gives some rigor to the question, "Can this machine compute?".
We want to to find computing architectures which are as powerful as Turing machines\footnote{I did not rigorously prove that any of the architectures were Turing-equivalent. This might be a good thing to do sometime.}. I've found\footnote{I haven't proved them but I think they're correct} some simple criteria for when a graph computation architecture will be as powerful as Turing machines. It is necessary and sufficient that such an architecture be able to express\footnote{as a subgraph} a NAND gate, be able to express a COPY gate, and be able to compose them. See Appendix \ref{appTuring} for much more elaboration on Turing machines and on when a graph computation architecture is as powerful as a Turing machine.
See Appendix \ref{appDefn} for my formal definition of a "graph computation machine".
We want to impose some sort of locality restriction on the update rule. There are many kinds of locality restrictions that we could impose.
For example, we could require that the change of state of a node be determined only using information about the state of the arcs connected to that node. A more permissive version of this would allow information about the state of neighboring nodes to be used. Similar update rules could be applied to the state of arcs.
More interesting notions of locality would allow access to other "local graphical structure". For instance, while recalculating the state of a node, we may allow ourselves to ask if that node is a member of any cycle. This information is not available merely by considering the state of neighboring nodes and the arcs between them, yet it is, in a sense, "local", because there could still be regions of the network about which the node has no information:
\begin{figure}[h] \centering \begin{graph} rankdir=LR size="3,3" X -> A -> B -> C C -> X Q -> Y -> B B -> Q \end{graph}
\caption{In this example, the connectivity of Q and Y is irrelevant to the question of whether X is in a cycle. We are assuming that Q and Y are forbidden from ever connecting to X, A, or C.} \end{figure}
Graph computation, as I have defined it here, is a generalization of cellular automata. See Appendix \ref{appCell} for details.
Notably, there has already been some work on cellular automatons which can contain machines of Turing-equivalent power. For example, Conway's Game of Life can support Turing-complete machines.
Conventional neural networks focus on nodes as the primary computational elements. But what other structures are important in graphs?
Maybe we should try to think of ways that computation may be accomplished using some of these other choices as the basic elements.
\chapter{Arc computation} This chapter is about computation which uses arcs, not nodes, as the basic computational elements. Conventional neural networks may be visualized as pulses of activation traveling down a line from one node to another. The pulses arrive at nodes, which perform some simple computation, and then perhaps emit a pulse of their own, which travel to other nodes.
Instead of visualizing pulse of activation traveling down lines, visualize the lines themselves flickering on and off. In an ideal arc computation network, none of the computational "action" is in the individual impulses, and all of the action is in the changing structure of the connections between the nodes.
What are the analogs of "logic gates" in arc computation?
The analog of binary values is the presence or absence of an edge in the graph.
Gates can often be formulated as subgraphs. Define some potential arcs in the subgraph as "input ports" and some potential arcs as "output ports". Assume that we have chosen a fixed update rule. If, for this update rule, the effect of the subgraph's input ports on its output ports is the same no matter what bigger graph it is embedded in\footnote{out of the allowed graphs for the chosen graph computation machine. That is to say; you are allowed to "disallow" certain graph structures so that they don't break your gates!}, then we can use the subgraph like a subroutine. A logic gate is just a very simple subroutine.
For example, for some update rules the subgraph in Fig. \ref{gate1} functions as a NAND gate.
\begin{figure}[h]\centering \begin{graph} rankdir=LR size="3,3" A -> B [label="input 1", dir=none, style=dotted, weight=50] A -> C [label="output", dir=none, style=dotted, weight=50] B -> C [label="input 2", dir=none, style=dotted, weight=50] \end{graph} \caption{Triangular logic gate schematic for arcs. The dotted lines represent potential arcs.} \label{gate1} \end{figure}For the structure in Fig. \ref{gate1} to work like a NAND gate, it must always satisfy the truth table in Fig. \ref{ttTriNAND}.
\begin{figure}[h]\centering \begin{tabular}{| l | l | l | } |
Triangles form a natural structure for gates because they have three sides. However, implementing triangle gates in certain physical systems may give us grief because two of the input sides share a node. So we may want to use a four-node "square" structure instead, as in Fig. \ref{4nodeSchm}.
\begin{figure}[h]\centering \begin{graph} size="2,2" A -> B [style=invis] A -> C [label="input 1", dir=none, style=dotted, weight=50] B -> D [label="input 2", dir=none, style=dotted, weight=50] C -> D [dir=none, style=dotted, weight=50] {rank="source" A; B;} {rank="sink" C; D;} \end{graph} \caption{A logic gate schematic. CD is the output. The dotted lines represent potential arcs.} \label{4nodeSchm} \end{figure}And for the structure in the last figure to work like a NAND gate, it must always satisfy the truth table in Fig. \ref{ttSqNAND}.
\begin{figure} \begin{tabular}{
| l | l | l | } |
If arcs are synapses, then arc computation provides a theoretical model for computing with \emph{plasticity} instead of with action potentials. Perhaps in some parts of the brain, the "fundamental unit of data" is synapse strength, not activation\footnote{Of course, for plasticity to be fast enough, we would probably want to model not just long-term plasticity but also short-term plasticity such as faciliation and depression. But then again, maybe some brain areas just compute slowly.}.
In the brain, we might interpret nodes as neurons, and arcs as representing \emph{synchrony} between neurons within a time step. This will allow us to model\footnote{Synchronization is a complex set of phenomena which cannot be completely modeled without tools like differential equations and nonlinear dynamics. We will abstract away from the actual physics of synchronization. Instead, we're looking for a "qualitative physics" of synchronization. "Qualitative physics" is a cognitive science term which basically means abstracting most of the numbers away and only modeling the state transition diagram between different regimes of the system.} synchronization-based neural computation with graphs.
These "implementation details" are separate from the question of what kinds of Turing-complete graph computation machines exist, so I've put them in a separate chapter. Often, a qualitative physics is not itself an update rule, but is rather an explanation for why the update rule is what it is, or how the update rule might be implemented in a physical system; that's why they are "implementation details".
For other general notes on arc computation, see Appendix \ref{appArc}.
\chapter{Computing with synchronization}
This chapter considers a special case of arc computation, that is, when the arcs represent synchronization between two nodes. It covers what synchronization might mean, and points to appendices which give simple models of neural synchronization, and logic gates implemented in those models.
Consider a population of neurons evolving over some short period of time $\Delta t$. What sort of notions of "synchronization" might help us compute?
For any two neurons $a$ and $b$, if the output $a$ and $b$ over $\Delta t$ are identical, we say that $a$ and $b$ are \emph{exactly synchronized}.
Sometimes the only output that we are concerned about is spike times. Let $A$ be the set of spike times of $a$ during $\Delta t$, and let $B$ be the set of spike times of $b$ during $\Delta t$.
Exact synchronization is reflexive, symmetric, and transitive. It is an \emph{equivalence relation}, and at any given time\footnote{with an associated time window}, the relation of exact synchronization partitions the network into equivalence classes\footnote{i.e. groups of neurons which are doing exactly the same thing during the time window}.
If we visualized exact synchronization between nodes by drawing an arc between nodes when they were exactly synchronized, then the graph would consist entirely of cliques\footnote{a clique is a subset of fully-connected nodes}. For example, if we have nodes $a, b, c, d, e$, and $a,b,c$ and $d,e$ were exactly synchronized near some time $t$, then we might represent the synchronization state of the network with this graph:
\begin{figure}[h]\centering \begin{graph} size="2,2" rankdir=LR a -> b -> c -> a [dir=none] d -> e [dir=none] \end{graph} \caption{A graphical representation of the state of some network near time $t$, where arcs denote exact synchrony at time $t$} \end{figure}See Appendix \ref{appMoreSyncDefn} for some other notions of synchrony that might be useful, and a few notes on their mathematical structure.
Sometimes I'll use the term "sync arc" to mean an edge denoting exact synchronization between two neurons. These "sync arcs" are different from the underlying "connective edges" of the network. Sync arcs represent the presence of synchronization at some time step, whereas connective edges represent a synaptic connection. I'll usually draw sync arcs as dotted lines.
How might we implement "logic gates" with exact-synchrony based computing? See Appendix \ref{synchGates1} for implementations of the fundamental boolean gates, and Appendix \ref{nonboolSynchGates} for implementations some other, non-boolean gates. Those sections also contain 3 distinct "qualitative physics" models of synchronization.
In Appendix \ref{appDynamic}, you'll find a definition of another kind of synchrony, \emph{dynamic synchronization}, which is applicable to forced nonlinear oscillators. A common phenomenon in such systems, the "Devil's staircase", is introduced. Also, a brief definition of "circle maps" is given; circle maps are simple, well-studied discrete dynamical systems which exhibit mode-locking and the Devil's staircase, and which are special cases of integrate-and-fire neurons.
Perhaps we could use the presence or absence of dynamic synchronization to represent binary data. In this framework, a logic gate might be represented as a nonlinear oscillator receiving input from two forcing oscillators. The oscillator would itself be forcing a third oscillator. The synchronization or lack of synchronization between these oscillators would represent binary inputs and output. Fig. \ref{nonlinGate} shows how such a logic gate might look.
\begin{figure}[h] \centering \begin{graph} size="1,1" A -> X B -> X X -> C \end{graph} \caption{What a logic gate might look like using dynamic synchronization. Each node above represents a nonlinear oscillator, and the arrows represent forcing. When A and X are in dynamic synchronization, then we say that "input 1 is TRUE". When B and X are in dynamic synchronization, we say that "input 2 is TRUE". When X and C are in dynamic synchronization, we say that "the output is TRUE".} \label{nonlinGate} \end{figure}
Appendix \ref{appMisc} has a few other notes on other ways to model synchronization.
\chapter{Computing with cycles} Another fundamental unit that we could compute with is cycles. There are at least three ways that we could look at cycles:
Have a notion of locality in which a node can "know" not just its neighbors, but also if it is involved in a cycle, and perhaps which of its arcs are involved in a cycle. Binary logic would be represented as whether a node is part of any cycle, or whether it is not. Each node represents one bit; 0 means not a part of any cycle, 1 means part of a cycle.
Another way to think about things would be to look at all potential cycles in the graph. Binary logic would be represented as whether each potential cycle was an actual cycle. Each potential cycle is one bit; the bit is 0 if the cycle is not active, and 1 if it is.
A third way would be to have a notion of locality in which a node $a$ can know, for any other node $b$, if $a$ and $b$ are both part of some cycle. Note that each node has the potential to be members of many cycles.
Fig. \ref{cycleGate1} shows what a gate might look at in an Is-This-Cycle-Active system: \begin{figure}[h] \centering \begin{graph} size="3,3"
subgraph clusterABC { "Gate's internal machinery" [shape=box, style=filled] A1 -> "Gate's internal machinery" [dir=none]; B1 -> "Gate's internal machinery" [dir=none]; C1 -> "Gate's internal machinery" [dir=none]; }
subgraph clusterA { style=invis "A1" -> "A2" -> "A3" -> "A1";
}
subgraph clusterB { style=invis "B1" -> "B2" -> "B3" -> "B1"; }
subgraph clusterC { style=invis "C1" -> "C2" -> "C3" -> "C1"; }
\end{graph}
\caption{What a two-input, one-output gate might look like. An intact cycle represents 1, a broken cycle represents 0. The inputs are the A cycle and the B cycle; the output is the C cycle. In this example, the A, B, and C cycles are all intact, so the input is TRUE, TRUE, and the output is TRUE} \label{cycleGate1} \end{figure}
For perspective, Fig. \ref{cycleGate2} shows what the same gate might look like if it were receiving FALSE, FALSE, and sending TRUE: \begin{figure}[h] \centering \begin{graph}
subgraph clusterABC { size="3,3" "Gate's internal machinery" [shape=box, style=filled] A1 -> "Gate's internal machinery" [dir=none]; B1 -> "Gate's internal machinery" [dir=none]; C1 -> "Gate's internal machinery" [dir=none]; }
subgraph clusterA { style=invis "A1" -> "A2" "A3" -> "A1";
"A2" -> "A3" [style=invis] }
subgraph clusterB { style=invis "B1" -> "B2" "B3" -> "B1";
"B2" -> "B3" [style=invis] }
subgraph clusterC { style=invis "C1" -> "C2" -> "C3" -> "C1"; }
\end{graph} \caption{What a two-input, one-output gate might look like. An intact cycle represents 1, a broken cycle represents 0. The inputs are the A cycle and the B cycle; the output is the C cycle. In this example, the A and B cycles are "broken", and C cycle is intact, so the input is FALSE, FALSE, and the output is TRUE} \label{cycleGate2} \end{figure}
See Appendix \ref{appCycleNAND} for a toy physics/update rule for doing cycle computation, and an implementation of a NAND gate within this framework.
\newpage
\chapter{References}
Vaughan Pratt's CS353 notes, http://boole.stanford.edu/cs353/handouts/book3.pdf
Ingo Wegner, "The Complexity of Boolean Functions, http://eccc.uni-trier.de/eccc-local/ECCC-Books/wegener\_book\_readme.html
S. Coombes and P. C. Bressloff. Mode-locking and Arnold tongues in integrate-and-fire neural oscillators. http://www.lboro.ac.uk/departments/ma/preprints/papers99/99-9.pdf
Rodrigo Laje and Gabriel B. Mindlin. Highly Structured Duets in the Song of the South American Hornero. Phys. Rev. Lett. 91, 258104 (2003). http://www.santafe.edu/sfi/education/international/intlfellows/intlfal02/fellows/files/mindlin.pdf
Eric W. Weisstein. "Circle Map." From MathWorld?