Bitwise Trance

From Esolang
Jump to: navigation, search
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

010000001101100001111110001010100

Empty program

Empty program is infinite loop. It is equivalent to instruction 0 jmp 0 jmp 0. Since this language has no way to halt entirely, this is also the closest thing the language has to a quine.