Paradigm(s) String-rewriting User:Hakerh400 2020 Turing-complete Interpreter `.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 ${\displaystyle 8}$ 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.)