Fading Shout

Fading Shout is an esoteric programming language created by User:ais523 in 2026, as part of a study into the special case of Collatz functions in which all the multipliers r_i are the same (this subset of Collatz functions are those implemented by Feed the Chaos, and are often observed in practice in small busy beavers). It has historically been difficult to prove useful results about this special case of Collatz functions, so ais523 decided to create Fading Shout as a language which had many of the same properties but was easier to reason about.

Specification

A Fading Shout program consists of a finite state machine, together with an initially all-bits-zero infinite tape of bits that acts as the program's memory, and a pointer that can point to tape elements (which only ever moves to the right, and whose initial position does not matter because the tape is initially all-bits-zero). Zero or more states of the finite state machine are considered "flip states", and zero or more states of the finite state machine are considered "halt states" (states that are neither flip nor halt states are permitted). Information about which states are flip and halt states is specified as part of the program.

Program execution proceeds by executing the following steps in a loop until the finite state machine reaches a halt state (or forever, if it never reaches a halt state):

• Read the tape element currently at the tape pointer, and provide it as input to the finite state machine (causing it to perform a transition based on whether a 0 or 1 bit was read).
• If the finite state machine is now in a flip state, flip all the bits on the tape that are a power-of-2 distance to the right of the tape pointer (i.e. the elements 1 to the right, 2 to the right, 4 to the right, etc.). As usual, flipping a bit changes it from 0 to 1 or vice versa.
• Move the tape pointer one element to the right.

Although this specification might appear to require an infinitely large data structure (because infinitely many tape elements are written to during program execution), Fading Shout can be implemented using memory linear in the length of time the program has been running via doing the flips lazily (i.e. instead of doing the flips immediately or attempting to store any of the tape, you just record which locations the tape pointer was at when a flip occurred, and whenever a tape element is read, you check to see whether it is at a power-of-2 distance from an even or odd number of tape pointer locations at which flips occurred).

Computational class

Fading Shout is Turing-complete, which can be shown by construction. The construction discussed in this section only enters a flip state when the tape pointer position is a multiple of 9 (numbering the tape so that the position of the tape pointer at the time of the first flip is 0).

One of the key ideas is to encode information about what caused a flip using the value of the tape pointer position at the time of the flip modulo 63. There are 7 possible locations for a flip modulo 63 (0, 9, 18, 27, 36, 45, and 54). When the finite state machine reads a 1 bit (which must have been flipped by at least one flip), it is always uniquely possible for it to determine which of these modulo-63 locations the flip(s) that flipped it occurred at, because (modulo 63) adding a power of 2 to a multiple of 9 always produces a value that uniquely determines which multiple of 9 it was:

• a flip at 0 (mod 63) produces 1 bits only at locations 1, 2, 4, 8, 16, 32 (mod 63);
• a flip at 9 (mod 63) produces 1 bits only at locations 10, 11, 13, 17, 25, 41 (mod 63);
• a flip at 18 (mod 63) produces 1 bits only at locations 19, 20, 22, 26, 34, 50 (mod 63);
• a flip at 27 (mod 63) produces 1 bits only at locations 28, 29, 31, 35, 43, 59 (mod 63);
• a flip at 36 (mod 63) produces 1 bits only at locations 5, 37, 38, 40, 44, 52 (mod 63);
• a flip at 45 (mod 63) produces 1 bits only at locations 14, 46, 47, 49, 53, 61 (mod 63);
• a flip at 54 (mod 63) produces 1 bits only at locations 7, 23, 55, 56, 58, 62 (mod 63).

A finite state machine can easily track the location of the tape pointer modulo 63 (by rotating between 63 sets of states whenever the tape pointer moves).

In this construction, the flip at 0 is the only flip to occur at a location that is 0 modulo 63. Thus, upon seeing a 1 bit at a location that is 1, 2, 4, 8, 16 or 32 (mod 63), the finite state machine will know that the tape pointer is currently at a power of 2 (and will know this at every power of 2). Let the bitwidth of a positive integer be the number of bits it occupies when written in binary with no leading zeroes; it is possible for the finite state machine to (after the first move) keep track of whether the bitwidth of the pointer's location is odd or even (because this changes when, and only when, the tape pointer's location is a power of 2 and the finite state machine can tell when it is in such a location). This construction uses the following additional rules for flip locations:

• for each of the seven modulo-63 locations (other than 0 (mod 63) which is used only for the flip at 0), flips at that set of locations only occur at one of the two bitwidth parities (i.e. only when the bitwidth is odd, or only when the bitwidth is even);
• flips (other than the flip at 0) only occur at locations which, when written in binary, have a 0 as the second-most-significant bit.

The finite state machine can always determine whether the distance between an observed 1 bit and the flip(s) that flipped that bit to 1 is a power of 4 or twice a power of 4 (because all flips occur at locations that are 0 mod 3, all powers of 4 are 1 mod 3, and twice a power of 4 is always 2 mod 3, so it just needs to look at the current tape pointer's value mod 3 to determine whether it was produced by adding 0+1 or 0+2 (mod 3)). This can be used to determine whether the bitwidth of the distance between the observed 1 bit and the flip(s) that flipped that bit is odd or even (powers of 4 have odd bitwidths, powers of 2 that are not powers of 3 have even bitwidths).

When the finite state machine observes a 1 bit that is not at a power-of-2 location, call the current location x = f + d, where f is the location of the flip that most recently flipped the bit to 1, and d is the distance between the current location and the flip (d must be a power of 2 because that's how flips in Fading Shout work). As explained above, the finite state machine will be able to determine, for each of x, f and d, whether its bitwidth is odd or even. Both f and d have a 0 as their second-most-significant bit when written in binary (f because flips are constrained to happen only at such locations and d because it is a power of 2 – here, 1 is interpreted as 1.0 so its second-most-significant bit is 0). This means that if the bitwidths of f and d are different, the bitwidth of x will be the same as that of whichever of f and d is larger (because with a 0 as the second-most-significant bit, it is impossible for the addition to carry and increase the number up to a wider width). Meanwhile, if the bitwidths of f and d are the same, the bitwidth of x will be one greater (because the two 1s in the most significant position will add to each other and carry). If f and d have the same bitwidth, the parity of x's bitwidth will therefore be different from both f's and d's – but if f and d have different bitwidths, the parity of x's bitwidth must match f's or d's or both. As such, the finite state machine will always be able to determine whether f and d have the same bitwidth or not.

However, for any given f, there is exactly one power of 2 d that has the same bitwidth as f (because for each possible bitwidth, exactly one power of 2 has that bitwidth). This means that, if the finite state machine enters a flip state at position f=2ⁿ + y (with y < 2^n-2), the finite state machine will as a consequence see an "f bitwidth = d bitwidth" 1 bit exactly once, at position 2ⁿ⁺¹ + y.

This mechanism can be used to allow the finite state machine to keep track of up to three nonnegative integers – each integer is given two flip locations mod 63 (one for use when the flip location has an odd bitwidth and one for use when the flip location has an even bitwidth), allowing the integer i to be encoded as 2ⁿ + 63i + the appropriate flip location offset. These integers i can be used like counters that cannot be decremented (because the finite state machine cannot react to the 1 bit at 2ⁿ⁺¹ + 63i + offset until it has actually read that bit), but which can be compared to each other (because when two integers are equal, the finite state machine will see the resulting 1 bits at locations which are within 63 of each other and finite state machines are able to count to 63). Three increment-only integers, together with an equality test and a finite state machine, are sufficient to be Turing complete (the basic idea is to treat the difference between the first and third integer as one counter, and the difference between the second and third as another counter – this lets you increment a counter by incrementing one of the integers, decrement a counter by incementing two of the integers, and zero-test a counter by comparing two of the integers for equality).

Relationship to Collatz functions

Fading Shout is a Collatz function over GF(2)[X], the univariate polynomial ring over GF(2). (Normally "Collatz function" indicates a Collatz function whose domain and codomain are integers, but Fading Shout uses a different ring.) Numbers in GF(2)[X] act similarly to the integers expressed in binary, except that they are expressed as a sum of powers of X rather than of powers of 2, and multiplication and addition do not carry (e.g. 1 + 1 = 0 and (X+1) × (X+1) = X² + 2X + 1 = X² + 1). (The powers-of-X notation is used because in GF(2)[X], 2 and 0 are the same number, so the number formed of the digits 10 needs to be given a name other than 2.) Subtraction is the same operation as addition (because 1 + 1 = 0 and thus −1 is the same number as 1), and division is done using long division (possibly producing a remainder if the numbers do not divide exactly). See wikipedia:Polynomial ring#Univariate polynomials over a field and wikipedia:GF(2) for more information about GF(2)[X].

This ring naturally implements the "flip all the bits that are a power-of-2 distance away" behaviour of the language when using a multiplier of X² / (X+1). This is because starting with 1, and repeatedly multiplying it by X² / (X+1), forms a Sierpinski triangle that leaves a nonzero remainder only at power-of-2 locations (in the table below, each row represents the result of multiplying the previous row by X² / (X+1), and each column represents a coefficient of X, except the last which represents the remainder of the division:

X7	X6	X6	X6	X6	X6	X	1	Remainder
							1	1
						1	1	1
					1			0
				1	1	1	1	1
			1		1			0
		1	1					0
	1							0
1	1	1	1	1	1	1	1	1

The Sierpinski triangle pattern is not obvious when the coefficients are listed right-aligned (as is normal in the table above), but becomes more obvious when seen listed left-aligned, e.g. as shown in this TIO! link.

This "flip all the bits that are a power-of-2 distance away" behaviour is linear (in the sense that adding together two or more different polynomials will end up producing a remainder of 1 if an odd number of polynomials would produce a remainder of 1 there, and a remainder of 0 if an even number of polynomials would). As such, a Collatz function using GF(2)[X] can store an unlimited amount of data just by using additions and subtractions below a fixed maximum size, with a fixed ratio of X² / (X+1) regardless of the remainder. This can be modified into a full Fading Shout implementation (including the finite state machine as well as the tape) by using the bottom few coefficients to store a number that represents which state the finite state machine is in (the additive coefficient in the Collatz function can implement the state transition by adding to the state bits, in addition to implementing flip states by adding to the coefficient immediately above).

See also

• Feed the Chaos
• Collatz function