Bitwise Trance
| Paradigm(s) | String-rewriting |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2019 |
| Computational class | Unknown |
| Major implementations | Interpreter |
| File extension(s) | .txt |
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.
Overview
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
where 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 addr2. Values op1 and 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):
| Opcode | Alias | Description |
|---|---|---|
00
|
jmp | Write the address from the argument to the address register |
01
|
xor | Flip the bit at the address from the argument |
10
|
in | Read a bit from input and store to the address from the argument |
11
|
out | Write the bit from the address (from the argument) to the output |
Addresses (addr0, addr1, 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 1.
Here is an example: suppose we want to parse addr0 from 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
Thus, the addr0 in this example is 17. All addresses are 0-indexed.
After each instruction, address register either becomes addr1 or addr2 (in case of opcode 00), or moves after the previously parsed instruction (all other opcodes).
Memory
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 format
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)).
Examples
First example
Given the following source code:
01010100001011
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.
Truth machine
01011000001011000001110000001111000000010101111
Empty program
Empty program is infinite loop. It is equivalent to instruction 0 jmp 0 jmp 0.
Cat program
01001000110110000001
Hello, World!
0111000000110000011100000011000001110000001100000111000000111000000111000000110000011100000011000001 1100000011100000011100000011000001110000001110000001110000001100000111000000111000000111000000110000 0111000000110000011100000011100000011100000011100000011100000011000001110000001100000111000000110000 0111000000111000000111000000111000000111000000110000011100000011100000011100000011100000011100000011 0000011100000011000001110000001100000111000000111000000111000000111000000111000000110000011100000011 1000000111000000111000000111000000110000011100000011100000011100000011100000011100000011100000011100 0000111000000111000000110000011100000011100000011100000011100000011100000011000001110000001100000111 0000001100000111000000111000000111000000111000000111000000110000011100000011100000011100000011000001 1100000011000001110000001100000111000000110000011100000011000001110000001100000111000000110000011100 0000111000000111000000110000011100000011000001110000001110000001110000001110000001110000001110000001 1100000011000001110000001110000001110000001100000111000000111000000111000000110000011100000011100000 0111000000111000000111000000111000000111000000111000000111000000110000011100000011100000011100000011 1000000111000000110000011100000011000001110000001110000001110000001100000111000000110000011100000011 1000000111000000111000000111000000111000000111000000110000011100000011000001110000001100000111000000 1110000001110000001110000001110000001100000111000000111000000111000000111000000111000000110000011100 0000110000011100000011000001110000001110000001110000001100000111000000110000011100000011100000011100 0000111000000111000000110000011100000011100000011100000011000001110000001100000111000000110000011100 000011000001110000001110000001110000001100000111000000110000011
Interpreters
See also
Other languages operating on bits (implemented only):