[tcbawo]

The game is constantly changing because new sets are rotating through, but I believe it is possible to create infinite loops with certain dynamics, or at least it has been possible at various points. ie. something like creating/killing token characters with "on entry"/"on exit"/"untap" mechanics, etc. Not all of them result in either player taking damage.

[chmod775]

The rules explicitly address infinite loops and forbid players from forever taking actions that create one. If one would occur anyways, the game ends in a draw.

https://mtg.fandom.com/wiki/Loop

[gpm]

Ok, so instead of being turing complete it requires solving the halting problem to properly referee it?

[lanternfish]

There are multiple unresolvable game states (panglacial wurm...) but there are catch all rules which allows judges to say 'you're not trying to win, so your blocking line results in a game loss'. They have banned cards before (painter's servant) which resulted in competitive non-deterministic winning sequences that forced hundreds of game actions to resolve.

[aidenn0]

> 'you're not trying to win, so your blocking line results in a game loss'.

Is that how it goes now? It used to be infinite loops (e.g. playing a Faceless Butcher when the only creature in play is a Faceless Butcher that exiled another Faceless Butchers) resulted in a draw, not a loss.

[ivanbakel]

Forced infinite loops are still a draw, but setting up a complex-enough board state where the infinite-ness or forced-ness of a particular loop is hard for the judge to decide on will just result in a game loss.

Put another way: you can try to set up a game state in a competitive match where the judge has to solve the Collatz conjecture, but because that would take way too long and clearly be contrary to good sportsmanship, you'd never reach that point.

[dolni]

The halting problem does not forbid us from discerning if SOME programs will ever halt. It says that there are definitely programs for which we cannot know.

I suspect most of the MTG infinite loops are something like "A triggers B, B triggers C, and C triggers A". Asserting that the loop will never resolve is not a violation of the halting problem.

[gpm]

Absolutely, but assuming that magic the gathering without the rule about loops is turing complete, then it's possible to set up all programs in magic the gathering, not just nice ones. In particular there exists a program where it is impossible to tell whether it is in an infinite loop or not without solving the halting problem.

The rule cited is worded to only apply to loops that go on indefinitely (machines that don't halt), so the referee can't even know whether or not they're allowed to apply the rule against a without knowing if it halts. On the particular machine mentioned above that would require solving the halting problem.

And yes, I'm sure the people saying "they'd just kick you out if you tried this in a tournament" are right. That's really not the point. The point is the cited rule doesn't really make things better with respect to turing completeness. If magic the gathering without the cited rule is turing complete, then with it it's both just-shy-of-turing-complete* (you'd be able to run any program that does halt) and uncomputable.

* Depending on the precise definition of "turing complete" it might in fact be turing complete. You can evaluate any program. Either it does halt and you can report the output, or it doesn't halt and you can report that you're in an infinite loop because the referee-oracle said so. That's probably enough to satisfy most definitions - even if it's a strange way to implement it.

[joshuamorton]

Probably not, the infinite loop rules are specifically about rules where a player cannot make a choice in the process.

It's possible that there's a way to do something turing-challenging or busy-beavery in such a situation, but it's usually pretty difficult to make complex unbendable loops, they're usually very direct cases where taking an action more or less forces you to immediately take the same action again, so the loop has...two steps. Anything much bigger or more complex and you're basically assured to have player choice.

There's probably room to do something where a player is clearly losing unless they do something which might continue a situation that is undecidable.

[tcbawo]

If you have two choices for spend/untap, I think it would be fairly trivial to create Turing complete logic that also presents discretion and requires involvement from the player. However, it sounds like such an arrangement can still considered a draw in “competitive play”. There are many formats to Magic, though. If any other Turing machine had an outside observer ready to pull the plug after an arbitrary amount of time, does it make it less of a Turing machine?

[themoonisachees]

Semantically, yes. Turing machines (actual ideal ones that only exist in maths papers) always compute forever. They are also instantaneous and have infinite resources.

The argument is that MtG is Turing complete except for that part, because it cannot compute forever, even in an ideal scenario where time and space are infinitely available, because the rules explicitly forbid it.

An ideal Turing machine with someone to pull the plug is not a Turing machine. Also: just because humans can recognize some infinite loops doesn't mean we can recognize all infinite loops, so the person pulling the plug may be misinterpreting and pulling the plug on a machine that would otherwise eventually halt.

[chmod775]

> Ok, so instead of being turing complete it requires solving the halting problem to properly referee it?

No - because the referee doesn't have to devise a program to do it. They can decide whatever they want. Also the statement of the halting problem isn't about it being impossible to tell whether a program will terminate, it's about it being impossible to devise a program that can tell whether any other program running on a turing machine (which actual physical computers are not, since they have finite state) will terminate.

For any program running on actual physical computer hardware it is obviously possible to tell whether it will terminate. For an actual game of magic, which has considerably less possible state, it's likely even trivial 99.9% of the time. The remaining 0.01% are up to the judge. In the case of MTGA on a computer, there are hard-coded limits on many things (but a lack of enforcement of the first part of the loop rule. Nexus of Fate wasn't a good time.).

[readams]

It is absolutely not true that for any problem on a real computer it's possible to tell if it terminates, other than fairly trivial observations such as noting that if it runs longer than 2^(size of memory) steps it must be looping.

If you could, then I'd start using your "real computer" halt checker to instantly mine bitcoin or break all cryptography, so let me know when you figure out out.

[aidenn0]

MTG doesn't require solving the halting problem because, if neither player nor the referee can come up with a way to halt a loop, then the match ends (long ago, when I played, it ended in a draw; other comments in this thread suggest that a player intentionally doing this may incur a loss now).

[chmod775]

> It is absolutely not true that for any problem on a real computer it's possible to tell if it terminates

Hmmm. Reading on...

> [..] other than fairly trivial observations such as noting that if it runs longer than 2^(size of memory) steps it must be looping.

So you are saying "You can't do it, even though it's trivially obvious that you can."

Or maybe "If we ignore that it is possible, it is not possible."

What am I supposed to do with your comment?

[ben_w]

2ⁿ > n ∀n ∈ ℕ (n>1), therefore while the test is trivial to define for any finite system, in practice you can't do that many steps even for very small n — n=256 states is 2^256 tests is just shy of 2e26 years if each test takes one Planck time.

For a purely theoretical system (which includes the abstracted rather than physically implemented rules of MtG as used by Churchill, Biderman, & Herrick in their paper), n is effectively ℵ₀.

https://arxiv.org/abs/1904.09828

[robertlagrant]

> So you are saying "You can't do it, even though it's trivially obvious that you can."

They're referring to the halting problem. If you believe you can solve it, you will win money[0].

[0] https://www.claymath.org/millennium/p-vs-np

[kbrkbr]

You probably meant 99.99%, or 0.1%.