Exploring Graph Computation Architectures for Computing and Synchronization

Title: Exploring Graph Computation Architectures for Computing and Synchronization

Abstract: This research explores the possibility of using graph computation architectures for computing and synchronization. The study investigates various graph structures and update rules to determine if they can be as powerful as Turing machines. The research proposes a locality restriction on the update rule, allowing information about neighboring nodes and arcs to be used. It also discusses the connection between graph computation and cellular automata.

Main Research Question: Can graph computation architectures with locality restrictions be as powerful as Turing machines?

Methodology: The study defines a "graph computation machine" and provides a formal definition of graph computation. It then explores various graph structures and update rules, imposing locality restrictions on them. The research also compares graph computation to cellular automata.

Results: The research finds that graph computation architectures with locality restrictions can be as powerful as Turing machines if they can express a NAND gate, a COPY gate, and compose them.

Implications: This research suggests that graph computation architectures with locality restrictions could be a viable alternative to Turing machines for computing and synchronization. It also provides a framework for further research in this area.

Conclusion: In conclusion, graph computation architectures with locality restrictions have the potential to be as powerful as Turing machines. Further research is needed to explore other graph structures and update rules that could meet the criteria for Turing-equivalence.

Link to Article: https://arxiv.org/abs/0404045v2 Authors: arXiv ID: 0404045v2