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 IPN1.8K views1:09

🔥 Related Trending Topics

LIVE TRENDS

This video may be related to current global trending topics. Click any trend to explore more videos about what's hot right now!

THIS VIDEO IS TRENDING!

This video is currently trending in Turkey under the topic 'bursa deprem'.

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

Video Information

Views
1.8K

Total views since publication

Likes
39

User likes and reactions

Duration
1:09

Video length

Published
Aug 10, 2018

Release date

Quality
hd

Video definition