swapfuck

swapfuck is a brainfuck derivative by User:Rdococ, which replaces the typical increment and decrement instructions with a single 'swap' instruction.

Differences from brainfuck

• Input is loaded into the tape at the beginning of execution.
• Cells can only hold a 0 or a 1.
• The only instruction that modifies the tape is @, which swaps the contents of the current cell with the cell to the right.

Instruction set

Instruction	Description
@	Swaps the values of the current cell and the cell to the right.
<	Move the cell pointer to the left.
>	Move the cell pointer to the right.
[	Jump past the matching ] if the current cell has a value of 0.
]	Jump back to the matching [ if the current cell has a non-zero value.
.	Adds the bit at the current cell to the output queue. When the output queue reaches a size of 8, it is emptied and the corresponding UTF-8/ASCII character is printed.

Computational class

If the input tape contains sufficient consecutive pairs of 1 0, a swapfuck program could trivially operate on each pair as if it was a single, flippable bit.

If swapfuck's [] loops were replaced with ones that looped while the current cell was zero, not non-zero, a finite input tape of 1 1 1 1 1 1 would allow a program to simulate three-cell unbounded brainfuck, which is Turing complete.

The tape is split into 6 interleaved streams of bits. The first stream has a 1 at the position matching the value of the first register, the second stream has a 1 at the position matching the second register, and so on. The other three streams are never permanently modified, serving as 'waypoints' for seeking the beginning of the tape.

Conjecture: swapfuck remains Turing-complete with only the while non-zero loops, with a specific, finite input. This could be done by lugging 1s along as it scans the tape so it can invert each cell it scans on the fly.

Implementation

A rough implementation of swapfuck in Lua is available here.