Flooding Waterfall Model

From Esolang
Jump to navigation Jump to search

Flooding Waterfall Model is a modification of The Waterfall Model, first observed by Deedlit11 and with a name coined by User:FortyTwo. It was inspired by an attempt to implement a Turing-complete language in Magic: the Gathering: the existing constructions for implementing The Waterfall Model make use of the card "Dralnu's Crusade", but there are reasons to want a Turing-completeness construction that does not require that card, and if it is removed, the constructions for implementing The Waterfall Model end up implementing Flooding Waterfall Model instead.

The primary difference between the original language and its flooding version is that when a flooding waterclock zeroes, instead of its zeroing trigger running once, it runs a number of times equal to the number of cycles since the waterclock was last zero.

Semantics

A Flooding Waterfall Model program consists of a number of waterclocks. Each waterclock has a zeroing trigger, which is a map from waterclocks to integers (i.e. for each waterclock, there is an integer that specifies that waterclock's relationship to each other waterclock); the zeroing triggers stay unchanged for the duration of the program. A running program also stores some numbers that represent the current state of each waterclock, and which vary over the lifetime of the program: each waterclock has an age and a value, which are both non-negative integers that could be arbitrarily large.

Program execution consists of alternating between the following two steps:

Steady decrement
For each waterclock whose value is not zero, that waterclock's age is increased and its value is decreased. (The age and value of waterclocks with zero value remain unchanged.)
Zeroing trigger
For each waterclock X whose value fell from 1 to 0 in the previous step, the value of each waterclock Y is increased by (the value Y is mapped to by X's zeroing trigger) × (X's age). Then the ages of all such waterclocks X are reset to 0.

(Note that a side effect of these rules is that a waterclock that has zero value will, except while its zeroing trigger is being processed, also have zero age.)

Unlike with The Waterfall Model, it is not undefined behaviour for two or more waterclocks to zero as a consequence of the same steady decrement; rather, all of their zeroing triggers run simultaneously. (This undefined behaviour is trivial to avoid in The Waterfall Model by multiplying all values and zeroing triggers by a constant and then using small changes to values to break the tie, but the same solution does not work for Flooding Waterfall Model, and it is much simpler to define the case explicitly.)

Another case that is undefined in The Waterfall Model but defined in Flooding Waterfall Model is the case of a waterclock's value remaining at zero for multiple consecutive cycles: in Flooding Waterfall Model, the waterclock's age will remain at zero in that situation, and thus its zeroing trigger will do nothing (because it is multiplied by zero).

Unlike with The Waterfall Model, implementations may well not be able to handle all possible age/value combinations at program startup. Implementations must be able to start up in a state where all the waterclocks have arbitrary specified values (including states where some of those values are 0), but need not be able to handle nonzero ages.

Halting is handled using a halt waterclock, designated by the program; if the value of this waterclock ever falls to 0, the program exits. (The age of the halt waterclock conceptually exists, but is irrelevant.) A waterclock is generally specified to an interpreter as being a halt waterclock via specifying an all-zero zeroing trigger, which is not otherwise useful.

Implementation in Magic: the Gathering

jfb1337 and FortyTwo discovered that Flooding Waterfall Model can be implemented in Magic: the Gathering using the following three components, producing an extremely simple construction to prove Magic Turing-complete:

  1. "Coat of Arms", a card which gives each creature +1 toughness (also +1 power, but that is not relevant to the proof) for each other creature with the same creature type;
  2. A sufficiently large number of permanents with triggered abilities that create a token creature of a specified creature type whenever a creature of a different specified creature type dies (e.g. many token copies of "Bishop of Wings", with "Artificial Evolution" used to change which creature types are listed in its text box and thus to allow the creature types to be specified);
  3. Something that repeatedly damages all creatures until a particular creature dies (typically "Arcbond" plus something that causes it to repeat, such as "Comeuppance" or a second copy of "Arcbond")

The implementation is pretty much direct. Each creature type represents a waterclock, with the waterclock's age being the maximum amount of damage marked on any creature with that type, and its value being the number of creatures of that type minus its age (which, due to 1. above, is also equal to the toughness of the creatures of that type minus the maximum damage marked on any of those creatures, i.e. the minimum amount of remaining toughness that any of the creatures have). 2. handles the zeroing triggers (which run for each creature that died, i.e. a number of times equal to the age + value, which is a number of times equal to the age because the value is 0), and 3. handles the steady decrement. Halting is handled by causing the "particular creature" in 3. to be a creature whose type is the halt waterclock.

As long as the implementation is set up in such a way that the triggers from 3. always go on the stack below the triggers from 2. (which in Magic can be done by choosing the controllers of the various cards in question: effects controlled by the active player go on lower positions than effects controlled by the inactive player), this particular Turing-completeness construction has no choices that can usefully be made by any player, and will run to completion (or run forever) automatically. This makes it useful for busy beaver constructions. In particular, it is useful for "largest non-infinite combo in Magic" challenges, when the size of a combo is measured in terms of, e.g., how far the opponent's life total is sent below 0; although Flooding Waterfall Model can of course construct an infinite loop, non-halting programs give no way to progress with the game and thus the infinite loop does not form a valid combo by this sort of definition, meaning that only the non-infinite loops count.

Computational class

Flooding Waterfall Model is Turing complete (and this has been proven via construction of an explicit compiler from The Waterfall Model; see #External resources below).

There are two key observations:

  • The most intuitive way to think about the flooding waterclocks, in terms of programming in Flooding Waterfall Model, is in terms of their velocity and position:
    • The velocity is the multiplier that will be applied to their zeroing trigger, i.e. the total amount it has been incremented by since it was last zero. This is equal to the waterclock's value plus its age.
    • The position is the moment in time at which the waterclock was last zero, i.e. a point in time that happened a number of steady-decrements ago equal to the waterclock's age. However, instead of thinking of the position relative to the current time, it is generally more intuitive to think about a few fixed moments in time and think about positions relative to those.
  • It is possible to design a construction in which the waterclocks are divided into two clusters, such that if any waterclock becomes zero, all the waterclocks in its own cluster will become zero before any waterclocks in the other cluster do (and will remain at zero when the first waterclock in the other cluster becomes zero). If the waterclocks zero in any such order, the positions will have no effect on the velocities: the velocities in the second cluster will depend purely on the velocities in the first, not on the positions nor on the sequence in which the waterclocks became zero. (This is because a flooding zeroing trigger is effectively of the form "one waterclock A velocity becomes x waterclock B velocity, plus y waterclock C velocity, etc.", which is entirely linear, so the velocities in the second cluster can be determined as a linear combination of the velocities in the first cluster.)

The basic idea is to measure velocities with respect to a "baseline" bc, where b is a sufficiently large fixed constant, and c is the number of times execution has gone back and forth between one cluster and the other. The relative velocity of each nonzero flooding waterclock against the baseline can be made to form a fixed cycle, via maintaining "baseline waterclocks" which are at fixed distances from the baseline, or that follow a very simple pattern (e.g. +1 compared to the baseline for 1 cycle, followed by being +0 compared to the baseline for n cycles). Because the velocities do not depend on the positions, the velocities that would be caused by any given zeroing trigger can be predicted and compensated for, meaning that the baseline waterclocks can effectively force the baseline-relative velocities of every waterclock in the construction to follow a fixed repeating pattern, and it is possible for the programmer to choose what that pattern is.

It is then possible to emulate the values of waterclocks from the program being compiled by using the positions (rather than values) of the program being compiled into. When a flooding waterclock zeroes, it will grant its position plus velocity as a new position for any waterclocks that change from zero to nonzero due to its zeroing trigger, but the positions of other waterclocks will remain unchanged (even if they were affected). If you have two waterclocks with the same position but different velocities (the "same position" is easy to arrange by having them be affected by the same zeroing triggers, and the velocities can be set in any arbitrary repeating cycle), and they both affect the same waterclock, then the waterclock with the smaller velocity will normally set the position of the affected waterclock (because it zeroes first). However, if another waterclock in the same cluster zeroes earlier and adds to the smaller-velocity waterclock, then the waterclock with the larger velocity will set the position of the affected waterclock instead. This effectively lets you write code that does the calculation if (w < x) { y = x + b; } else { y = x + a; }, which is sufficient computational power to implement The Waterfall Model.

Although this construction needs velocities and positions to be set carefully in order to work, and doesn't "naturally" start in a state where all waterclocks have the same position (which is how Flooding Waterfall Model programs are required to start up), this is easy to work around using "startup waterclocks" which start at a given value, zero once, and are never incremented by anything; a counter can then be initialised to arbitrary position and velocity (as long as the position is less than half the velocity) by using two startup waterclocks, a smaller one to set the position and a larger one to top up the velocity once the position has been set. (The easy case is when the position is greater than one third of the velocity, in which case you can use a 1 in both zeroing triggers and the second startup waterclock will top up the counter before the water it gained from the first startup waterclock runs out. If the desired position is smaller, it is still possible to make startup work, via increasing the number in the first zeroing trigger, but this situation is more complex and avoided by the compiler linked below.)

See also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Flooding_Waterfall_Model&oldid=123839"