[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.