3 ms·
Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a
by calf 7y ago
Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a reduction of Halt to Magic exists). So your task is that difficult.
Thus the theory says it is a logical contradiction for any algorithm to exist that can solve Magic. In practice, this can be different because we are routinely successful in special cases for example we still have anti virus programs in practice, just no one perfect anti virus program can exist for the same reason.
- hinkley 7y agoWhat happens in Magic when you run out of cards? If the tape isn't infinite then there are lots of algorithms that halt. The halting problem is like the pigeonhole principle. Just because there is no general compression algorithm doesn't mean we don't use compression all day every day. We have solutions for many interesting subsets of the problem domain, and that's good enough. We can also tell if a program will halt in no more than N clock cycles by providing the analysis with a budget. If the budget is exhausted then the program would keep running for an unknown duration longer than the limit. Possibly 1 cycle. For third party code, you could just refuse to run that code at all. There are some useful programs that would get rejected but there are many useful ones that would not. So implementing an "infinite loop detector" as a "really big loop detector" wouldn't be the dumbest thing to try, anymore than implementing video compression is.
- hannasanarion 7y agoIn magic, if you run out of cards, you lose, but there are ways to restore your cards so you never run out, so games can continue theoretically forever.
- thiagoharry 7y agoAnd even if you don't, it's possible to create infinite resources combining a finite number of cards. Like creating infinite tokens, infinite mana. The paper uses an infinite number of creature tokens to represent an infinite tape.
- calf 7y agoMy understanding is that the undecidability of the halting problem is equivalent to the undecidability of the decision version of compression (does a given string have a Kolmogorov representation, or not). They're saying the same thing and mathematically equivalent to Godel's incompleteness as well. The difference is that with data compression, you don't get random-looking inputs and would explain why text, voice, image domains are amenable to compression algorithms. In contrast, the state space of programs is exponential in the budget N and looks very random. The exponential explosion makes the analysis very inefficient relative to hardware ability. And then the random-looking state sequences are especially not very compressible. These characteristics are harder to leverage. The pigeonhole principle works for lossless compression but I don't see the analog to Halt or Rice's theorem, etc.
- improv32 7y agoIf we knew Magic was limited to N states, then we can conclude that a program running on the Magic Turing machine will never halt if it has not halted after BB(N) steps.