Hello today I am a unicorn
|Computational class||Turing complete|
Hello today I am a unicorn is a Turing-complete programming language that has only two variables.
There are only two variables:
y. Both are non-negative integers of unlimited size.
Source code consists of zero or more instructions. Any instruction can be prefixed by a label.
Each instruction begins with the variable name it uses (
y), then operator that is applied and operands.
~. No operands. Inverts the lowest bit of the variable. Example:
Operator Shift left
+. No operands. Performs binary shift to the left. Example:
Operator Shift right
-. No operands. Performs binary shift to the right. Example:
?. Two operands (and they are labels). If the lowest bit is
1 jump to the first label, otherwise jump to the second label. Example:
y? label1 label2 label1: x+ label2: x-
y is odd,
x will be shifted left and then shifted right. If
y is even,
x will only be shifted right.
Note: all instructions except this simply increment instruction pointer.
Input is a non-negative number. It is written in the
x variable before program starts, while
y is initially
0. When program terminates,
y contains the output.
Note: assuming the same I/O format as described here for converting from/to ASCII strings.
x? copy exit copy: x- y+ y~ y+ x? flip next flip: y~ next: x- x? copy exit exit: x~
y effectively implement two stacks of bits; you can push to these via a left-shift (possibly followed by an xor), pop them via a right-shift, and test the bottom bit via the if operator. Because the language also allows arbitrary control flow, this allows two-stack machines to be implemented more or less directly (a two-counter machine can also be implemented via treating the counter as a stack of multiple 0 bits above a single 1 bit), making the language Turing complete.