FourQueue

FourQueue is an esoteric programming language made by User:Caenbe. It is supposed to be wildly inconvenient to program in, but (hopefully) not impossible. To that end, it has these features:

• Like Single Four, commands are referenced by numbers, but you can only use the digit 4.
• Data is manipulated on a queue, because doing math on a stack would be too easy.
• The two commands needed for Turing-completeness are assigned randomly.

Syntax

The only allowed characters in a program are 4s and spaces. The program is parsed as a sequence of integers, which are run as commands. They operate on a queue of integers, which is initially empty.

Commands

Command	Description
0	Halt.
1	Dequeue a and b; enqueue a + b.
2	Dequeue a and b; enqueue a - b.
3	Dequeue a and b; enqueue a * b.
4	Dequeue a and b. If b != 0, enqueue floor(a / b); otherwise, execute command a.
5	Dequeue a number and output its corresponding Unicode character.
6	Input a character and enqueue its Unicode value. EOF is -1.
x	Dequeue a, then dequeue the next a integers, then execute them in the same order they came off the queue.
y	Dequeue a and b. Dequeue the next a integers, then enqueue b copies of that sequence.

Almost any number not listed here enqueues itself. The exceptions are positive numbers which consist of two or more 4s. These enqueue the number with one less 4 than themselves: 44 enqueues 4, 444 enqueues 44, etc.

At the beginning of execution, x and y are randomly assigned values between 7 and 99 inclusive. They are guaranteed to be different from each other and from 44.

Anything not defined above (dequeueing too many things, outputting a negative number, etc.) produces the error message ERROR 44.

Example

Print 'e':

444 44 444 44 4 44 4 4 44 444 44444 444 4 4 4 4

Detailed explanation:

444 44 444 44    - enqueue 44, 4, 44, and 4
4 44             - perform a division and enqueue another 4. Queue is now 44 4 11 4
4 4              - perform 2 more divisions. Queue is now 11 2
44 444 44444 444 - enqueue 4, 44, 4444, and 44
4 4 4            - perform 3 divisions. Queue is now 5 0 101
4                - execute the 5, which prints character 101: the letter 'e'

Computational class

If the program can guess the values of x and y, any ResPairate program can be translated to a sequence of commands. To translate each pair:

n m -> 2 y x (5n) m

To execute the program, manipulate the queue into the state x 0 [program], then use the 4 command. To actually do this, programs would have to search through the possible x,y pairs one by one, cleaning up after every pair that fails. The author has not tested this method in full detail, and it probably needs some modification to work (i.e. putting in code to help with cleanup that will be ignored by ResPairate). There might also be a better way to prove Turing-completeness.

Interpreter

Here is an interpreter written in Python 3. It has a couple of wimpmode options:

• --no-prng-... guarantees x=7 and y=8.
• --any-ints-... allows any integers in the source code.

The full names of the options are long and randomly generated every time the interpreter is run, so as to discourage their use.