Robotic tag system
Robotic Post Machine
Robotic tag system
Robotic Post Machine
Genaro J. Martínez, Ricardo Q. Figueroa, Andrew Adamatzky
The "Robotic Tag System" was done in the year 2020. It was an international project worked between the Artificial Life Robotics Laboratory (ALIROB, ESCOM, IPN) and the Unconventional Computing Laboratory (UCL, UWE).
This Robotic Tag System is constructed with modular robots "Cubelets" and LEGO bricks. The robotic Post machine is constructed with 18 Cubelets robots, as follows:
4 driver
8 battery
1 lightness
3 sense
2 rotator
A "tag system" is a formal grammar system proposed by Emil L. Post in 1920 to prove computability and undecidability. The system is based on substitution of binary symbols with binary strings.
The robot executes four operations of the Post tag system: 0 -> 00, 1 -> 1101, v=3, starting with the string 1001 which becomes periodic in the fourth iteration.
1001
11101
011101
10100
001101 *
10100
We analyze four different initial conditions from which the robot can reach one of the following states:
00011 - halt
100 - periodic
1001 - periodic
10011 - ?
Note that a robotic Turing machine was constructed with Cubelets as well and published in https://youtu.be/GIQDA5Gnxkc
References.
1.Post, E.L. (1921). Introduction to a general theory of elementary propositions. American Journal of Mathematics, 43(3), 163-185.
2.Post, E.L. (1943). Formal reductions of the general combinatorial decision problem. American Journal of Mathematics, 65(2), 197-215.
3.Davis, M. (Ed.) (1994). Solvability, Provability, Definability: The Collected Works of Emil L. Post. Birkhauser.
4.Figueroa, R.Q., Zamorano, D.A., Martínez, G.J., & Adamatzky, A. (2019). A Turing machine constructed with Cubelets robots. Journal of Robotics, Networking and Artificial Life, 5(4), 265-268.
5.Celebrating Emil Post & His "Intractable Problem" of Tag: 100 Years Later. YouTube: https://youtu.be/ultMxODJE7o
6.After 100 Years, Can We Finally Crack Post’s Problem of Tag? A Story of Computational Irreducibility, and More. URL: https://writings.stephenwolfram.com/2...