CULET: Cubelets and Lego-Based Universal Turing Machine Implementing ECA Rule 110
This construction using Cubelets and Lego blocks demonstrates the emulation of any 2-symbol Turing machine. The showcased machine features 7 states and illustrates the computational capabilities of physical modular components.
ALIROB IPN
1.8K views • Aug 10, 2018
About this video
This construction with Cubelets and Lego blocks is able to emulate the execution of any Turing machine with 2 symbols. The machine of the video is a 7-states 2-symbols Turing machine which is universal duo to being able to emulate the behaviour of the elementary cellular automaton Rule 110.
The proof of the universality in Rule 110 was given by Matthew Cook and the design of this machine in particular by David Eppstein [2].
The head of the machine goes backs and forwards, every time stretching the tape and computing the generations of the cellular automaton. In the video, the steps of the machine that represents one more generation are marked with an asterisk in the right of the label indicating the state of the tape. A string labeled with an asterisk is a valid string in the evolution of Rule 110.
[1] A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2(1), 230-265, 1936.
https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230
[2] M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 1-40, 2004.
http://www.complex-systems.com/abstracts/v15_i01_a01.html
[3] S. Wolfram, A New Kind of Science, Wolfram Media, Inc., Champaign, Illinois, 2002. http://www.wolframscience.com/nks/
[4] H.V. McIntosh, Rule 110 as it relates to the presence of gliders, 1999.
http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html
[5] G.J. Martínez, H.V. McIntosh, J.C.S.T. Mora, Gliders in Rule 110, International Journal of Unconventional Computing, 2(1), 1-49, 2006.
http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC2.1abstracts/IJUCv2n1p1-49Martinez.html
[6] G.J. Martínez, A.Adamatzky, H.V. McIntosh, A Computation in a Cellular Automaton Collider Rule 110, In: Advances in Unconventional Computing: Volume I Theory, A. Adamatzky (Ed.), Springer, chapter 15, 391-428, 2017.
[7] Rule 110 repository. http://uncomp.uwe.ac.uk/genaro/Rule110.html
The proof of the universality in Rule 110 was given by Matthew Cook and the design of this machine in particular by David Eppstein [2].
The head of the machine goes backs and forwards, every time stretching the tape and computing the generations of the cellular automaton. In the video, the steps of the machine that represents one more generation are marked with an asterisk in the right of the label indicating the state of the tape. A string labeled with an asterisk is a valid string in the evolution of Rule 110.
[1] A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2(1), 230-265, 1936.
https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230
[2] M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 1-40, 2004.
http://www.complex-systems.com/abstracts/v15_i01_a01.html
[3] S. Wolfram, A New Kind of Science, Wolfram Media, Inc., Champaign, Illinois, 2002. http://www.wolframscience.com/nks/
[4] H.V. McIntosh, Rule 110 as it relates to the presence of gliders, 1999.
http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html
[5] G.J. Martínez, H.V. McIntosh, J.C.S.T. Mora, Gliders in Rule 110, International Journal of Unconventional Computing, 2(1), 1-49, 2006.
http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC2.1abstracts/IJUCv2n1p1-49Martinez.html
[6] G.J. Martínez, A.Adamatzky, H.V. McIntosh, A Computation in a Cellular Automaton Collider Rule 110, In: Advances in Unconventional Computing: Volume I Theory, A. Adamatzky (Ed.), Springer, chapter 15, 391-428, 2017.
[7] Rule 110 repository. http://uncomp.uwe.ac.uk/genaro/Rule110.html
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
1.8K
Likes
39
Duration
1:09
Published
Aug 10, 2018
User Reviews
4.5
(1)