6 ms·

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

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 3y ago
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 3y ago
> 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?
- robertlagrant 3y ago
  > 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 https://www.claymath.org/millennium/p-vs-np
  - chmod775 3y ago
    > They're referring to the halting problem. If you believe you can solve it, you will win money. Proving that you can programatically determine whether a program halts when you limit the turing machine to finite memory is trivial - which the conversation you interjected was about.
    - robertlagrant 3y ago
      They weren't saying the problem was trivial. They were saying that if you massively reduce the problem to its most trivial form, then its trivial form is doable.
      - chmod775 3y ago
        > They weren't saying the problem was trivial. Neither was I? The proof is trivial - actually doing it is very much not.
        robertlagrant 3y ago
        How would you prove it in the non-trivial case?
        chmod775 3y ago
        What? Are you trolling?
        robertlagrant 3y ago
        I've no idea what you're talking about. If you ask a non-content free question I can help.
- ben_w 3y ago
  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 https://arxiv.org/abs/1904.09828
  - chmod775 3y ago
    We don't actually need to know whether something will result in a loop ahead of time, so there's another approach which is much more doable in the context of MTG: Most digital CCG engines already record every past state through a history of actions (some even have full match replays). Together with engine-limits on recursively triggered actions, it really isn't that much data. You can check for repeated state here. The most naive implementation would replay the entire previous match every time a new action happens. A better implementation realizes that you don't need to - because once you have one repeat, everything after should be a repeat as well, so you really can just keep running and merely check for repeats at strategic points (such as between turns or on any human input). Store the serialized state at those points in some appropriate Set implementation to make checking easy and fast. Increase the spacing between those checkpoints, deleting old ones, if space becomes an issue - though if you get to this point, the game has run for so long that the humans playing it probably need medical attention. If you want to get even fancier, store serialized state rarely and just store hashes of state at checkpoints, replay from a serialized state using recorded inputs once you detect a collision. All of this is possible because of the human element: Human just aren't physically capable of producing enough input to make a computer sweat about recording it. One downside of this approach is that it requires some programmatic refeering in case of "numbers go up" scenarios if you don't want to wait for some player's health pool or token pile to run into the engine limit and keep the game to a length a human can enjoy (do you cap these for comparison? compare with low precision? only allow a decrease?). There's some other scenarios that will not repeat exact state until a human died of old age too. However in real life magic "Loop" is not such a narrow term - just one number being slightly different will not save you from having to explain yourself to the judge. It'll stop this guy in any case: https://www.reddit.com/r/MagicArena/comments/amxhnk/is_there_a_game_time_limit_currently_in_an/ https://www.reddit.com/r/MagicArena/comments/amxhnk/is_there... Since what they did was reportable behavior, I suppose technically human referees would eventually take care of it anyways.

aidenn0 3y ago

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 3y ago

> 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?

robertlagrant 3y ago
> 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 https://www.claymath.org/millennium/p-vs-np
- chmod775 3y ago
  > They're referring to the halting problem. If you believe you can solve it, you will win money. Proving that you can programatically determine whether a program halts when you limit the turing machine to finite memory is trivial - which the conversation you interjected was about.
  - robertlagrant 3y ago
    They weren't saying the problem was trivial. They were saying that if you massively reduce the problem to its most trivial form, then its trivial form is doable.
    - chmod775 3y ago
      > They weren't saying the problem was trivial. Neither was I? The proof is trivial - actually doing it is very much not.
      - robertlagrant 3y ago
        How would you prove it in the non-trivial case?
        chmod775 3y ago
        What? Are you trolling?
        robertlagrant 3y ago
        I've no idea what you're talking about. If you ask a non-content free question I can help.
ben_w 3y ago
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 https://arxiv.org/abs/1904.09828
- chmod775 3y ago
  We don't actually need to know whether something will result in a loop ahead of time, so there's another approach which is much more doable in the context of MTG: Most digital CCG engines already record every past state through a history of actions (some even have full match replays). Together with engine-limits on recursively triggered actions, it really isn't that much data. You can check for repeated state here. The most naive implementation would replay the entire previous match every time a new action happens. A better implementation realizes that you don't need to - because once you have one repeat, everything after should be a repeat as well, so you really can just keep running and merely check for repeats at strategic points (such as between turns or on any human input). Store the serialized state at those points in some appropriate Set implementation to make checking easy and fast. Increase the spacing between those checkpoints, deleting old ones, if space becomes an issue - though if you get to this point, the game has run for so long that the humans playing it probably need medical attention. If you want to get even fancier, store serialized state rarely and just store hashes of state at checkpoints, replay from a serialized state using recorded inputs once you detect a collision. All of this is possible because of the human element: Human just aren't physically capable of producing enough input to make a computer sweat about recording it. One downside of this approach is that it requires some programmatic refeering in case of "numbers go up" scenarios if you don't want to wait for some player's health pool or token pile to run into the engine limit and keep the game to a length a human can enjoy (do you cap these for comparison? compare with low precision? only allow a decrease?). There's some other scenarios that will not repeat exact state until a human died of old age too. However in real life magic "Loop" is not such a narrow term - just one number being slightly different will not save you from having to explain yourself to the judge. It'll stop this guy in any case: https://www.reddit.com/r/MagicArena/comments/amxhnk/is_there_a_game_time_limit_currently_in_an/ https://www.reddit.com/r/MagicArena/comments/amxhnk/is_there... Since what they did was reportable behavior, I suppose technically human referees would eventually take care of it anyways.