The Program Is Mostly Ignored
The Program Is Mostly Ignored (or TPIMI for short) is an esoteric programming language, originally created by User:ais523 in 2019 to prove 3-Echo Tag Turing-complete. ais523 subsequently created an alternate version of the language to prove 2-Echo Tag Turing complete.
Specification
Original version
In the original version of TPIMI, the state of a running TPIMI execution contains three pieces of state: the program, the blockchain, and the instruction pointer. The instruction pointer starts at 0; the program is specified by the user (and thereafter never changes); the blockchain's initial value is specified by the user, but can be appended to over the course of program execution (i.e. the blockchain can change, but only by having things appended at its end). The blockchain has a finite length at any given point in time (but can grow without bound). The program is infinite, but periodic (i.e. it must consist of a specific sequence of blocks repeated infinitely many times, and would be stored in a file via using just a single copy of that sequence).
The blockchain and program are both one-dimensional structures made out of blocks appended to each other. Blocks come in four different colours: red, blue, green, and white. The only other relevant aspect of blocks is their size; as TPIMI is one-dimensional, the size is measured in only one dimension, and thus blocks have a length. The length of each red, blue, and green block must be an integer. The length of a white block need not be an integer, but must be a multiple of ⅑.
The program and blockchain effectively use the same coordinate system, and can be thought of as existing side-to-side; for example, the section of the program between positions 3 and 4 and the section of the blockchain between positions 3 and 4 correspond to each other. Program execution, therefore, consists of the instruction pointer moving from position 0 continuously to the right, appending things to the blockchain based on what blocks it encounters (in the program or blockchain) as it moves. The block that's observed on the blockchain is the primary determiner of what happens (and, in most but not all cases, specifies that the corresponding part of the program should be ignored). The fractional part of the instruction pointer at the start of the block is also relevant. (It should be noted that parts of the program or blockchain "behind" the instruction pointer will never be relevant again. Thus, the blockchain acts like a queue, but a sort of queue that's synchronized with the program rather than existing in the abstract.)
Here are all the possible things that can happen during program execution:
Beyond the end of the blockchain
If program execution ever overtakes the end of the blockchain, the program halts.
When the blockchain has a white block
When the instruction pointer reaches the start of a white block within the blockchain, it moves to the end of that white block with no other changes; the corresponding part of the program is ignored, and nothing is appended to the blockchain. The only change is thus to the instruction pointer. (One of the main uses of white blocks in the blockchain is therefore to change the fractional part of the instruction pointer, as they're the only blocks that can have non-integer size. However, they can also be used to skip portions of the program in the same way as a conditional statement or the 0 command from cyclic tag.)
When the blockchain has a red block
When the instruction pointer reaches the start of a red block within the blockchain, its fractional part must be ⅑; otherwise, undefined behaviour results. If the fractional part is ⅑, then the instruction pointer moves to the end of that red block, and a blue block that's twice as long is appended to the blockchain. The corresponding part of the program is ignored.
When the blockchain has a blue block
When the instruction pointer reaches the start of a blue block within the blockchain, the instruction pointer moves to the end of that blue block, and a block of the same size is appended to the blockchain. The corresponding part of the program is ignored.
The colour of the block that's appended to the blockchain depends on the fractional part of the instruction pointer:
| (IP mod 1) × 9 | Colour of appended block |
|---|---|
| 0 | Red |
| 1 or 4 | Blue |
| 5 | Green |
| 2, 3, 6, 7, or 8 | Undefined behaviour |
When the blockchain has a green block
When the instruction pointer reaches the start of a green block within the blockchain, the instruction pointer moves to the end of that green block, and a block or string of blocks of ⅑ the size is appended to the blockchain:
- If the (IP mod 1) × 9 is 3, 4, 6, or 7, then a single white block is appended (of size ⅑ the size of the green block on the block chain), and the corresponding part of the program is ignored.
- If the (IP mod 1) × 9 is 1, 2, 5, or 8, undefined behaviour results.
- If the IP is an integer, then the part of the program that corresponds to the green block is, for once, not ignored. Rather, a copy of that corresponding part of the program is appended to the blockchain, but at ⅑ the size. This causes undefined behaviour unless the program contains a block starting at the same place as the green block started, and a block (not necessarily the same block) ending at the same place as the green block ended; it also causes undefined behaviour if one of the blocks in it becomes an invalid size when scaled down (i.e. any white blocks in this portion of the program must have integer size, and the size of any red, blue, or green blocks must be a multiple of 9).
Summary
All cases not listed are undefined behaviour.
- Red (min size 1):
- IP = 1/9 mod 1 → blue (size × 2)
- Blue (min size 1):
- IP = 0/9 mod 1 → red (size × 1)
- IP = {1,4}/9 mod 1 → blue (size × 1)
- IP = 5/9 mod 1 → green (size × 1)
- Green (min size 1)
- IP = {3,4,6,7}/9 mod 1 → white (size ÷ 9)
- IP = 0 mod 1 → from program (size ÷ 9)
- White (min size ⅑):
- any IP → any (size × 0)
Modified version
The modified version of TPIMI works in a very similar way to the original, but adds two more colours of block (cyan and turquoise), and has different rules for minimum block sizes and for the relationships between the various colours of blocks. (There is still a requirement for the size of a block to be a multiple of its minimum size.) Here are the new rules, in the same format as the summary in the previous subsubsection:
- Red (min size 1):
- IP = 6/48 mod 1 → blue (size × 1¼)
- Blue (min size 1):
- IP = 33/48 mod 1 → red (size × 1)
- IP = {0,12,24,36}/48 mod 1 → blue (size × 1)
- IP = 2/48 mod 1 → cyan (size × 1)
- Cyan (min size 1):
- IP = 34/48 mod 1 → turquoise (size ÷ 2)
- Turquoise (min size 1):
- IP = 20/48 mod 3 → green (size ÷ 3)
- Green (min size 1)
- IP = 3/48 mod 1 → white (size ÷ 48) (many other offsets also work but are not listed here)
- IP = 32/48 mod 1 → from program (size ÷ 48)
- White (min size 1/48):
- any IP → any (size × 0)
Implementations in Echo Tag
Implementation of the original version in 3-Echo Tag
In this section, for conciseness and ease of reading, 000 will be represented as 0, and 111 will be represented as 1. Whitespace has also been added for clarity (although Echo Tag does not use it), splitting examples into groups of 27 elements.
Sizes in TPIMI correspond directly to lengths in Echo Tag, with a scale factor of 81 bits (e.g. a size 2 block is 162 bits long, a size ⅑ block is 9 bits long, etc.). The blockchain of The Program Is Mostly Ignored corresponds directly to Echo Tag's data queue. The encoding is as follows:
- Red block, size n: n repeats of
111111111 111111111 000000000 - Blue block, size n: n repeats of
111111111 000000000 000000000 - Green block, size n: n repeats of
000000000 000000000 000000001 - White block, size n/9: n repeats of
000
Meanwhile, the production list consists of a number of repeats of the following sequence of elements (with x and p substituted):
111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxxppp
x here represents an irrelevant element (that could be 0 or 1 without disturbing the behaviour of the program). p represents three bits taken from the program. Each size-1 segment of the program corresponds to one of the (81-bit) repeats of the sequence above; and the p bits are determined via taking three bits from the (non-echoed) encoding of the relevant block ⅑ the size. (If ⅑ the size of the block would be an invalid size, then the program block must necessarily be ignored, thus the value of the p bits does not matter.)
So for example, a white block within the program of size 2 would look like this:
111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000
and a green block of size 9 would look like this:
111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx000 111111111 111111111 000000000 000000000 111111111 000000000 000000000 000000001 xxxxxx001
With this correspondence, the 3-Echo Tag productions directly implement the original version of TPIMI, with every (data queue + offset within productions) combination in Echo Tag doing the same thing as the corresponding (blockchain block + offset within program) combination in TPIMI.
Implementation of the modified version in 2-Echo Tag
For conciseness, the notation 0 will be used for 0000, 1 for 1111, b for 1100.
The basic nature of the construction is the same as for the original version. The scale factor between TPIMI sizes and Echo Tag bit lengths for this construction is 192 (thus the smallest possible block, a white block of size 1/48, has an encoding 4 bits long).
The blocks on the TPIMI blockchain are encoded on the Echo Tag data queue as follows:
- Red block, size n: n repeats of
111111 111111 000000 111111 000000 111111 000000 111111 - Blue block, size n: n repeats of
111111 000000 111111 000000 111111 000000 111111 000000 - Cyan block, size n: n repeats of
110000 001111 110000 000000 110000 000000 110000 000000 - Turquoise block, size n: n repeats of
111100 000000 000000 000000 111100 000000 000000 000000 - Green block, size n: n repeats of
b00000 000000 000000 000000 000000 000000 000000 000000 - White block, size n/48: n repeats of
0
Meanwhile, the list of productions contains repeats of the following sequence (with k, q substituted):
111000 111000 111000 00k000 111000 00q111 111000 000000
Here, k is 1000 if the position of the sequence within the production list is divisible by 3, and 0000 otherwise; and q consists of two bits taken from the un-echoed version of the encoding of the program (in the same style as p from the construction of the previous section), followed by two irrelevant bits.
With this correspondence, the 2-Echo Tag productions directly implement the modified version of TPIMI, with every (data queue + offset within productions) combination in Echo Tag doing the same thing as the corresponding (blockchain block + offset within program) combination in TPIMI.
Computational class
ais523 thinks that both versions of TPIMI are almost certainly Turing-complete, but has not formally proved this yet. (The easiest approach may be to write an algorithm that compiles tag systems to TPIMI.)