A team consisting of the Unconventional Computing Lab (UCL) at UWE Bristol and Artificial Life and Robotics Lab (ALIROB) of the Instituto Politécnico Nacional (IPN) have built the first Post Machine.
A Post machine (or tag system) is a machine equivalent to a Turing’s machine and therefore equally powerful in recognising decidable problems. A Turing’s machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model’s simplicity, it is capable of implementing any computer algorithm.
In 1961, Marvin Minsky proved which tag systems are computationally universal. A Post machine can perform any algorithm as well and its substitution system is simple in essence.
This robotic Post machine is built with modular robots (Cubelets) and is the first known physical implementation of such machines. Similarly, a previous UCL and ALIROB collaboration was the first robotic Turing machine also built with modular robots.
The success of this result has been acknowledged in the recent Stephen Wolfram’s book “Twenty Years of A New Kind of Science”. The Post machine robot is referred to in the book and in the virtual gallery.
Additionally, Eric Schweikardt, founder of Modular Robotics, refers to this result as “A No Longer New Kind of Science” in his blog post.
The project is a collaboration with the UCL, led by Professor Andrew Adamatzky and ALIROB, led by Professor Genaro J. Martínez.
Professor Genaro Martínez commented on the project: This international collaboration has been very productive for more than 20 years. This interchange between both laboratories include topics in: computer science, cellular automata, robotics, complex systems, art and artificial intelligence. Relating academics and students from UK and Mexico and other countries.
Consult the Post Machine in detail.
References:
Martínez, G. J., Adamatzky, A., Figueroa, R. Q., Schweikardt, E., Zaitsev, D. A., Zelinka, I., & Oliva-Moreno, L. N. (2022). Computing with Modular Robots. International Journal of Unconventional Computing, 17(1-2), 31-60. URL: https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-17-number-1-2-2022/ijuc-17-1-2-p-31-60/
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. URL: https://download.atlantis-press.com/journals/jrnal/125905739