article

Free access

Simple Computation-Universal Cellular Spaces

Author:

Alvy Ray Smith, IIIAuthors Info & Claims

Journal of the ACM (JACM), Volume 18, Issue 3

Pages 339 - 353

https://doi.org/10.1145/321650.321652

Published: 01 July 1971 Publication History

PDF eReader

References

[1]

ARBIB, M.A. A simple self-reproducing universal automaton. Inform. Contr. 9 (1966), 188-189.

Google Scholar

[2]

BALZER, R.M. Studies concerning minimal time solutions to the firing squad synchronization problem. Ph.D. dissertation, Carnegie Inst. of Tech., Pittsburg, Pa., 1966.

Google Scholar

[3]

CODD, E. F. Cellular Automata. ACM Monograph Series, Academic Press, New York, 1968.

Crossref

Google Scholar

[4]

KILMER, W.L. On dynamic switching in one-dimensional iterative logic networks. Inform. Contr. 6 (1963), 399-415.

Google Scholar

[5]

LEE, C.Y. Synthesis of a cellular computer. In Applied Automata Theory, J. T. Tau, Ed., Academic Press, New York, 1968, pp. 217-234.

Google Scholar

[6]

LIEBLEIN, E. A theory of patterns in two-dimensonal tessellation space. Ph.D. dissertation, University of Pennsylvania, Philadelphia, Pa., 1968.

Google Scholar

[7]

MINSKY, M. Computation: Finite and Infinite Machines. Prentice-Hail, Englewood Cliffs, N. J., 1967.

Crossref

Google Scholar

[8]

ROGERS, H., JR. Theory of Recursive Functions and Effective Computability. McGraw- Hill, New York, 1967.

Crossref

Google Scholar

[9]

SHANNON, C. E. A universal Turing machine with two internal states. In Automata Studies, C. E. Shannon and J. McCarthy, Eds., Princeton U. Press, Princeton, N. J., 1956.

Google Scholar

[10]

SMITH, A. R., III. Simple computation-universal cellular spaces and self-reproduction. Proc. IEEE Ninth Annual Switching and Automata Theory Symp., pp. 269-277.

Crossref

Google Scholar

[11]

SMITH, A. R., III. Cellular automata theory. Tech. Rep. 2, Digital Systems Lab., Stanford U., Stanford, Calif., 1970.

Google Scholar

[12]

SMITH, A. R., III. Cellular automata complexity trade-offs. Inform. Contr. 18 (1971) (In press).

Google Scholar

[13]

SMITH, A. R., III. General shift-register sequences of arbitrary cycle length. IEEE Trans. Comp. C-SO (1971), 456--459.

Google Scholar

[14]

THATCHER, J.W. Universality in the yon Neumann cellular model. Tech. Rep. 03105- 30-T, ORA, U. of Michigan, Ann Arbor, 1964.

Google Scholar

[15]

VON NEUMANN, J. The Theory of Self-Reproducing Automata, A. W. Burks, Ed. U. of Illinois Press, Urbana, Ill. 1966.

Crossref

Google Scholar

[16]

WAGNER, E.G. An approach to modular computers I: Spider automata and embedded automata. Tech. Rep. IBM RC 1107, IBM Watson Research Lab., Yorktown Heights, N.Y., 1964.

Google Scholar

Cited By

View all

Guedes TWinter DMüller M(2024)Quantum Cellular Automata for Quantum Error Correction and Density ClassificationPhysical Review Letters10.1103/PhysRevLett.133.150601133:15Online publication date: 7-Oct-2024
https://doi.org/10.1103/PhysRevLett.133.150601
Donoso Leiva IGoles ERíos-Wilson MSené S(2024)Asymptotic (a)Synchronism Sensitivity and Complexity of Elementary Cellular AutomataLATIN 2024: Theoretical Informatics10.1007/978-3-031-55601-2_18(272-286)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-55601-2_18
Modanese A(2022)Complexity-theoretic aspects of expanding cellular automataNatural Computing: an international journal10.1007/s11047-020-09814-221:1(53-65)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11047-020-09814-2
Show More Cited By

Index Terms

Simple Computation-Universal Cellular Spaces

Recommendations

Interference Evaluation in Cellular Networks

Interference in cellular networks is one of the most common problems in the radio access network. In fact, it is the major issue in cellular networks that affects performances and quality of service. Indeed, interference can be caused by a call on the ...
A Simple Time Shift Scheme for Beacon Broadcasting Based on Cluster-Tree IEEE 802.15.4 Low-Rate WPANs

Wireless sensor networks based on the IEEE 802.15.4 standard is able to carry out short-distance transmissions in low-rate and low-power wireless personal area networks. To access the channel, it uses the slotted carrier sense multiple access with ...
Interference mitigation through reverse frequency allocation in multi-tier cellular network: a downlink perspective

With the introduction of third generation mobile services, femtocells are considered as an economically feasible solution for combining mobile and internet technologies, thereby giving fast and reliable access to data with a better coverage. However, it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 18, Issue 3

July 1971

147 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321650

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1971

Published in JACM Volume 18, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

124
Total Citations
View Citations
869
Total Downloads

Downloads (Last 12 months)96
Downloads (Last 6 weeks)12

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Guedes TWinter DMüller M(2024)Quantum Cellular Automata for Quantum Error Correction and Density ClassificationPhysical Review Letters10.1103/PhysRevLett.133.150601133:15Online publication date: 7-Oct-2024
https://doi.org/10.1103/PhysRevLett.133.150601
Donoso Leiva IGoles ERíos-Wilson MSené S(2024)Asymptotic (a)Synchronism Sensitivity and Complexity of Elementary Cellular AutomataLATIN 2024: Theoretical Informatics10.1007/978-3-031-55601-2_18(272-286)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-55601-2_18
Modanese A(2022)Complexity-theoretic aspects of expanding cellular automataNatural Computing: an international journal10.1007/s11047-020-09814-221:1(53-65)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11047-020-09814-2
Demongeot JMelliti TNoual MRegnault DSené S(2022)On Boolean Automata Isolated Cycles and Tangential Double-Cycles DynamicsAutomata and Complexity10.1007/978-3-030-92551-2_11(145-178)Online publication date: 20-Apr-2022
https://doi.org/10.1007/978-3-030-92551-2_11
Ortiz YCarrión JLahoz-Beltrá RGutiérrez M(2021)A Framework for Implementing Metaheuristic Algorithms Using Intercellular CommunicationFrontiers in Bioengineering and Biotechnology10.3389/fbioe.2021.6601489Online publication date: 10-May-2021
https://doi.org/10.3389/fbioe.2021.660148
Briceño RRapaport I(2021)Communication complexity meets cellular automata: Necessary conditions for intrinsic universalityNatural Computing: an international journal10.1007/s11047-021-09857-z20:2(307-320)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s11047-021-09857-z
Hawkins JHawkins J(2021)Cellular AutomataErgodic Dynamics10.1007/978-3-030-59242-4_14(255-278)Online publication date: 29-Jan-2021
https://doi.org/10.1007/978-3-030-59242-4_14
Banerjee RLiew T(2020)Artificial life in an exciton-polariton latticeNew Journal of Physics10.1088/1367-2630/abc29022:10(103062)Online publication date: 2-Nov-2020
https://doi.org/10.1088/1367-2630/abc290
Bhattacharjee KNaskar NRoy SDas S(2020)A survey of cellular automata: types, dynamics, non-uniformity and applicationsNatural Computing: an international journal10.1007/s11047-018-9696-819:2(433-461)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1007/s11047-018-9696-8
Banda PCaughman JCenek MTeuscher C(2019)Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumerationChaos: An Interdisciplinary Journal of Nonlinear Science10.1063/1.508988929:6Online publication date: 25-Jun-2019
https://doi.org/10.1063/1.5089889
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Interference Evaluation in Cellular Networks

A Simple Time Shift Scheme for Beacon Broadcasting Based on Cluster-Tree IEEE 802.15.4 Low-Rate WPANs

Interference mitigation through reverse frequency allocation in multi-tier cellular network: a downlink perspective

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations