English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider graph Turing machines, a model of parallel computation on agraph, in which each vertex is only capable of performing one of a finitenumber of operations. This model of computation is a natural generalization ofseveral well-studied notions of computation, including ordinary Turingmachines, cellular automata, and parallel graph dynamical systems. We analyzethe power of computations that can take place in this model, both in terms ofthe degrees of computability of the functions that can be computed, and thetime and space resources needed to carry out these computations. We furthershow that properties of the underlying graph have significant consequences forthe power of computation thereby obtained. In particular, we show that everyarithmetically definable set can be computed by a graph Turing machine inconstant time, and that every computably enumerable Turing degree can becomputed in constant time and linear space by a graph Turing machine whoseunderlying graph has finite degree.

On the computability of graph Turing machines