Concerning something FortyTwo mentioned earlier, about undefined behavior: While some states in The Waterfall Model can have undefined behavior, it is still considered Turing-complete. I assume that this means that we can model all Turing machines, using setups that never lead to undefined behavior. Is this correct? In that case, we can handle the undefined behavior however we choose, so long as those situations don't invalidate the deck, i.e. lead to being able to send the opponent to arbitrarily low life. So long as we can still model any Turing machine without those situations, we would still achieve Busy Beaver.
Edit: Going back to the [c}Chalice of the Void[/c] deck, we can do one card better by not making the K'rrik change, and just producing black mana with Llanowar Dead:
Yes that is correct, it it kind of akin to dividing by zero, or a race condition. Except this has a clear ideal solution: Resolve all of the triggered operations before continuing operation. In this machine that would be: remake all of the creatures, then pump everything to the right sizes, then continue.
That is why I'm trying to force the opponent to have all of the rotlungs, so that all of those death triggers resolve first and it doesn't matter what order they are in. Making a bear and an ape is the same as making an ape and a bear. Same with pumping all apes then pumping all bears. and vice versa,
The problem is that if we can create a bear and pump all apes then create an ape and pump all bears. The new ape did not get pumped.
It is more clear if we have a Kazuul Warlord type card (would need to be mandatory)
Then normal operation would be arcbond damages things,
Rotlung triggers and remakes whatever dies
Kazuul warlords trigger and make everything the right sizes.
Arcbond continues to trigger.
But, if two things die at the same time we can choose how to order things and the second token would not be pumped by the first token. We would want both tokens to be bigg
Yeah, I can see that we do not want to have any choices, since that can affect when or if the computation halts. This looks like a very difficult problem.
Edit: No, the last change doesn't work, since the deck still has Verdant Succession. So we can't use green creatures as stage creatures. How hard is it to remove Verdant Succession from the proceedings? I think we could use Assembly Hall, but that would require another copy of Centaur Safeguard, and also Child of Alara I think, and there's not enough space in the deck for that.
So, to put a cap on the waterfall TM discussion we would be unblocked by either of the following two things:
1) A way to ensure that the opponent is the only one to have any of the Rotlung Reanimators, and none of the hungry lynxes. That way the triggers are forced to be in the order we want.
2) An alternative way to boost toughness, the timing on this is very tricky. It needs to be forced to resolve after(before works too but seems harder) all of the rotlungs, and before the next arcbond trigger.
1 looks like a dead end for now.
2 looks very tricky as well, I'm not even sure what could fit in a spot like that. Something like Bramblewood paragon works for remaking the token at the right size, but I don't see anything like that that could work for the rest of our creatures. Maybe a Coat of Arms style effect?
So, instead of Bramblewood Paragon putting a +1/+1 counter on a token coming into play, you would like all creatures to gain toughness? What about Cathars' Crusade?
Cathar's crusade is too generic, (and tiggers at the wrong time).
We want to be able to increase one creatures toughness by +X and another's by +Y etc.
Coat of Arms is kind of the right effect, but requires the total number of creatures to increase (and decrease?), which seems difficult to manage properly.
Edit:
Hmm, we might be able to implement a type of cyclic tag system with Coat of Arms and strictly increasing the number of creatures. I'm not sure what exactly we'd be able to implement here, but it might be worth looking into.
The idea is that we would have an extra set of rotlung reanimators making tokens that are indestructable thanks to something like Timber protector, with some Dralnu's crusades giving things the multiple types we'd need.
Actually halting is a problem, we'd need to set it up so that the arcbond creature only dies under some special circumstance.
I don't know that much about Turing-complete langauges, but I do remember that a particularly simple system was counter machines.
There is a Turing-complete version of counter machines that uses just two counters and two types of instructions. However, the intructions can jump to arbitrary instructions in the program, so that might be hard to implement with Magic.
Looking at cyclic tag systems, that might be better suited to Magic. Cylic tag systems involve a sequence of productions, which are binary words, and a data word. So we need to be able to encode a sequence of binary words. One particularly simple Turing-complete version of cyclic tag systems are binary cyclic tag systems. BCTs have a command word and a data word, so only two binary words, but we still need to implement them as distinct structures.
First off, how are we going to implement binary words? We need to order our battlefield somehow. One way to do that is by increasing order of power or toughness. So, we could implement a binary word by existence of a creature of toughness - damage equal to n meaning the nth digit is a 1 while the lack of existence indicates that the nth digit is a 0. So for example, 01011101 would mean there are creatures of toughness - damage equal to 2,4,5,6, and 8, but none of any other values. To get both a command word and a data word, we could have two different creatures or creature types. Then, decrementing would appear straightforward, we deal 1 damage or give a -1/-1 counter to all appropriate creatures. However, appending words would appear to be difficult; we would have to add creatures of toughness of various levels greater than the max toughness. Coat of Arms wouldn't quite work here, since the number of creatures isn't necessarily tied to the length of the data word.
Perhaps reverse the order, and have increasing toughness - damage represent the data word from right to left? Then, we can append words by creating a token and triggering Cathars' Crusade when want to append a 1, and just adding +1/+1 to all appropriate creatures when we want to add a 0. Decrementing then becomes destroying the creature of greatest power or toughness - I seem to recall that there were cards like that.
Hmm, but then there's the command word. This is actually a cyclic word, so I'm not really sure how we should implement it. Evidently BCT's are Turing-complete even if the data word is just a 1, but then the command words would need to be allowed to be arbitrarily long. So we would need a construction of unlimited size, meaning we would have to use something indexed by numbers, i.e. toughness, power, or number of counters. But it would also have to operate cyclically, which seems very tricky.
It would be nice if BCT's were also Turing-complete using some restricted set of command words, but arbitrarily large data words. That would be worth finding out for sure.
Having said all this, I'm not sure how Coat of Arms would fit in here.
Edit: I just noticed that "destroy creature of greatest power/toughness" will not eliminate the rightmost digit, it will eliminate the rightmost digits up to the next 1, and the subsequent string of 0's. So rather than have 1 indicate existence and 0 indicate nonexistence, we will need to have 0 and 1 indicate different creatures or types of creatures of the appropriate toughness. So now, desroying a creature of the greatest power toughness will successfully decrement.
Examining the commands further, the appending command is actually executed if and only if the leftmost data bit is 1. So we need something to be executed or not executed depending on the creature or type of creature of the lower/highest power/toughness. That could be hard as well.
It is too early to celebrate now, but I think I may have cracked the waterfall implementation with Coat of Arms + Dralnu's Crusade. One issue is that this method eats up our creature type namespace twice as fast, but we should still be able to implement a UTM in that size?
The key insight was using extra creature types to link with the Dralnu's Crusades. This allows the coat of arms type be different than the Rotlung reanimator trigger type. Letting the Rotlungs do the work of both pumping other registers, and remaking the current one. In a way that doesn't depend on the order the triggers resolve.
We do need to switch to 1/1 tokens to make the math easy but that's easy with Bishop of wings (though gaining that much life is unfortunate)
Setup, we have Dralnu's Crusades on "all As are a*s", "all Bs are b*s", etc. And a bunch of bishops that trigger on an X dying and make a y*. And one Bishop each of remaking the Main types.
OPERATION:
Arcbond trigger resolves dealing 1 damage to everything, and triggering arcbond.
When the 'Main' creature for row N dies, first Coat of arms causes a chain reaction and kills any supporting N* tokens.
Then the various Bishops trigger from an N dying. One remakes the N, then others make the supporting tokens for all of the rows in accordance with the "program", (making a*s, b*s etc), Making all of those tokens be 1/1 base forces that when the Main type dies, all of the tokens of the linked type die as well, truly Zeroing out the register so that we can be confident in the number we now have in there.
HALTING:
We can then set it up to have our Arcbond-ed creatures be creature type X
We keep them alive by occasionally making more creatures of type X
Note that the arcbonded creatures themselves take damage at half the rate everything else does however their supporting X tokens still take full damage and any of them dying causes a chain reaction that results in the originals dying.
As a demo/Proof of Concept I'll encode the last example program from the waterfall tutorial page linked earlier.
Setup: only 6 rows so the initial Dralnu's Crusades get set to
All Apes are Atogs
All Bats are Bees All Cats are Crabs -- This is the halting row so nothing is needed here
All Drakes are Druids
All Eggs are Eyes
All Fish are Foxes
The first collumn is just our initial state, so we have:
2 Atogs (one is an ape atog)
3 Bees (one is a bat bee)
3 Cats (with arcbond on two of them)
11 Druids (one is a Drake Druid)
7 Eyes (one is an Egg Eye)
3 Foxes (one is a Fox Fish)
Then each row tells us how much of the other things to make via bishops when triggered
Taking just the last row as an example
Whenever a fish dies: create 2 atogs, 3 bees, 1 cat, 2 eyes, 3 foxes and a fish.
Then we ping a cat and are off to the races.
This operation seems to be completely free of meaningful choice, ordering the death triggers does not matter here.
I think I need a sanity check here? Is there some problem that I missed?
Hmm, very nice! Yeah, there doesn't seem to be a way to meaningfully change how the sequence of play goes, once the Waterfall Model starts executing.
Of course, the issue of whether the number of variables we can implement (it looks like there are 249 creature types so I think we can implement at most 124 variables?) is enough for Turing-completeness is a critical one. I don't think we can necessarily say that some UTM will correspond to some Waterfall setup (I'm calling a "Waterfall setup" to be some number of variables and the set of zeroing triggers for each variable), because the fact that the Waterfall model is Turing-complete doesn't necessarily imply that each Turing machine corresponds to one Waterfall setup; we could have a single Turing machine with different inputs correspond to different Waterfall setups (with various inputs), so a single UTM could potentially require an unbounded number of variables. Which would kibosh the whole idea of using The Waterfall Model for Turing-completeness, at least in terms of having creature types for variables. This might not be the case, but if not, we still need to find the number of variables required for Turing-completeness.
There are some creatures that we probably need to keep around (our various Rotlung Reanimators, for example), and they will have various creature types. We don't want these types to be set as Coat of Arms types, as then we will have unwanted pumps to our variable numbers. But perhaps these types being set to Rotlung Reanimator types will be okay? That looks fine, so we should be able to get the full 124 possible variables I think.
Another issue: Sure, once the Waterfall Model is fully set up, and the execution is started, maybe we will have no ways to affect the sequence of play (provided the rest of the deck doesn't provide us with any way to interrupt the execution), but for any point up until that execution starts, we have to be wary of possible infinities. With unlimited usage of Artificial Evolution, the threat of such infinities is very real.
But anyway, this looks like a major step forward - kudos!
Edit: Hmm no, I don't think we can set the creature types from our necessary creatures to be Rotlung Reanimator types either, since Dralnu's Crusade will turn these into Coat of Arms types. So, the maximum of number of variables will be some number less than 124, depending on however many creature types there are of creatures that we need to have on the battlefield during the execution of the computational model.
Yeah the namespace is a problem, How does BB(100) compare to our current estimates?
I have no clue how much space we need for a UTM. But that is a good point about how we don't actually have more variables for inputting an arbitrary Turing Machine. I also don't know if being able to handle two things zeroing at the same time lets us do anything fancy.
Creatures we need to keep around can be Artificial Evolutioned into some out of the way type-Zubera and we can set timber protector to give them indestructible.
I don't think our ability to diverge from setting up a 'normal' Waterfall Program is a problem?
And yeah we need to be just as careful of infinites as before.
Edit: and we can go back to Rotlung Reanimator by simply having a second coat of arms and doing 2 damage initially, freeing up life.
If by BB(100) you mean the maximum productivity of a 100 state, 2 symbol Turing machine, that number is enormous. It has been shown that BB(85) > F_{epsilon_0} (1907), where epsilon_0 = w^w^w^w..., so yeah, such numbers are completely out of reach of our current methods. And I believe even that bound is a tremendous underestimate.
The problem is that we aren't implementing Turing machines, we're implementing the Waterfall Model, for which the amount of work done in programming fast growing-functions is probably 0. So, we could guess that, once we got confirmation that the Waterfall Model is Turing-complete with the number of variables that we have available, that with a googolplex mana available for construction, we could implement all 100-state Turing machines. But even though this seems very likely, we wouldn't know for sure, unless we did some actual Waterfall Model programming and implemented a Turing machine interpreter. I imagine that would be quite a task!
Perhaps it would be easier to just try to program large numbers directly into the Waterfall Model. This might not be an easy task either though, if the Waterfall Model is very difficult to program in, which looks like it could well be the case.
Hmmm, Artificial Evolution only affects card text, not creature type. But perhaps you mean combining Artificial Evolution with a card that sets creature type? I couldn't find any suitable cards though - the cards I find either added creature types on top of existing creature types (which wouldn't solve the Coat of Arms problem), or removed all abilities from the creature, which is no good. But, I probably missed some cards.
I do think diverging from the correct setup could very well be a problem, but we can talk more about this once we have a prospective deck.
Ok, yeah the BB function is ridiculous, (How is BB(5) still not known for sure??)
I don't want to get too far into the weeds optimizing the waterfall program, especially as there will probably be more creature types added.
But knowing the approximate ratio we can encode will be nice. But probably we can encode all n-state Turing Machines for some n that may be a function of the total number of creature types.
And as for putting large numbers in directly, I'm not sure how effective that would be...?
Also Artificial evolution does change types:
"10/4/2004 Alters all occurrences of the chosen word in the text box and the type line of the given card."
I don't think that there will be a nice ratio of number of creature types of number of states of a Turing Machine. Rather, if the number of creature types is large enough to support a Turing-complete computational model, then we will be able to encode all n-state Turing machines, where n is a function of how much setup we can do. But, if the number of creature types isn't enough to support a Turing-complete computational model, then the complexity class of our computational model will be very restricted, and we won't necessarily be able to encode even a 4 or 5-state Turing machines. I don't know for sure in this case of course, but it appears that generally when a computational model fails to be Turing-complete, it fails by quite a large margin. For example, if we have a simple BASIC-type programming language with increment, decrement, setting one variable equal to another, and WHILE loops, this programming language is Turing-complete, and the Busy Beaver function for it outgrows all computable functions, just like the normal Busy Beaver function. However, if we replace WHILE loops with FOR loops, the language becomes primitive recursive, so the Busy Beaver function for it will actually grow like the Ackermann function. Quite a drop off! It has been shown that even 4 or 5 state Turing machines can implement Collatz-like procedures, and I don't think we can implement those with a primitive recursive language, so we could top out at even something like 3 states if we fail to get Turing-completeness.
In order to get an actual lower bound for our deck, I don't see how we could do it other than to write a program to compute large numbers directly, or write an interpreter for a different computational model/language, and then program a large number in that other computational model. So it's not a matter of effectiveness but necessity. I suppose in the end we might just give up on this, and present a deck that in all likelihood generates a great big ginormous number, but we don't have any good lower bounds for it.
I'm pretty sure that a size 124 machine is more than enough to encode a UTM, But it might only be able to "input" Turing machines via additional states, and possibly not at a 1-1 ratio, so our limit would be BB((124-UTM)/Ratio)
For instance if every TM instruction requires its own waterclock (seems likely to me), The ratio would be 2 for a binary TM, and if the UTM takes 40 clocks to implement, that gives us BB((124-40)/2)=BB(42)
Some way to make ~124 copies of the crusade
Some way to make as many Rotlung Reanimators as possible.
Some way to deal 2 damage to a creature.
Some way to make a second Coat of arms.
Some way to spread Artificial Evolution to a bunch of creatures.
Some way to give our opponent a copy of Runed Halo
We have no assurance of that though; this is something we really need to check out.
Edit: Hmm, does the fact that the Rotlung Reanimator tokens come in higher break the Waterfall Model? We would have tokens come in at 3/3, so that would basically mean our zero triggers could not increment by one or two. Would we still have universality? Actually, for any Waterfall setup, we can mimic it with a the same Waterfall setup, but with the zero triggers all having their increments multiplied by 3. Then this new Waterfall setup would have the same execution sequence as the former setup, except it takes three times as many clock ticks to complete. So yes, I believe we would still be able to implement the same computations even if the tokens started at 3/3, so we can stick with Rotlung Reanimators and save life for later. Do you agree with this argument?
I don't think we even need more Coat of Arms though, we still get the same expressive power even if the tokens start off higher than the further minimal increments.
Edit: So, I've been thinking about how to not be able to do anything to interrupt the operation of the Waterfall Model computation, and it seems quite restricting. We can avoid cards like Leyline of Anticipation to not be able to casts sorceries, but Arcbond and Artificial Evolution are both instants. Now, both of those require mana and we lose the card from our hand, so either of those could prevent us from reusing them. But, if we have a way to get them back from the graveyard, either for setup purposes or for iterating this thing further, then we are in danger of being able to cast them, bring them back, and save enough mana in order to cast them during the execution of the Waterfall Model. So, that's very dangerous. One solution of course is to not be able get cards back from the graveyard, or instants anyway. That could definitely restrict our ability to iterate either the WM computation, or even just a starting combo to build up our resources for the WM computation.
Yeah, we don't really need a second coat of arms, just that if the initial size was a problem it would be easy to use that to make the mapping onto a TM more clear.
We need to use Bishop of wings anyway due to Rotlung reanimator itself being a zombie cleric, so we can't hide them in a useless creature type.
Do we need to hide them in a useless creature type? It's okay of tokens come in at higher toughness, and we can save the Rotlung Reanimators from being killed in various ways, for example making them indestructible using Soul of New Phyrexia.
It is not clear to me if it OK for them to come in bigger, as they need to die at a very scheduled rate and order, and the Rotlungs are not evenly spread across the types.
Yeah, maybe it doesn't work out quite right. Anyway, I suppose it is looking like it will be very difficult to add layers or stages to this, so perhaps mooting life is not the worst thing.
It would be some setup for it, we need Copy Enchantment and... I guess just creature copiers, which we need anyway? So not that much more.
Edit: Good news! So, it looks like The Waterfall Model can be emulated by Minsky machines fairly efficiently. I got a friend to help me find the minimum number of variables needed to encode a universal Minsky machine, but it doesn't look like it will be that many, as in less than 50. So with just 50 variables (presumably), we get a Busy Beaver-like function based on the amount of setup that we can do. So we don't need to try to hard to get to 124 variables, once we already have Turing-completeness. So we don't necessarily need to have something like Timber Protector so that we can reuse the card types of necessary creatures. On the other hand, if there's not much in the way we can do in terms of iteration, then maybe we might as well use them to increase the variable count.
As for actually programming in TWM, it does not look easy at all, but I think some unsolved problems seem easy enough to iterate through, that we could get Goldbach's conjecture or something to fit in.
Edit:
That is great news indeed, so we definitely have the TM improvement we were searching for, and the extra variables can be just for additonal computation.
Unsolved problems don't seem to be helpful. For example, if Goldbach's conjecture is true, a program that tries to find a counterexample will never halt, so it doesn't give us a score. If it is false, we only know that a counterexample is at least about 10^18.
Private Mod Note
():
Rollback Post to RevisionRollBack
To post a comment, please login or register a new account.
Edit: Going back to the [c}Chalice of the Void[/c] deck, we can do one card better by not making the K'rrik change, and just producing black mana with Llanowar Dead:
2 Psychic Battle
3 Cowardice
4 Horobi, Death's Wail
5 Bloodbond March
6 Chalice of the Void
7 Mimic Vat
8 Omniscience
9 Vedalken Orrery
10 Mirror of Fate
11 Karn, Silver Golem
12 Brain Freeze
13 Allay
14 Skull of Orm
15 Mirrorworks
16 Mana Vault
17 Eye of Ramos
18 Clockwork Gnomes
19 Goryo's Vengeance
20 Muzzio, Visionary Architect
21 Hurkyl's Recall
22 Goblin Dark-Dwellers
23 Changeling Hero
24 Anaba Ancestor
25 Engineered Explosives
26 Wheel of Sun and Moon
28 Acorn Harvest
29 Smite the Monstrous
30 Child of Alara
31 Centaur Safeguard
32 Verdant Succession
33 Select for Inspection
34 Spellweaver Helix
35 Worldfire
36 Worldfire
37 Spider Spawning
38 Spider Spawning
39 Titania, Protector of Argoth
40 Multani's Decree
41 Bayou
42 Eureka
43 Mox Emerald
44 Llanowar Dead
45 Everglove Courier
46 Grassland Crusader
48 Frightshroud Courier
49 Havengul Runebinder
50 Ghosthelm Courier
51 Devout Chaplain
52 Simian Spirit Guide
53 Goblin Kites
54 Old Man of the Sea
55 Sea Snidd
56 Reign of Chaos
57 Xathrid Gorgon
58 Tribal Unity
59 Consecrated Sphinx
60 Sphinx of Enlightenment
That is why I'm trying to force the opponent to have all of the rotlungs, so that all of those death triggers resolve first and it doesn't matter what order they are in. Making a bear and an ape is the same as making an ape and a bear. Same with pumping all apes then pumping all bears. and vice versa,
The problem is that if we can create a bear and pump all apes then create an ape and pump all bears. The new ape did not get pumped.
It is more clear if we have a Kazuul Warlord type card (would need to be mandatory)
Then normal operation would be arcbond damages things,
Rotlung triggers and remakes whatever dies
Kazuul warlords trigger and make everything the right sizes.
Arcbond continues to trigger.
But, if two things die at the same time we can choose how to order things and the second token would not be pumped by the first token. We would want both tokens to be bigg
Edit: No, the last change doesn't work, since the deck still has Verdant Succession. So we can't use green creatures as stage creatures. How hard is it to remove Verdant Succession from the proceedings? I think we could use Assembly Hall, but that would require another copy of Centaur Safeguard, and also Child of Alara I think, and there's not enough space in the deck for that.
1) A way to ensure that the opponent is the only one to have any of the Rotlung Reanimators, and none of the hungry lynxes. That way the triggers are forced to be in the order we want.
2) An alternative way to boost toughness, the timing on this is very tricky. It needs to be forced to resolve after(before works too but seems harder) all of the rotlungs, and before the next arcbond trigger.
1 looks like a dead end for now.
2 looks very tricky as well, I'm not even sure what could fit in a spot like that. Something like Bramblewood paragon works for remaking the token at the right size, but I don't see anything like that that could work for the rest of our creatures. Maybe a Coat of Arms style effect?
Oh, but I guess you don't want triggered effects.
Edit: Would Coat of Arms not work with, say, Arcane Adaptation?
We want to be able to increase one creatures toughness by +X and another's by +Y etc.
Coat of Arms is kind of the right effect, but requires the total number of creatures to increase (and decrease?), which seems difficult to manage properly.
Edit:
Hmm, we might be able to implement a type of cyclic tag system with Coat of Arms and strictly increasing the number of creatures. I'm not sure what exactly we'd be able to implement here, but it might be worth looking into.
The idea is that we would have an extra set of rotlung reanimators making tokens that are indestructable thanks to something like Timber protector, with some Dralnu's crusades giving things the multiple types we'd need.
Actually halting is a problem, we'd need to set it up so that the arcbond creature only dies under some special circumstance.
There is a Turing-complete version of counter machines that uses just two counters and two types of instructions. However, the intructions can jump to arbitrary instructions in the program, so that might be hard to implement with Magic.
Looking at cyclic tag systems, that might be better suited to Magic. Cylic tag systems involve a sequence of productions, which are binary words, and a data word. So we need to be able to encode a sequence of binary words. One particularly simple Turing-complete version of cyclic tag systems are binary cyclic tag systems. BCTs have a command word and a data word, so only two binary words, but we still need to implement them as distinct structures.
First off, how are we going to implement binary words? We need to order our battlefield somehow. One way to do that is by increasing order of power or toughness. So, we could implement a binary word by existence of a creature of toughness - damage equal to n meaning the nth digit is a 1 while the lack of existence indicates that the nth digit is a 0. So for example, 01011101 would mean there are creatures of toughness - damage equal to 2,4,5,6, and 8, but none of any other values. To get both a command word and a data word, we could have two different creatures or creature types. Then, decrementing would appear straightforward, we deal 1 damage or give a -1/-1 counter to all appropriate creatures. However, appending words would appear to be difficult; we would have to add creatures of toughness of various levels greater than the max toughness. Coat of Arms wouldn't quite work here, since the number of creatures isn't necessarily tied to the length of the data word.
Perhaps reverse the order, and have increasing toughness - damage represent the data word from right to left? Then, we can append words by creating a token and triggering Cathars' Crusade when want to append a 1, and just adding +1/+1 to all appropriate creatures when we want to add a 0. Decrementing then becomes destroying the creature of greatest power or toughness - I seem to recall that there were cards like that.
Hmm, but then there's the command word. This is actually a cyclic word, so I'm not really sure how we should implement it. Evidently BCT's are Turing-complete even if the data word is just a 1, but then the command words would need to be allowed to be arbitrarily long. So we would need a construction of unlimited size, meaning we would have to use something indexed by numbers, i.e. toughness, power, or number of counters. But it would also have to operate cyclically, which seems very tricky.
It would be nice if BCT's were also Turing-complete using some restricted set of command words, but arbitrarily large data words. That would be worth finding out for sure.
Having said all this, I'm not sure how Coat of Arms would fit in here.
Edit: I just noticed that "destroy creature of greatest power/toughness" will not eliminate the rightmost digit, it will eliminate the rightmost digits up to the next 1, and the subsequent string of 0's. So rather than have 1 indicate existence and 0 indicate nonexistence, we will need to have 0 and 1 indicate different creatures or types of creatures of the appropriate toughness. So now, desroying a creature of the greatest power toughness will successfully decrement.
Examining the commands further, the appending command is actually executed if and only if the leftmost data bit is 1. So we need something to be executed or not executed depending on the creature or type of creature of the lower/highest power/toughness. That could be hard as well.
The key insight was using extra creature types to link with the Dralnu's Crusades. This allows the coat of arms type be different than the Rotlung reanimator trigger type. Letting the Rotlungs do the work of both pumping other registers, and remaking the current one. In a way that doesn't depend on the order the triggers resolve.
We do need to switch to 1/1 tokens to make the math easy but that's easy with Bishop of wings (though gaining that much life is unfortunate)
Setup, we have Dralnu's Crusades on "all As are a*s", "all Bs are b*s", etc. And a bunch of bishops that trigger on an X dying and make a y*. And one Bishop each of remaking the Main types.
OPERATION:
Arcbond trigger resolves dealing 1 damage to everything, and triggering arcbond.
When the 'Main' creature for row N dies, first Coat of arms causes a chain reaction and kills any supporting N* tokens.
Then the various Bishops trigger from an N dying. One remakes the N, then others make the supporting tokens for all of the rows in accordance with the "program", (making a*s, b*s etc), Making all of those tokens be 1/1 base forces that when the Main type dies, all of the tokens of the linked type die as well, truly Zeroing out the register so that we can be confident in the number we now have in there.
HALTING:
We can then set it up to have our Arcbond-ed creatures be creature type X
We keep them alive by occasionally making more creatures of type X
Note that the arcbonded creatures themselves take damage at half the rate everything else does however their supporting X tokens still take full damage and any of them dying causes a chain reaction that results in the originals dying.
As a demo/Proof of Concept I'll encode the last example program from the waterfall tutorial page linked earlier.
Setup: only 6 rows so the initial Dralnu's Crusades get set to
All Apes are Atogs
All Bats are Bees
All Cats are Crabs-- This is the halting row so nothing is needed hereAll Drakes are Druids
All Eggs are Eyes
All Fish are Foxes
The first collumn is just our initial state, so we have:
2 Atogs (one is an ape atog)
3 Bees (one is a bat bee)
3 Cats (with arcbond on two of them)
11 Druids (one is a Drake Druid)
7 Eyes (one is an Egg Eye)
3 Foxes (one is a Fox Fish)
Then each row tells us how much of the other things to make via bishops when triggered
Taking just the last row as an example
Whenever a fish dies: create 2 atogs, 3 bees, 1 cat, 2 eyes, 3 foxes and a fish.
Then we ping a cat and are off to the races.
This operation seems to be completely free of meaningful choice, ordering the death triggers does not matter here.
I think I need a sanity check here? Is there some problem that I missed?
Of course, the issue of whether the number of variables we can implement (it looks like there are 249 creature types so I think we can implement at most 124 variables?) is enough for Turing-completeness is a critical one. I don't think we can necessarily say that some UTM will correspond to some Waterfall setup (I'm calling a "Waterfall setup" to be some number of variables and the set of zeroing triggers for each variable), because the fact that the Waterfall model is Turing-complete doesn't necessarily imply that each Turing machine corresponds to one Waterfall setup; we could have a single Turing machine with different inputs correspond to different Waterfall setups (with various inputs), so a single UTM could potentially require an unbounded number of variables. Which would kibosh the whole idea of using The Waterfall Model for Turing-completeness, at least in terms of having creature types for variables. This might not be the case, but if not, we still need to find the number of variables required for Turing-completeness.
There are some creatures that we probably need to keep around (our various Rotlung Reanimators, for example), and they will have various creature types. We don't want these types to be set as Coat of Arms types, as then we will have unwanted pumps to our variable numbers. But perhaps these types being set to Rotlung Reanimator types will be okay? That looks fine, so we should be able to get the full 124 possible variables I think.
Another issue: Sure, once the Waterfall Model is fully set up, and the execution is started, maybe we will have no ways to affect the sequence of play (provided the rest of the deck doesn't provide us with any way to interrupt the execution), but for any point up until that execution starts, we have to be wary of possible infinities. With unlimited usage of Artificial Evolution, the threat of such infinities is very real.
But anyway, this looks like a major step forward - kudos!
Edit: Hmm no, I don't think we can set the creature types from our necessary creatures to be Rotlung Reanimator types either, since Dralnu's Crusade will turn these into Coat of Arms types. So, the maximum of number of variables will be some number less than 124, depending on however many creature types there are of creatures that we need to have on the battlefield during the execution of the computational model.
I have no clue how much space we need for a UTM. But that is a good point about how we don't actually have more variables for inputting an arbitrary Turing Machine. I also don't know if being able to handle two things zeroing at the same time lets us do anything fancy.
Creatures we need to keep around can be Artificial Evolutioned into some out of the way type-Zubera and we can set timber protector to give them indestructible.
I don't think our ability to diverge from setting up a 'normal' Waterfall Program is a problem?
And yeah we need to be just as careful of infinites as before.
Edit: and we can go back to Rotlung Reanimator by simply having a second coat of arms and doing 2 damage initially, freeing up life.
Also we only need to cast Artificial evolution once, on Zada, Hedron grinder.
The problem is that we aren't implementing Turing machines, we're implementing the Waterfall Model, for which the amount of work done in programming fast growing-functions is probably 0. So, we could guess that, once we got confirmation that the Waterfall Model is Turing-complete with the number of variables that we have available, that with a googolplex mana available for construction, we could implement all 100-state Turing machines. But even though this seems very likely, we wouldn't know for sure, unless we did some actual Waterfall Model programming and implemented a Turing machine interpreter. I imagine that would be quite a task!
Perhaps it would be easier to just try to program large numbers directly into the Waterfall Model. This might not be an easy task either though, if the Waterfall Model is very difficult to program in, which looks like it could well be the case.
Hmmm, Artificial Evolution only affects card text, not creature type. But perhaps you mean combining Artificial Evolution with a card that sets creature type? I couldn't find any suitable cards though - the cards I find either added creature types on top of existing creature types (which wouldn't solve the Coat of Arms problem), or removed all abilities from the creature, which is no good. But, I probably missed some cards.
I do think diverging from the correct setup could very well be a problem, but we can talk more about this once we have a prospective deck.
I don't want to get too far into the weeds optimizing the waterfall program, especially as there will probably be more creature types added.
But knowing the approximate ratio we can encode will be nice. But probably we can encode all n-state Turing Machines for some n that may be a function of the total number of creature types.
And as for putting large numbers in directly, I'm not sure how effective that would be...?
Also Artificial evolution does change types:
"10/4/2004 Alters all occurrences of the chosen word in the text box and the type line of the given card."
I don't think that there will be a nice ratio of number of creature types of number of states of a Turing Machine. Rather, if the number of creature types is large enough to support a Turing-complete computational model, then we will be able to encode all n-state Turing machines, where n is a function of how much setup we can do. But, if the number of creature types isn't enough to support a Turing-complete computational model, then the complexity class of our computational model will be very restricted, and we won't necessarily be able to encode even a 4 or 5-state Turing machines. I don't know for sure in this case of course, but it appears that generally when a computational model fails to be Turing-complete, it fails by quite a large margin. For example, if we have a simple BASIC-type programming language with increment, decrement, setting one variable equal to another, and WHILE loops, this programming language is Turing-complete, and the Busy Beaver function for it outgrows all computable functions, just like the normal Busy Beaver function. However, if we replace WHILE loops with FOR loops, the language becomes primitive recursive, so the Busy Beaver function for it will actually grow like the Ackermann function. Quite a drop off! It has been shown that even 4 or 5 state Turing machines can implement Collatz-like procedures, and I don't think we can implement those with a primitive recursive language, so we could top out at even something like 3 states if we fail to get Turing-completeness.
In order to get an actual lower bound for our deck, I don't see how we could do it other than to write a program to compute large numbers directly, or write an interpreter for a different computational model/language, and then program a large number in that other computational model. So it's not a matter of effectiveness but necessity. I suppose in the end we might just give up on this, and present a deck that in all likelihood generates a great big ginormous number, but we don't have any good lower bounds for it.
For instance if every TM instruction requires its own waterclock (seems likely to me), The ratio would be 2 for a binary TM, and if the UTM takes 40 clocks to implement, that gives us BB((124-40)/2)=BB(42)
So as a Starting point the 100% required cards are:
Dralnu's Crusade
Coat of Arms
Rotlung Reanimator
Arcbond (Can we now allow this to be cast more than twice?)
Artificial Evolution
Runed Halo
Some way to make ~124 copies of the crusade
Some way to make as many Rotlung Reanimators as possible.
Some way to deal 2 damage to a creature.
Some way to make a second Coat of arms.
Some way to spread Artificial Evolution to a bunch of creatures.
Some way to give our opponent a copy of Runed Halo
Oh Rotlung Reanimator can't get put to an out of the way creature type...
I think that means we need Bishop of Wings
Edit: Hmm, does the fact that the Rotlung Reanimator tokens come in higher break the Waterfall Model? We would have tokens come in at 3/3, so that would basically mean our zero triggers could not increment by one or two. Would we still have universality? Actually, for any Waterfall setup, we can mimic it with a the same Waterfall setup, but with the zero triggers all having their increments multiplied by 3. Then this new Waterfall setup would have the same execution sequence as the former setup, except it takes three times as many clock ticks to complete. So yes, I believe we would still be able to implement the same computations even if the tokens started at 3/3, so we can stick with Rotlung Reanimators and save life for later. Do you agree with this argument?
Edit: So, I've been thinking about how to not be able to do anything to interrupt the operation of the Waterfall Model computation, and it seems quite restricting. We can avoid cards like Leyline of Anticipation to not be able to casts sorceries, but Arcbond and Artificial Evolution are both instants. Now, both of those require mana and we lose the card from our hand, so either of those could prevent us from reusing them. But, if we have a way to get them back from the graveyard, either for setup purposes or for iterating this thing further, then we are in danger of being able to cast them, bring them back, and save enough mana in order to cast them during the execution of the Waterfall Model. So, that's very dangerous. One solution of course is to not be able get cards back from the graveyard, or instants anyway. That could definitely restrict our ability to iterate either the WM computation, or even just a starting combo to build up our resources for the WM computation.
We need to use Bishop of wings anyway due to Rotlung reanimator itself being a zombie cleric, so we can't hide them in a useless creature type.
It would be some setup for it, we need Copy Enchantment and... I guess just creature copiers, which we need anyway? So not that much more.
Edit: Good news! So, it looks like The Waterfall Model can be emulated by Minsky machines fairly efficiently. I got a friend to help me find the minimum number of variables needed to encode a universal Minsky machine, but it doesn't look like it will be that many, as in less than 50. So with just 50 variables (presumably), we get a Busy Beaver-like function based on the amount of setup that we can do. So we don't need to try to hard to get to 124 variables, once we already have Turing-completeness. So we don't necessarily need to have something like Timber Protector so that we can reuse the card types of necessary creatures. On the other hand, if there's not much in the way we can do in terms of iteration, then maybe we might as well use them to increase the variable count.
Edit:
That is great news indeed, so we definitely have the TM improvement we were searching for, and the extra variables can be just for additonal computation.