Delta Relay

Delta Relay is an esoteric programming language that User:ais523 had been thinking about on and off since around 2018, but did not fully work out the details until 2024. The final version of the language was created as a result of two language ideas converging: one was to create a simplification/tarpitification of Flow of Holes via removing the distinction between primary and secondary connections (instead using the values of the counters to guide control flow), and the other was to create a language similar to The Waterfall Model, but where counters had a self-reset of 0 (which requires substantial changes to the language to function correctly).
== Semantics ==
A Delta Relay program stores information in a number of variables called "counters", each of which can store arbitrarily large nonnegative integers (and which have initial values specified by the program; the first counter must have an initial value of 0, with the other counters having positive initial values). In addition to the initial values, the program also specifies, for each ordered pair of counters, an integer (negative values allowed) that represents the influence that the first counter has on the second (and the first counter is said to influence the second if its influence on the second is nonzero: positively influence if the influence is positive and negatively influence if the influence is negative). Each counter always has zero influence on itself.
There is no explicit instruction pointer; however, the set of counters whose value is zero acts in a way that somewhat resembles an instruction pointer. Implementation proceeds by repeatedly picking a counter whose value is zero (the control counter), then increasing the value of each counter it influences by the amount of influence it has on that counter. (If the influence is a negative influence, this will reduce the value of that other counter, due to increasing it by a negative number.)
Sometimes, there may be two counters with value zero. In this case, the implementation may use any of the following algorithms to determine which zero-valued counter to pick:
* pick the counter that was not picked as the control counter last step; or
* pick the counter that positively influences the other counter; or
* pick the counter that became zero most recently; or
* pick the counter that would not influence a counter below zero.
In order to ensure that these algorithms all behave identically, Delta Relay programs must ensure that if they ever zero two counters simultaneously, one positively influences the other, and one negatively influences the other; to do otherwise is undefined behaviour. Undefined behaviour also occurs if influencing a counter below 0 (but see #Continuous Delta Relay below), or zeroing three counters simultaneously (but see #Three zeroed counters below).
A counter is considered to be a halt counter if all the counters it influences are influenced positively (with no negative influences). If such a counter is ever chosen as the control counter, the program halts (this situation would otherwise be a trivial infinite loop because there would be no way for any other counter to ever become zero). Likewise, the first counter must have only negative influences on other counters (with no positive influences).
== Syntax ==
A Delta Relay program consists of a 1-dimensional vector (listing the initial values of the counters) and a 2-dimensional matrix (listing the influence each counter has on each other counter: the value in the mth row and nth column indicates the influence that the mth counter has on the nth counter). The main diagonal of the influence matrix must be all zeroes, because a counter is not allowed to influence itself.
If a program is stored in a file, it uses JSON syntax: the initial values are represented as an array in JSON, and the influence matrix is an array of arrays (the inner arrays are the rows of the matrix, and the outer array is the matrix as a whole). The initial values are written first, followed by the influence matrix. Whitespace (horizontal, vertical, or both) is allowed but not required to appear at the start of the file, end of the file, and between the initial values and influence matrix.
== Reversibility ==
Delta Relay is reversible: given the state of the counters, it is always possible to uniquely reconstruct what happened on the previous execution step (assuming that it was not the start of the program. This can be accomplished simply by negating every element of the influence matrix, changing positive influences to negative influences of the same size, and vice versa. After simulating backwards to the start of the program, a halt is simulated.
== Extensions ==
=== Continuous Delta Relay ===
Although Delta Relay is specified in terms of integers, with influence applied in discrete steps, it is alternatively possible to interpret influence as being a sort of "rate of change", and the control-counter status being something that is relayed from one counter to another as the new control counter becomes zero. In this view, the undefined behaviour on sending a counter can be interpreted as "the changeover from one control counter to the next can only happen at integer times".
It is possible to lift this restriction, in effect causing the undefined behaviour to become defined. In this case, situations where a counter would be influenced below zero are handled by scaling down the influence matrix, e.g. if counter 4 (the control counter) influences counter 5 by +1 and counter 6 by -2, but counter 6 has a value of 1, this would be implemented by adding +½ to counter 5 and -1 to counter 6 (i.e. applying the maximum proportion of the influence that does not send a counter below zero).
This version of the language is mathematically neat (e.g. it is possible to multiply a row of the influence matrix by an arbitrary rational without changing the behaviour of the program) and probably the closest version to ais523's original vision for the language. However, it is substantially harder to implement (because the counters can become arbitrary rationals) and does not have obvious practical benefits, so this is not considered the "main" version of the language.
=== Three zeroed counters ===
Delta Relay programs become somewhat simpler to write if the language is extended to allow for three counters to be simultaneously zero, with a programmer-specified tiebreak on which of the counters should be considered the control counter in that case. However, the rules become even harder to specify correctly than the rules for two simultaneously zero counters, and it seems that there might be more than one potentially useful set of rules. It also becomes awkward to ensure that the language remains reversible in this case.
ais523 thinks that there may be potential here, but (at the time of writing) is not yet happy with any particular definition for the three-zeroed-counters case.
== Computational class ==
Delta Relay is Turing-complete, because it can implement Bouncy Counters with only one start side, and no restart after stopping (which is Turing-complete).
The basic idea is to represent each pair of counterpart sides with five counters, "start incrementing" and "finish incrementing" (which implement the + side), "start decrementing" and "finish decrementing" (which implement the - side), and "bounce" (which implements the bounce). Except while the Bouncy Counters program is executing either of the sides in question, most of these counters have value 2, but the "bounce" counter has value equal to 1 plus twice the value of the Bouncy Counters counter that the sides pertain to. For any side, define the next side as the RHS of the side definition with that side on the LHS, and the previous side as the LHS of the side definition with that side on the RHS. The influence is set up as follows:
* "start decrementing" negatively influences (-1) "finish decrementing" and (-1) "bounce"; and positively influences (+1) the "finish" of the previous side;
* "finish decrementing" negatively influences (-2) the "start" of the next side and (-2) the "bounce" of every other side pair that refers to the same counter (but not the "bounce" of this side pair); and positively influences (+2) "start decrementing";
* "start incrementing" negatively influences (-2) "finish incrementing"; and positively influences (+2) the "finish" of the previous side and (+2) the "bounce" of every other side pair that refers to the same counter (but not the "bounce" of this side pair);
* "finish incrementing" negatively influences (-1) the "start" of the next side; and positively influences (+1) "start incrementing" and (+1) "bounce";
* "bounce" negatively influences (-1) "start" of the next side after the + side, (-1) "start incrementing", (-2) "finish incrementing"; and positively influences (+1) "finish" of the previous side before the - side, (+1) "stop decrementing", (+2) "start decrementing".
Here's what happens in each of the three possible cases (where "before" refers to the "finish" of the previous side, and "after" refers to the "start" of the next side):
beforeincrementing 	startincrementing 	finishincrementing 	afterincrementing 	bounce 	beforedecrementing 	startdecrementing 	finishdecrementing 	afterdecrementing 	otherbounces
Increment 	Increment 	Increment 	Increment 	Increment 	Increment 	Increment 	Increment 	Increment 	Increment
0 	0 	2 	2 	2n+1 	2 	2 	2 	2 	2n+1
2 	0 	0 	2 	2n+1 	2 	2 	2 	2 	2n+3
2 	1 	0 	1 	2n+2 	2 	2 	2 	2 	2n+3
2 	2 	0 	0 	2n+3 	2 	2 	2 	2 	2n+3
Bounce 	Bounce 	Bounce 	Bounce 	Bounce 	Bounce 	Bounce 	Bounce 	Bounce 	Bounce
2 	2 	2 	2 	1 	0 	0 	2 	2 	1
2 	2 	2 	2 	0 	1 	0 	1 	2 	1
2 	1 	0 	1 	0 	2 	2 	2 	2 	1
2 	2 	0 	0 	1 	2 	2 	2 	2 	1
Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)	Decrement (non-bounced)
2 	2 	2 	2 	2n+3 	0 	0 	2 	2 	2n+3
2 	2 	2 	2 	2n+2 	1 	0 	1 	2 	2n+3
2 	2 	2 	2 	2n+1 	2 	0 	0 	2 	2n+3
2 	2 	2 	2 	2n+1 	2 	2 	0 	0 	2n+1
This behaviour exactly matches that of Bouncy Counters, so the only remaining problem is to show that program starting and halting can also be made to correspond. For start and stop sides, there is no counterpart (by definition), so the above construction does not explain what to do for the counters "after" and "before" the counterpart. This problem can easily be fixed by adding extra otherwise unused counters to serve as the after and before counters; the dummy "before" counters negatively influence (-2) the appropriate "start" counter (and no other counters), and the dummy "after" counters positively influence (+2) the appropriate "finish" counter (and no other counters). This makes the dummy "after" counters into halt counters, by definition, causing Delta Relay's halt state to match Bouncy Counters's. The first counter of the whole construction should be the "before" of the lone start side's counterpart; this has only negative influences (as required for the first counter), and will start by simulating a bounce onto the start side, which is the correct startup state for Bouncy Counters.
== See also ==
* Flow of Holes
* The Waterfall Model
Category:LanguagesCategory:2024Category:Reversible computingCategory:Turing completeCategory:Turing tarpitsCategory:No IOCategory:UnimplementedCategory:Low-level