Abstract
We consider graph Turing machines, a model of parallel computation on a graph, which provides a natural generalization of several standard computational models, including ordinary Turing machines and cellular automata. In this extended abstract, we give bounds on the computational strength of functions that graph Turing machines can compute. We also begin the study of the relationship between the computational power of a graph Turing machine and structural properties of its underlying graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aledo, J.A., Martinez, S., Valverde, J.C.: Graph dynamical systems with general Boolean states. Appl. Math. Inf. Sci. 9(4), 1803–1808 (2015)
Aledo, J.A., Martinez, S., Valverde, J.C.: Parallel dynamical systems over graphs and related topics: a survey. J. Appl. Math. (2015). Article no. 594294
Angluin, D., Aspnes, J., Bazzi, R.A., Chen, J., Eisenstat, D., Konjevod, G.: Effective storage capacity of labeled graphs. Inform. Comput. 234, 44–56 (2014)
Aubrun, N., Barbieri, S., Sablik, M.: A notion of effectiveness for subshifts on finitely generated groups. Theor. Comput. Sci. 661, 35–55 (2017)
Baldwin, J.: Review of A New Kind of Science by Stephen Wolfram. Bull. Symb. Logic 10(1), 112–114 (2004)
Barrett, C.L., Chen, W.Y.C., Zheng, M.J.: Discrete dynamical systems on graphs and Boolean functions. Math. Comput. Simul. 66(6), 487–497 (2004)
Blass, A., Gurevich, Y.: Abstract state machines capture parallel algorithms. ACM Trans. Comput. Log. 4(4), 578–651 (2003)
Cohn, H.: Review of A New Kind of Science by Stephen Wolfram. MAA Reviews, Washington D.C. (2002)
Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1), 1–40 (2004)
Gurevich, Y.: Kolmogorov machines and related issues. In: Current Trends in Theoretical Computer Science. World Scientific Series in Computer Science, vol. 40, pp. 225–234. World Scientific (1993)
Gurevich, Y.: Sequential abstract-state machines capture sequential algorithms. ACM Trans. Comput. Log. 1(1), 77–111 (2000)
Knuth, D.E.: The Art of Computer Programming: Volume 1: Fundamental Algorithms. Addison-Wesley, Boston (1968)
Kolmogorov, A.N., Uspensky, V.A.: On the definition of an algorithm. Uspekhi Mat. Nauk 13(4), 3–28 (1958)
Lovász, L.: Very large graphs. In: Current Developments in Mathematics, vol. 2008, pp. 67–128. International Press, Somerville (2009)
Schönhage, A.: Storage modification machines. SIAM J. Comput. 9(3), 490–508 (1980)
Soare, R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, Berlin (1987)
Sutner, K.: Cellular automata and intermediate degrees. Theoret. Comput. Sci. 296(2), 365–375 (2003)
Toffoli, T., Margolus, N.: Cellular Automata Machines: A New Environment for Modeling. MIT Press, Cambridge (1987)
Woods, D., Neary, T.: The complexity of small universal Turing machines: a survey. Theoret. Comput. Sci. 410(4–5), 443–450 (2009)
Acknowledgements
The authors would like to thank Tomislav Petrović, Linda Brown Westrick, and the anonymous referees of earlier versions for helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer-Verlag GmbH Germany
About this paper
Cite this paper
Ackerman, N.L., Freer, C.E. (2017). Graph Turing Machines. In: Kennedy, J., de Queiroz, R. (eds) Logic, Language, Information, and Computation. WoLLIC 2017. Lecture Notes in Computer Science(), vol 10388. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-55386-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-55386-2_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-55385-5
Online ISBN: 978-3-662-55386-2
eBook Packages: Computer ScienceComputer Science (R0)