Miserie

Miserie is a simple state + queue language designed by User:Keymaker. The language was created with the purpose of being easy to translate into DownRight, but due to some errors in the author's thinking, right from the start it was a considerably difficult ordeal and was not accomplished until 2025, when the language (along with the translation) was released. The language itself was designed almost to its final form in 2019.

Program and execution

The program consists of initial queue definition (which may be lacking, in which case the program cannot do anything) and at least one instruction.

Instructions are all of the same type. The instruction has its unique state label, then definitions for what it should do in case the dequeued bit is 0 or 1. Program execution starts at the first defined instruction.

Executing one instruction is: See if the queue is empty, if it is, halt program. If there is data, dequeue a bit and depending on its value either enqueue data associated with 0 or 1, then select the next state associated with 0 or 1. If data is -, append nothing. If state is *, halt. If an instruction is specified to halt the program, the specified data (if any) is added before halting.

Computational class

The language is Turing-complete. The simplest way to prove it is by translating Cyclic Tag into it, as is done on the official page. (See external resources.)

The combination of state and queue makes the language quite powerful. Aside the aforementioned Cyclic Tag translation (a queue-based system which translates easily), there is also a method for translating I/D machine into Miserie, which requires handling a considerably more complicated memory construction (I/D machine utilizes an infinite array of arbitrarily-sized non-negative integers). Various other languages would be easy to implement, too.

The language allows a translation chain right down into Cyclic Tag; a Miserie program can be translated into DownRight, which translates simply into Cyclic Tag. Unfortunately, all but the simplest Miserie-to-DownRight translations are infeasible (or impossible) to run (at least in the current times with the current computational resources), but in theory the possibilities are there.

Program example

Here is a program by User:Keymaker that computes the Collatz sequence for a given number, halting if the number reaches 1.

; collatz (halts if value 1 is reached)
; debug check1

-1111110 ; initial number in unary (1s followed by 0), expected to be at least 1

check1(-,*)(1,check1a) ; as 0 is never reached here, its data and state are just 'empty' and 'halt'
check1a(0,*)(1,scroll1) ; halt if number is 1 (meaning 0 was read from queue), otherwise proceed

scroll1(0,div1)(1,scroll2) ; if reach 0 here, number is even
scroll2(0,mul1)(1,scroll1) ; if reach 0 here, number is odd

div1(0,check1)(-,div2) ; if reach 0 here, dividing is done
div2(-,*)(1,div1)

mul1(10,check1)(111,mul1) ; append 111 for every 1 (multiply by 3), append 10 for 0 (increase by 1)

DownRight translation

The language was created for the purpose of translating a state + queue language into DownRight. More details about the translation can be found here: Miserie to DownRight translation

External resources

• Miserie page (detailed explanations of the language, Cyclic Tag translation, I/D machine translation, interpreter in Python)