Bitwise Trance (or simply BT) is probably a Turing complete language, but it hasn't been proven. It is similar to an assembler, except the memory is unbounded.
Every string of bits is a valid BT program. BT has one internal address register of unlimited size. When program starts, it executes instructions consecutively. Program reads each instruction from the address that is stored in the address register, decodes the instruction, executes it, then read another instruction and so on. This is the format of instructions:
addr0 op1 addr1 op2 addr2
addr0 is the address from where a bit should be read, then if the bit is
0 execute operation
op1 with argument
addr1, otherwise execute operation
op2 with argument
op2 represent operation code (opcode) and they are exactly 2 bits each. Here are the instruction descriptions (the left bit is the bit at lower address):
||jmp||Write the address from the argument to the address register|
||xor||Flip the bit at the address from the argument|
||in||Read a bit from input and store to the address from the argument|
||out||Write the bit from the address (from the argument) to the output|
addr2) are parsed in the following way: read minimal odd number of bits such that the last bit is
0, then drop all bits at even positions in the read array (0-indexed), add
1 at the end, reverse the bits, parse as binary number and subtract
Here is an example: suppose we want to parse
101110100000000101 (address register points to the start of this sequence). The minimal odd number of bits such that the last bit is
0 in this case is
101110100. Then following the above rules:
101110100 -> 0100 -> 01001 -> 10010 -> 18 (decimal) -> 17
addr0 in this example is 17. All addresses are 0-indexed.
After each instruction, address register either becomes
addr2 (in case of opcode
00), or moves after the previously parsed instruction (all other opcodes).
Memory is infinite. Addresses cannot be negative, so the lowest address is
0. Address register doesn't need to be aligned in any way (it is possible to jump inside another instruction). Source code is placed at the beginning of the memory and address register has value
0 when program starts. The rest of memory is filled with zeros.
IO operations can be implemented in various ways. For input operations, one solution is to convert all bytes from stdin to bit array. Output can be implemented like this: read pair of bits, if the first bit of a pair is
1 then write the second bit to the output stream, otherwise terminate the program (as from the instruction specification, there is no
halt instruction, so the code will run indefinitely until it is terminated from outside (note that this doesn't affect computational class in any way)).
Given the following source code:
Address register is
0, so we read the first instruction:
[0 10 10100 00 10110] -> 0 in 3 jmp 5
Notice the last zero that is not present in the source code. That is because memory is filled with zeros, we just don't write the ending zeros for simplicity.
This instruction says: read the bit at address
0, if the bit is
0 then input a bit and save to address
3, otherwise jump to address
5. Bit at address
0 is 0, so we need to read a bit from input and save to address
3. Suppose the input bit is
1, the program execution continues as following:
010101000010110 [0 00 0 00 0] -> 0 jmp 0 jmp 0
Brackets are used here to encapsulate the current instruction. Now, since both operands are the same, we jump to address
0. Notice that we are back to the start of the program execution. We can conclude that as long as
1s appear on the input stream, nothing will change. Therefore, suppose a
0 appear as the next input bit. After performing
in 3 the memory will look like this:
010001000010110 [0 00 0 00 0] -> 0 jmp 0 jmp 0
The difference is that the third bit is now
0. When we jump to the address
0, next instruction will be parsed as
[0 10 0 01 0] 0001011 -> 0 in 0 xor 0
Going further and applying rules, we can conclude that this program reads zero or more
1s, then reads one or more
0s and after it receives the next
1 it spins in a loop and doesn't read anything.
Empty program is infinite loop. It is equivalent to instruction
0 jmp 0 jmp 0.