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. 1.Post, E.L. (1921). Introduction to a general theory of elementary propositions. American Journal of Mathematics, 43(3), 163-185.

  2. 2.Post, E.L. (1943). Formal reductions of the general combinatorial decision problem. American Journal of Mathematics, 65(2), 197-215.

  3. 3.Davis, M. (Ed.) (1994). Solvability, Provability, Definability: The Collected Works of Emil L. Post. Birkhauser.

  4. 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. 5.Celebrating Emil Post & His "Intractable Problem" of Tag: 100 Years Later. YouTube: https://youtu.be/ultMxODJE7o

  6. 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...