BitChanger
BitChanger is a version of brainfuck that operates only on bits, and was created December 2, 2000 by Jeffry Johnston.
Commands
| Command | Meaning |
|---|---|
| } | Invert the bit that the current tape cell holds, and move the tape head right. |
| < | Move tape head left. |
| [ | Jump past matching ] if current tape cell holds 0. |
| ] | Jump back to matching [ |
Conversion process
The conversion process from from brainfuck to BitChanger follows:
Original instructions: + - > < . , [ ]
Combine "+" and "-" by restricting each memory location to a 1-bit value (0 and 1 only). A "+" or "-" is then really the same as an inverse. Call the new instruction "@":
Intermediate instruction set: @ > < . , [ ]
Combine ">" with "@", and call it "}". Because the memory is restricted to 1-bit, the sequence "}<}" is the equivalent of a ">". The pointer moves forward and memory is inversed, then the pointer moves backward, then moves forward again and memory is inversed, but this second inverse operation changes the memory value back to the original, however the pointer is now one to the right from where it started off.
I/O was memory mapped, resulting with:
BitChanger instruction set: < } [ ]
There was a second version of BitChanger, but it went a little overboard, trying to use memory mapping of "[" and "]" to result with only the two instructions "<" and "}". It was almost certainly not Turing-complete.
Gregor Richards determined the following way to do memory mapped I/O:
Cell Description ---- ----------- 5 set to 1 to perform input or output 6 set by input operation: 1=EOF, 0=otherwise 7 0=input, 1=output 8-15 I/O bits The pointer starts at cell 16.
Computational class
BitChanger is sometimes assumed to be Turing-complete, on the argument that, well, if brainfuck with 8-bit cells and an unbounded tape is Turing-complete, then brainfuck with 7-bit cells and an unbounded tape must also be Turing-complete, and then brainfuck with 6-bit cells and an unbounded tape must also be Turing-complete, and so forth down to one-bit cells.
This sort of reasoning is not guaranteed to be sound, however -- if you carry it one step further, you conclude that brainfuck with zero-bit cells and an unbounded tape must also be Turing-complete, which is obviously not the case. There are also cases of automata being found to have certain properties over an alphabet of size 3, but not having those properties over an alphabet of size 2 (see On Two Letters versus Three (Kozen, 2002)).
What is actually needed to establish that BitChanger is Turing-complete is a reduction from a language that is known to be Turing-complete.
It should be easy to give a reduction from Boolfuck to BitChanger, as the languages are very similar. Alternately, the reduction from brainfuck to Boolfuck, given by the author of Boolfuck, that shows that Boolfuck is Turing-complete, could be adapted to reduce to BitChanger instead.
The memory-mapped I/O in BitChanger is the only place where an involved translation would need to happen, but even that is not difficult to imagine (e.g. at the start of execution, place a distinctive bit pattern near the memory-mapped tape cells; whenever I/O needs to take place, write a (different) distinctive bit pattern to the current location, seek left until you find the distinctive bit pattern that indicates the memory-mapped area, do your I/O thing, then seek right to find the distinctive bit pattern that indicates where you were). And even so, simulating I/O exactly is not generally required to show Turing-completeness.
See also
- ZOWIE's memory-mapped control flow was inspired by the failed attempt to memory-map "[" and "]" in the 2nd version of BitChanger
Derivatives of BitChanger:
Other languages operating on bits (implemented only):