10 ms·
> 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 pr
by chmod775 3y ago
> 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 3y agoIt 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 agoMTG 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 agoThey 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 agoHow would you prove it in the non-trivial case?
- chmod775 3y agoWhat? Are you trolling?
- 3y ago
- kbrkbr 3y agoYou probably meant 99.99%, or 0.1%.