“Remembering John Conway’s FRACTRAN, a Ridiculous, yet Surprisingly Deep Language”, 2020-05-03 (; backlinks; similar):
[Memorial for beloved mathematician John Horton Conway, who died in 2020 of coronavirus.
One of his many playful creations was the esoteric programming language FRACTRAN: a Turing-complete language implemented as simply multiplying numbers against a list repeatedly. How can this implement even the Fibonacci function, much less all computable functions, how could one come up with said implementation, and why would Conway think of this in the first place?
Braithwaite explains FRACTRAN and traces its evolution from Minsky machines: by starting with a fairly understandable model of computation and repeatedly simplifying it to an equivalent computer, one winds up with FRACTRAN, and FRACTRAN turns out to take the same form as the famous unsolved Collatz conjecture—and since each step is Turing-complete (they are all equivalent), that means questions about functions like the Collatz conjecture involving repeated multiplication are undecidable [2013] (because we have shown they are all equivalent to full-blown computer programs), and so the Collatz conjecture itself may be undecidable! And that was the serious goal of the whimsical 1987.]