Fading Rainbow
| Paradigm(s) | String-rewriting |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2020 |
| Computational class | Turing-complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
Fading Rainbow is a string-rewriting esolang. It may seem similar to Encapsulation, Thue and 1.1, but it is fundamentally different. Instead of matching and replacing a single occurrence of a substring in each step, Fading Rainbow deletes the entire string, keeping only substrings (their replacements) that matched in the current iteration.
Syntax
Source code consists of or more blocks, but the total number of blocks must be even. A block is either a single . character, or an array of one or more bits. Example of blocks:
. 0 1 10101 111000101010
A block cannot contain both . and bits. For example, 01. are two blocks (one being 01 and the other being .). Also, .. are two blocks. Whitespace characters are ignored (and they can be used to separate blocks that contain only bits). A block which contains . is called an empty block and it is effectively the same as an array of zero bits.
I/O format
Input and output are streams of bits. When the program starts, we first take the input, prepend the first block from the source code (as said, . is simply an empty block), then append the fourth block, then before each bit of the original input prepend the second block and after each bit of the original input append the third block. That is how we obtain the main string. For example, given the source code:
10 0 11. ....
and the input string 110. First, we enumerate blocks. The first block is 10, the second is 0, the third is 11 and the fourth is . (empty block). So, the main string will be:
10011101110011
We rewrite the main string in iterations until the program halts (details are explained in the next paragraph). When the program halts, we simultaneously do the following:
- If the main string starts with the fourth block from the end, remove it from the main string.
- If the main string ends with the last block, remove it from the main string.
- Remove each occurrence of the second and the third block from the end from the main string.
Rewriting rules
- Note: This algorithm is hard to explain. The wordings may not be clear. Please see the implementation for details
In each iteration we first initialize an empty priority queue. Each element of the priority queue will contain three attributes: block index, start position, length, and next. Note: interpreter does not need to be implemented this way, but the result must be the same as explained in this algorithm.
For each block with odd index (1-indexed) from the source code (except the first four and the last four), we enumerate all occurrences of that block in the main string (including the overlapping ones) and for each occurrence add a new element to the priority queue, having block index set to the actual block index, start position set to the index of the occurrence in the main string, length set to the length of the current block and next set to the first block that appears after this block in the source code.
After that, we first reset the main string (the main string becomes empty). Then we iterate through the priority queue and for each element we append the block next from that element. Given two elements, we compare them in the following way (apply the first case that matches):
- If they have different start position, the element with smaller start position has higher priority.
- If they have different length, the element with smaller length has higher priority.
- The element with smaller block index has higher priority.
If the last block that we consider is successfully matched, then halt the program after that iteration.
Examples
Cat
........
Invert bits
000 01.. 010 011 011 010 000. .01..
Reverse bits
1000001 1001 . 10000001 10000101000010100001 1000010 10000101000011100001 1000011 10000111000010100001 1000010 10000111000011100001 1000011 10000011000010100001 10000011000010 10000011000011100001 10000011000011 100000110000001 100000110000001100000001 10000011001010000001 1000001100001010000001 10000011001110000001 1000001100001110000001 1000001100001010000001 1000001100001010000001100000001 1000001100001110000001 1000001100001110000001100000001 1000001100101001 100000110010 1000001100111001 100000110011 100000110010100010 1000001100010 100000110010100011 1000001100011 100000110011100010 1000001100010 100000110011100011 1000001100011 10000011000101001 10000011000010 10000011000111001 10000011000011 100000110000101001 10000011000010 100000110000111001 10000011000011 100000110001010001 10000011000010 100000110001110001 10000011000011 1000001100001010001 10000011000010 1000001100001110001 10000011000011 10010100101001 10010 10010100111001 10011 10011100101001 10010 10011100111001 10011 1001010010100010 100010 1001010010100011 100011 1001010011100010 100010 1001010011100011 100011 1001110010100010 100010 1001110010100011 100011 1001110011100010 100010 1001110011100011 100011 100101000101001 10010 100101000111001 10010 100111000101001 10011 100111000111001 10011 1001010001010001 10010 1001010001110001 10010 1001110001010001 10011 1001110001110001 10011 100010100101001 10010 100010100111001 10011 100011100101001 10010 100011100111001 10011 10001010010100010 100010 10001010010100011 100011 10001010011100010 100010 10001010011100011 100011 10001110010100010 100010 10001110010100011 100011 10001110011100010 100010 10001110011100011 100011 1000101000101001 100010 1000101000111001 100011 1000111000101001 100010 1000111000111001 100011 10001010001010001 100010 10001010001110001 100011 10001110001010001 100010 10001110001110001 100011 1000010100101001 10010 1000010100111001 10011 1000011100101001 10010 1000011100111001 10011 100001010010100010 100010 100001010010100011 100011 100001010011100010 100010 100001010011100011 100011 100001110010100010 100010 100001110010100011 100011 100001110011100010 100010 100001110011100011 100011 10000101000101001 1000010 10000101000111001 1000011 10000111000101001 1000010 10000111000111001 1000011 100001010000101001 1000010 100001010000111001 1000011 100001110000101001 1000010 100001110000111001 1000011 100001010001010001 1000010 100001010001110001 1000011 100001110001010001 1000010 100001110001110001 1000011 1000010100001010001 1000010 1000010100001110001 1000011 1000011100001010001 1000010 1000011100001110001 1000011 100101001010000001 10001010000001 100101001110000001 10001110000001 100111001010000001 10001010000001 100111001110000001 10001110000001 1001010001010000001 1001010000001 1001010001110000001 1001010000001 1001110001010000001 1001110000001 1001110001110000001 1001110000001 1000101001010000001 10001010000001 1000101001110000001 10001110000001 1000111001010000001 10001010000001 1000111001110000001 10001110000001 10001010001010000001 10001010000001 10001010001110000001 10001110000001 10001110001010000001 10001010000001 10001110001110000001 10001110000001 10000101001010000001 10001010000001 10000101001110000001 10001110000001 10000111001010000001 10001010000001 10000111001110000001 10001110000001 100001010001010000001 100001010000001 100001010001110000001 100001110000001 100001110001010000001 100001010000001 100001110001110000001 100001110000001 1000010100001010000001 100001010000001100000001 1000010100001110000001 100001110000001100000001 1000011100001010000001 100001010000001100000001 1000011100001110000001 100001110000001100000001 100000001 . 1000001 100001 . 10000001100000001
Computational class
Fading Rainbow is Turing-complete because Consistent 01-2C can be compiled almost directly into it. (The only subtlety is handling the ends of the string, which can be implemented using a long string of 0s that is replaced with an even longer string of 0s; the Turing-completeness proof for 01-2C has a limit on how long a string of 0s can become in the middle of the construction, so this will match only at the ends. It may match too many times and create an excessive number of 0s, but these do not change the behaviour of the nonzero part of the program and thus do not change the computational class of the language.)