Talk:The Waterfall Model

Minsky machine construction

Expanding on your last section, I think that a Minsky machine implementation only needs:

• 1 clock per counter
  • Normal values in 2-increment steps starting at 2.
• 2 clocks per conditional decrement state (one for failing and one for succeeding decrement).
  • Failure clocks have default value 3, and success clocks default value 2.

In addition, an optional clock can be used for each state for ease of programming - these do only actions that can be inlined into their pre-triggering clocks. Default value 2.

The below uses both of the "adjustments can be negative" and "clocks trigger immediately when their value becomes the minimal one" conventions, which I find easier to think about since it allows keeping untouched clock values stable.

Triggers

Counter clock

Add 2 to self, subtract 2 from all failure clocks (bringing them to 1, except the one for the current state which becomes 0.)

Failure clock

Add 3 to self, 1 to the same state's success clock, 2 to all other failure clocks, subtract 2 from appropriate following state clock (or inline its trigger).

Success clock (triggers at value 1)

Add 1 to self and to the same state's failure clock, subtract 2 from appropriate following state clock (or inline its trigger).

Incrementing (or otherwise unconditional) state clock

Adjust appropriate counter clocks, add 2 to self, subtract 2 from next state clock. (Optional, can be inlined.)

Conditional decrement state clock

Subtract 2 from counter and 1 from this state's failure and success clocks, add 2 to self. (Optional, can be inlined.)

In the case where a counter has only one conditional decrement state, that state's failure clock can be inlined into the counter's trigger, essentially reducing to the construction you already gave. --Ørjan (talk) 05:53, 5 March 2018 (UTC)

Initial clock

The "waterclocks must not start with 0 as their current value" rule makes no sense. What you really need is for the minimal starting value to be unique, but then it may just as well be 0. --Ørjan (talk) 21:56, 11 March 2018 (UTC)

Never mind, I realized after waking up that it's for implementations that start out by decrementing all the clocks. I still think it's an inelegant restriction, though. --Ørjan (talk) 12:46, 12 March 2018 (UTC)

Right, this is intended to be as easy to implement as possible, so adding restrictions that can help implementations can only be helpful. (You could change the input encoding by incrementing the initial clocks, but that seems even less elegant.) --ais523 00:11, 13 March 2018 (UTC)

Undefined behavior

Out of curiosity, what is the motivation for saying that, when two waterclocks' current values hit 0 simultaneously, the behaviour is undefined? Since addition of zeroing triggers is commutative (so to speak), there's no race condition (so to speak), so there seems no reason not to simply apply all the zeroing triggers of all the waterclocks that hit zero, when multiple waterclocks hit zero. Have I missed something? --Chris Pressey (talk) 12:39, 14 June 2018 (UTC)

Eh, I just now noticed the "intended to be as easy to implement as possible" goal, and I would guess that is probably the reason. OK. --Chris Pressey (talk) 15:00, 14 June 2018 (UTC)

There are some TC proofs I'm working on via The Waterfall Model where the most natural construction leads to undefined behaviour in the case of simultaneous zeroing (and most simple The Waterfall Model interpreters would only apply one of the two zeroing triggers).

In a sense, you can think of The Waterfall Model as a cross between analog behaviour (steadily decreasing waterclocks; in an analog setting they'd be decreasing at a set rate rather than discretely), and digital behaviour (detecting when a waterclock hits zero, which is a sharp transition). In real life, digital behaviour needs a sharp cutoff, and things start going wrong when you have a "metastable" state which is very close to two contradictory cutoffs at the same time (as it's quite possible that either waterclock zeroing would increase the other, thus preventing it zeroing, and so you effectively have an "arbiter" whose purpose is to ensure that when two events happen nearly-simultaneously, one is clearly identified as having come first). The same phenomenon often occurs in real computer implementations, e.g. when comparing computable reals, the comparison always halts and gives the correct answer if they are in fact different, but if they're equal, the comparison goes into an infinite loop.

So I'd say it's not just a case of being easy to implement, but it's also making a statement about the world. If two things are different, you can normally demonstrate that they're different. If two things are the same, you'll never be certain that they're the same, because there might be some difference that you haven't noticed. In a way, integers are unnatural precisely because they're easy to compare for equality. So there is a concession to ease of implementation here, but it's in the choice of integers as the default number system, rather than in the behaviour on equality. --ais523 16:24, 14 June 2018 (UTC)

I see, thanks for the background. From the perspective of extending to other number systems (which is what I've been thinking about), it almost looks like it's anticipating being extended to an inexact number system, which would have race conditions (so to speak.) --Chris Pressey (talk) 21:01, 14 June 2018 (UTC)

Waterclocks over the reals

The article says this model "naturally extends" to waterclocks with real-number amounts of water, but is not clear if that means a model in which the "draining" of the clocks is still a discrete stepwise activity, or one in which it is a continuous activity. Or, to put it another way, waterclocks don't involve just one number (amount of water), but two numbers (amount of water, and time) - do both of these numbers naturally extend to other kinds of numbers? (This question is somewhat rhetorical. If anyone's thought about it, the article might benefit from those thoughts, that's all.) --Chris Pressey (talk) 12:51, 14 June 2018 (UTC)

(Oh, also, I don't see why "computable reals" specifically; I don't see why, offhand, both water-level and time couldn't just be reals. --Chris Pressey (talk) 12:54, 14 June 2018 (UTC))

They can be arbitrary reals, but that would be a language that in theory has very different computational power. It would effectively allow the machine to have a countable infinite number of advise bits embedded in the starting state of the program, and the program can access all those bits (although only with an exponentially decaying speed, but we don't care about runtime), and thus solve any non-computable word classification problem. We're interested in the vanilla Waterfall Model, with integer amounts of water, because it's Turing-complete but only exactly, not more powerful computationally. – b_jonas 13:52, 14 June 2018 (UTC)

OK, but I wasn't thinking of allowing uncomputable reals in the initial state (how would you write them in the program...?), only modelling the water levels as reals during runtime. Particularly in a continuous extension of the model, where time is also a real number. By the way, I'm not familiar with the term "advise bit" and it doesn't appear elsewhere on this wiki. I can guess what you mean though (probably), and it sounds plausible enough, but if you have an explanation of "advise bit" and a proof of your claim, it might make a nice addition to the article. --Chris Pressey (talk) 14:16, 14 June 2018 (UTC)

And actually, wouldn't even computable reals allow you to give the program a countable infinite number of "advise bits"? [If not, you probably mean something more by that term than what I'm guessing.] --Chris Pressey (talk) 14:40, 14 June 2018 (UTC)

No, I don't think so. Not countably many bits that you can choose arbitrarily at least. There are only countably many computable reals (as many as there are integers or rationals or algebraic numbers), so you can only store a finite (but unbounded) amount of information in one. And since the simulation using computable reals is computable, the whole machine can't be more powerful than a Turing machine. – b_jonas 14:59, 14 June 2018 (UTC)

True, it wouldn't make it more powerful than a Turing machine, but if, as you say, we're interested in this language because it's Turing-complete but only exactly, then we should be very wary about allowing entire computable reals (instead of just the finite TMs that generate them) to be embedded in the programs of the language, lest we accidentally give it a free ride (so to speak). --Chris Pressey (talk) 16:28, 14 June 2018 (UTC)

Uncomputable numbers are in general very difficult to compare with things (and doing so is effectively an oracle, e.g. being able to compare Chaitin's constant with arbitrary rationals allows you to solve the halting problem, as you can then brute-force programs until you've found all the ones that halt). So when you allow those, the language processing them effectively becomes irrelevant as the computational power is in the comparison itself. Now you've got me thinking about computable numbers that work as oracles to allow sub-TC systems to become TC. --ais523 16:30, 14 June 2018 (UTC)

There's a real that contains all execution traces of all TMs. Let's call it u. u is computable. Now suppose you have a language where programs consist of a number n and a list of instructions. I think you can pick the instructions so that, if n is an integer or rational, the language is not TC, but if n is allowed to be a computable real, then you can pick n=u and, applying those instructions to u, extract the execution trace of any given TM, in effect simulating it, in effect being TC. (Do let me know if you disagree.) (Part of me wonders if this is worth designing an esolang around. Fleshing out the construction in full detail would probably be pretty tedious.)--Chris Pressey (talk) 04:44, 17 December 2018 (UTC)

Now that you've mentioned the basic idea, it's pretty easy to construct a language with the desired property. An LBA plus one stack is not Turing-complete. Form the stack out of your number n via the normal stack/number correspondence (i.e. the stack operations are "halve n", "add 1 to n then halve it", and "double n, if the result is above 1, subtract 1 from n and go down an alternative code path"). The LBA has easily enough power to extract the execution trace from the digits of u (when n=u), but any rational n effectively just gives you a repeating pattern "below the bottom" of the stack, which is something the LBA could generate by itself, and thus doesn't add any computational power to the system. So we have a (powerful but sub-TC) language that becomes Turing-complete when we initialise n to this specific irrational (but computable) real. --ais523 23:57, 17 December 2018 (UTC)

Yeah. The construction that was forming in my mind was a little different but not hugely different (write the digits on n onto the tape of a TM that can only move the tape head rightward...) But the point is that we agree that such situations are possible, and, to bring it back to the topic of this talk page, does that mean we should be slightly concerned about allowing computable reals in the initial conditions of The Waterfall Model (lest there is some way for it to be TC by providing a water level like u instead of using The Waterfall Model's features to be TC)? If not, why not (i.e. how do we justify that confidence?) To be sure, I don't think this is a "serious" concern -- if the inputs were restricted to rationals I don't think that would detract from the spirit of the language, and otoh showing that there is no need to do so could be interesting/enlightening too. But it's interesting to think about.--Chris Pressey (talk) 12:04, 18 December 2018 (UTC)

The intention is that "the smallest waterclock runs out first and then gets processed"; at that point, the clocks all have the same relative value but the smallest is at 0. So it's definitely intended to conceptually be a continuous drain. --ais523 16:30, 14 June 2018 (UTC)

OK. My main concern in this section was about continuity. I agree that, for sanity's sake, we can avoid considering The Waterfall Model programs that specify arbitrary reals; I would in fact be happy for these values to continue to be integers. But if we think of the values varying continuously at runtime, I suspect there are advantages to thinking of them as varying over the reals, because (as I understand it - the actual mathematicians can put me in my place here) the reals are probably the most natural setting for considering questions of continuity. Yes, as they vary they will take on uncomputable values, but, that's just what reals do, there's not much sense trying to avoid it. Anyway, I don't think it causes any problems for the language, so long as all the numbers in all the zeroing triggers are computable. --Chris Pressey (talk) 21:25, 14 June 2018 (UTC)

Well, if all the numbers in the program are computable, then all the intermediate values at the time a zeroing trigger runs will be computable. I guess you can say that the program uses uncomputable values temporarily while the clocks are decreasing, but that's more a conceptual issue than anything that makes a difference for practical implementation purposes. --ais523 21:29, 14 June 2018 (UTC)

Yes, that "lemma" (your first sentence) is what I was thinking too. I had some more thoughts on this, but at some point I think I decided it would be simpler to just assemble my various thoughts into a design, so I made this: Your Pong May Minsky. --Chris Pressey (talk) 21:37, 16 June 2018 (UTC)

Truth-machine

This is my attempt at a Truth-machine:

[[7, 4, 4, 4, 4],
 [6, 1, 0, 0, 0],
 [4, 2, 2, 0, 2],
 [5, 2, 2, 2, 2],
 [{input * 2 + 3}, 0, 0, 0, 0]]

Second row is the 'output' clock, last row is the input. I'm not using the output extension, designating a single clock as output for a simple result seemed clear enough.

Using the recommended number encoding (2x + 3): 3 in the first cell of the last row represents 0, 5 is 1. On 3(=0), the output clock will be set to 3(=0) and the program will cleanly exit. On 5(=1), the output clock will alternate between 5(=1) and 4(NaN?) without terminating.

Given that the Waterfall Model can be implemented in many languages, I thought it would be nice to have some simple, moderately interesting examples to test with. Putting it here in the talk page for review -- if it is a suitable Truth-machine example (I had at least 3 false starts!) feel free to move it to the main page, if you want examples on the main page. It has been tested in the online interpreter and runs there as described. Salpynx (talk) 10:35, 19 December 2018 (UTC)

This is an interesting case, because truth-machines are designed to demonstrate I/O, and The Waterfall Model doesn't really have input. So a "full program" version of a truth-machine isn't available. This seems like a pretty close equivalent, a "function" version of a truth-machine (it's easy to see how it could be incorporated into surrounding code, with the output clock not having its zeroing trigger used, and the fourth clock being easily alterable by the rest of the program).

The issue then, of course, is how you define "output 1 forever" without interactive I/O (which a function doesn't have). Having the output value stay at the encoding of 1 is probably the closest you can get to that. So I guess this is as valid as we're going to get (unless we use the output extension to be able to do interactive rather than batch I/O). --ais523 08:04, 22 December 2018 (UTC)

The Truth-machine article itself has some suggestions for these cases. --Ørjan (talk) 16:27, 22 December 2018 (UTC)

Based on the suggestions there, I think this is a correct solution. --ais523 22:58, 23 December 2018 (UTC)

Relationship to Fractran

As mentioned on IRC, but here seems like a better place:

<ais523> incidentally, something I noticed recently: a program in The Waterfall Model with n non-halt waterclocks can be compiled into a FRACTRAN program with N+1 fractions
<ais523> the basic idea is to use a prime for each waterclock (including halting waterclocks), then multiply together all the primes but one in order to implement a zeroing trigger
<ais523> then if none of those fractions can run, a final fraction does the steady decrement
<ais523> halting waterclocks aren't given fractions, but are still given primes, so if one of them zeroes, none of the fractions can run because their prime is multiplied into every denominator

--ais523 10:28, 16 March 2020 (UTC)