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
0or a1. - The only instruction that modifies the tape is the '
@' instruction, 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, and serve only to allow seeking the beginning of the tape while preserving which register is currently selected. This is reducible to 4 bit streams (and therefore 4 1s) if this is not required.
Conjecture: swapfuck remains Turing-complete even using only the while non-zero loops, if given 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.