Feed the Chaos
Feed the Chaos is an esoteric programming language created by User:ais523 in 2024. It was inspired by some thoughts that User:int-e had about Sloopy, although the resulting language ended up somewhat more like a Stun Step derivative. The language was explicitly constructed to have a particular computational class, that has empirically been frequently observed in busy beaver champions and candidates, that is not known to be Turing-complete but also is not known to be Turing-incomplete.
Specification
Feed the Chaos programs work using two counters, the data counter and control counter, each of which is capable of storing an unbounded integer (negative values are allowed). The first two lines of the program specify initial values for the data counter and for the control counter respectively. The rest of the program consists of commands; as in brainfuck, unrecognised commands are ignored and can be used as comments.
The behaviour of most commands depends on whether or not the control counter is zero (\ is an exception, it does the same thing regardless of the control counter's value). Here's a list of what the commands do:
| Command | When the control counter is nonzero | When the control counter is zero |
|---|---|---|
+ |
Adds 1 to the data counter | Does nothing |
- |
Subtracts 1 from the data counter | Does nothing |
$ |
Does nothing | Halts the program |
/ |
Swaps the values of the data and control counters | Does nothing |
\ |
Swaps the values of the data and control counters | Swaps the values of the data and control counters |
The program is contained within an implicit infinite loop, and will run until a $ command causes it to halt.
Example
This example program simulates the bbchallenge:5-state busy beaver winner.
0 1 One program loop does one of the two following things: * If the control counter is not near zero, subtracts 3 from it and adds 5 to the data counter. * If the control counter is near zero, performs the following map: * control = 3: halt * control = 2: data counter increased by 9 * control = 1: data counter increased by 6 then sets the control counter to the data counter plus 1 and the data counter to 0. This emulates the rules of the 5 state 2 color Busy Beaver winner program (by storing the value of x plus 1 in one counter whenever the other is zero). + Ensure data counter is nonzero, so that we can change the control counter. \---\$\+++\ If control counter is 3, halt. ++++++/-/ If control counter was at least 1, increase data counter by 6. +++/-/ If control counter was at least 2, increase data counter by 3 more = 9. ----/-/ If control counter was at least 3, reduce data counter increase by 4 = 5. - If the control counter was large, undo the increase that ensured a nonzero data counter. (If it wasn't large, this will do nothing, effectively adding 1 to the data counter.) /\ If the control counter is now 0, swap it with the data counter.
Computational class
Assuming that at least one of the counters is maintained at a nonzero value (which is easy to ensure via adding an offset), Feed the Chaos is entirely capable of checking to see if one of the counters has a specific small value, and adding an offset to the other counter if it does. This makes it easy to construct state machines in Feed the Chaos.
However, a finite state machine + 1 counter is not Turing-complete, meaning that if Feed the Chaos is Turing-complete, it will also be necessary to use states where both of the counters are arbitrarily far from 0. In this situation, all the +-/\ commands will run unconditionally, and $ will do nothing, meaning that one iteration of the main loop will add some known offset to each counter (which is always the same), and optionally swap the counters. If the total number of / and \ is odd, this will swap the counters on every iteration, meaning that they will both increase or decrease by the same amount as each other every 2 iterations, which is not useful (if increasing, this is an infinite loop; if decreasing, there is no way to get both counters arbitrarily far from zero). However, if the total number is even, this will effectively multiply one counter by a rational number and add it to the other, which is a potentially useful operation.
As such, Feed the Chaos is basically a state machine that has access to one counter, plus the ability to multiply that counter by a given rational number (branching based on the remainder), but the rational number is always the same for any given program. This is equivalent to Collatz functions restricted so that the value of r in every case is the same.
While more powerful than a finite-state machine, these primitives don't obviously construct any way to store and retrieve arbitrary amounts of data. If r is an integer, then storing data is easy, but (because there is no remainder from the division) there is no way to retrieve it; and if r is less than 1, there is a limit on how much data can be stored. The interesting case is where r is a non-integer rational greater than 1 – in this case, the sequence of remainders acts like a pseudo-random number generator (in fact, it is quite reminiscent of an MRNG or LCRNG, although the amount of state it stores grows during program execution rather than remaining constant). It is currently unclear whether there is any way to store and subsequently retrieve data in this situation: the finite state machine can change the state of the pseudo-random number generator via adding and subtracting constants, which will have an effect on the pseudo-random numbers it generates later on, and thus have an effect on its later execution – and every adjustment made to the state will persist forever and affect the state machine infinitely many times, meaning that an arbitrary amount of data can be "stored" – but it is unclear whether it is possible to usefully read the resulting changes to the sequence, because it is hard to distinguish one sequence of pseudo-random numbers from another, especially using a state machine, and because the sequence is affected by all the data that was stored into it so far, not just the particular datum that the program might be trying to read. The language's author thus suspects that the language is not Turing-complete, but is not sure.
Interpreter
Here's a simple non-optimizing interpreter written in Perl:
#! /usr/bin/perl
use warnings;
use strict;
use Math::BigInt;
(my $data = Math::BigInt->new(scalar <>))->is_nan()
and die "Invalid data counter starting value";
(my $control = Math::BigInt->new(scalar <>))->is_nan()
and die "Invalid control counter starting value";
undef $/;
my $program = <>;
$program =~ s=[^+-/\\\$]==g;
OUTER: for(;;) {
print "$data $control\n";
for my $command (split '', $program) {
if (!$control->is_zero()) {
$command eq '+' and ++$data;
$command eq '-' and --$data;
$command eq '/' and ($data, $control) = ($control, $data);
} else {
$command eq '$' and last OUTER;
}
$command eq "\\" and ($data, $control) = ($control, $data);
}
}
print "$data $control (halted)\n";
Some optimizations are known that allow Feed the Chaos to be simulated in time quasilinear in the number of times a counter gets near zero (even though the counters grow exponentially in the process); there is a description at bbchallenge:Consistent Collatz. However, no existing interpreters implement that sort of optimization at present.