Collatz-bolge: A non-universal language, unless the Collatz Conjecture is false

Speculation on an esolang

I was reading recently about Malbolge, an esoteric language that was "designed to be as difficult to program in as possible". The language just has 8 operations. Those operations are "turing complete", (up to the limitation of memory size) but several complications are added for difficulty of creating working programs. In fact, while the language was specified in 1998, it took until 2021 for the announcement of a working LISP interpreter on a related language, Malbolge Unshackled.

Here I'm concerned with the "encypher operation": After each instruction is executed, the memory position indicated by the code pointer is "encyphered" according to a fixed permutation. Part of the proof of Malbolge's turing completeness was finding cycles under the encypher operation that would predictably alternate an instruction between a useful operation and a NOP.

In Collatz-bolge, the fixed permutation is replaced with the Collatz iteration function, n' = n * 2 + 1 (n odd), n' = n / 2 (n even), and the restriction that instructions be in the range 33-126 is relaxed to requiring instructions be 33 or above. It's widely believed that (as formalized in the Collatz Conjecture) every positive integer starting value eventually falls into the repeating sequence 4-2-1. If the Collatz Conjecture is true, every Collatz-bolge program's instructions would eventually decay into non-executable instructions, making the machine halt in a finite number of steps.

On the other hand, if there turn out to be other nontrivial cycles of the Collatz iteration function, it might be possible to prove the language was universal, by using those cycles to construct a translator from Normalized Malbolge to Collatz-bolge.

(Collatz-bolge would also need Malbolge Unshackled features like unbounded register sizes; as arbitrarily large numbers can probably be constructed by extremely long ASCII programs in Collatz-bolge we could also allow a training-wheels version where immense numbers could be directly specified)

Entry first conceived on 5 August 2021, 15:41 UTC, last modified on 5 August 2021, 15:42 UTC
Website Copyright © 2004-2021 Jeff Epler