> No. Just don't use outside state? Obviously you can just make the state of your PRNG part of your overall state as well.

You can't write a program to analyze any given PRNG (or whatever) to know what it will return when without executing it. You could do this for some PRNGs, but that... probably doesn't meet the definition of pseudorandom.

> Also remember we're trying to reason about computer programs before you come up with ideas like measuring physical phenomena.

Oh I think if anyone's doing this it's you: one of your argument's main legs is that you can analyze RAM usage.

> In the case MTG, which doesn't have many dice mechanics

Yeah the last I played was Homelands so I'm very out of date. If we restrict ourselves to MtG then yeah, I think dice probably aren't insurmountable. For instance, dice are pretty limited RNGs, so you can easily interpret them as ranges to limit the scope of states you'd need to track, and you can do even better if they're just numeric values (i.e. it's always like "add N health" or "add N * 2 health") instead of branches (N <= 2 you lose, N >= 4 you win). This is modelable in finite space, and as you point out the space in general is pretty small. So, yeah sometimes the domain can allow you to avoid theoretical pitfalls.

> Attach that previous state (sans recursion) to the state of the enchantment on the field. You'll need it to code that enchantment anyways.

I'm not super sure what you mean here. I've been thinking of state as like, what cards are in play/hands/graveyard/etc, (tapped) lands, counters, turn, life, phase, and so on--basically whatever you would save in a game save to restore it later. I guess maybe you're thinking you can save something like a triggered or didn't trigger flag on every enchantment as part of your state, but this only works for the "check last state" enchantment, not a "check the last 10 (or N) states". Again I'd be very surprised if there were ever a card like this, so we're purely in the wider realm of the halting problem. My only point here is that there's, as Wikipedia puts it, always a theoretical pathological program (enchantment) to do the opposite of what your heuristic analysis program expects it to do, such that it's not possible to write a general analysis program to see if a Turing complete program will halt. I think the answer re: MtG is: don't print that card lol.

> How would you implement stateDidntChange

Nah let's not get confused here. States are successive, not recursive, i.e. they can refer to each other ("last turn", "after untap") but they can't contain each other. Re: implementation, generally the execution engine has some container of states it can access in various ways (previous, first, current, etc) and things in the program/game can access them. In this way you can then check for changes, because you now have access to more than 1 thing.

But, yeah you can get around this by just limiting the number of states you'll store that haven't changed, and not printing cards (writing expressions) that refer to states outside that limit. This is what a lot of in-game scripting engines do: if you've run N bytecode ops or for M seconds without finishing, you're looping infinitely (even if you might not be) and you're killed. Hardware watchdog timers do a similar thing. So, I think overall you're right that in practice we deal with the halting problem in arbitrary ways all the time and it's very OK, you just kind of have to outline the kinds of valid programs you're disallowing.