ABCDirection

ABCDirection is a 2 dimensional esolang by User:BoundedBeans.

Instructions

A	Turn right.
B	No-op.
C	Execute a command depending on the direction. right: Move pointer left. left: Move pointer right and flip the bit. up: If the value at the pointer is 1, turn left. Otherwise, go straight. down: Output like in Boolfuck.
D	Execute a command depending on the direction. right: Enqueue the current cell into the queue. left: Dequeue the current cell from the queue. up: Input the current cell like in Boolfuck. down: If the value at the pointer is 1, set direction to down. Otherwise, dequeue a value from the queue. If the front of the queue is 1 and the cell is 0, set direction to up. Otherwise, if the front of the queue and the cell are both zero, dequeue another value from the queue. If the value dequeued is 0, set direction to left. If the value dequeued is 1, set direction to right.

The pointer starts at the top left, and starts by going downwards.

Note there can be no spaces in the code, other than after a line with six consecutive D’s, B should be used instead. The source file must therefore be a rectangle consisting of only A, B, C, D, with the final line having DDDDDD somewhere in it. After the file reader reads 6 consecutive D’s in one line of code, from left to right, it reads the rest of the line, then stops. If you need to use D six times in a row before the end of the program, use B to separate it. The file reader needs to be stopped like this (6 D’s are required). Since it has stopped reading the file, anything can be written afterwards. This is a comment mechanism.

Computational class

We can view the four commands as acting on different parts of the automaton. The first two, A and B, manage the behavior of the code pointer. Using A in a file of B we can have our pointer travel along nearly any path we desire.

The C command manages interaction with an unbounded tape of bits. Since we can achieve any direction with A, we can use any function of C. We thus have access to what are effectively <, >*, and ; from Boolfuck. We can get * with <>* (C_rightC_left) and > with >*<>* (C_leftC_rightC_left). We can also conditionally rotate in any orientation we desire based on the currently selected cell with C_down.

The D command interacts with a bit queue, which also interacts with the tape.

In either case we can combine the rotation changing variants of A with C and D to achieve any given function of C or D, from any incoming direction. This effectively means we have Boolfuck's movement and invert commands. The only question for Turing completeness is the control flow. For any nested set of braces we can construct an underbar scheme like so:

( ( ) ) ( )
| +-+ | +-+
+-----+

We can translate any Boolfuck program into a linear ABCDirection program, where the tape/head alteration occurs on a horizontal strip. Control flow can be managed with these underbars, each underbar allowing for the code pointer to travel to the appropriate side of the brace without incidentally executing the wrong code.

One more complication is the starting condition. As stated, all ABCDirection programs start from the top left going down, the V in the program below:

VBBBBBBBBBBBBB
BBBBBBBBBBBBBB
BBBBBBBBBBBBBB
BBBBBBBBBBBBBB
BBBBBBBBBBBBBB
BBBBBBBBBBBBBB
BBBBBBBBDDDDDD

The behavior of the program when it encounters the edges is undefined. Additionally, the initial configuration of the queue is undefined, as is the behavior when the queue is taken from while empty. These are problematic, as it makes it nonobvious how to reach more than the leftmost column of the program.

If we assume that the edges are connected and the program is a donut, then the first command can be an A, which would wrap the code pointer around to the right side, where execution can begin.

If we assume that the queue either contains a zero at the start, or that it is considered to contain a zero when empty, and we assume that the tape is initialized to zeros, then the first command can be a D, which turns left under this circumstance.