News for hackers. Stuff that matters.
Re:Magic: The Gathering Is Turing Complete (2012) by maxiepoo on Thursday November 16, 2017 @12:56PM (#15714821)
As someone that does not understand the rules of Magic, how do they get around the fact that a Turing machine requires infinite memory? Presumably a particular game of Magic has a finite set of cards and probably states too?
Re:Magic: The Gathering Is Turing Complete (2012) by valbaca on Thursday November 16, 2017 @01:10PM (#15714978)
Many Magic cards can create "tokens" which don't count as cards, but can operate in the same way as cards in many ways.

You can have as many tokens as you can create. The MTM (Magic Turing Machine) seems to rely on this.

It's actually within the rules to "go infinite" with tokens. For example, you have a Foo which taps (is spent) to create a Bar token. The Bar token can untap (reset) Foo. Since you can do this as much as possible, within the rules you effectively just simulate that you can repeat the combo, pick a number (100, 1 million or 1 Googolplex), and you have that many.

The proof is much more complex than that, using various creature types (zombie, rats, etc.) and other game states, but that is how the infinite memory problem can be overcome.

It's also worth noting that the infinite memory requirements is often ignored when showing Turing Completeness.

(I play a lot of Magic and just took a glance at the page)

Re:Magic: The Gathering Is Turing Complete (2012) by dragontamer on Thursday November 16, 2017 @01:12PM (#15715001)
The tape is actually very simple.

+1/+1 counters on Zombies represent the tape to the right. +1/+1 counters on Yetis represent the tape to the left.

Whenever you reach the "end of Tape" (ie: All your Zombies are now Yetis), there's a trigger that creates a new Zombie token. Effectively creating "infinite tape". I didn't read to see how it worked on the "Yeti side", but I presume its the same concept.

Moving the tape back and forth is about putting -1/-1 counters on Yetis and +1/+1 counters on Zombies, or vice versa. Death triggers convert Yetis into Zombies and vice versa.

There are 18-states representing the "tape head" (which I presume to be the current creature with zero counters on it). I haven't really looked into how it works, but "Halt" state is pretty amusing actually. The "Halt" state kills all players, which "Halts" the program.

Re:Magic: The Gathering Is Turing Complete (2012) by deepnotderp on Thursday November 16, 2017 @12:57PM (#15714843)
Tokens or an infinite blink (exiled and returns) mechanism I think. I haven't seen the thing in a while :)
Re:Magic: The Gathering Is Turing Complete (2012) by staticautomatic on Thursday November 16, 2017 @02:30PM (#15715734)
You can also go infinite with time warp and a means of fetching it from your graveyard.
Re:Magic: The Gathering Is Turing Complete (2012) by xaedes on Thursday November 16, 2017 @02:09PM (#15715520)
huh? - so we can never build turing machines? because we can never build infinite memory?
Re:Magic: The Gathering Is Turing Complete (2012) by gnulinux on Thursday November 16, 2017 @07:25PM (#15717991)
Yes, computers are not Turing machines but finite state machines. But in practice, this is not very useful since the number of states of a computer is huge, so, Turing machine is a good model for computers. In math, we're not interested in physical objects but models and it turns out the study of Turing machines can be applied to physical computers. When you think of computer, you do not think it as finite state machine, but as a Turing machine. Maybe if you had a machine with 1KB memory, you could think it as a finite state machine, if it's more useful.

Another thing is, most algorithms people deal with are O(1) since people are interested in ints which can represent -2^63 to 2^63-1. But this is just an abuse of terminology, an algorithm that tries all 2^64 combinations would be a very impractical O(1) algorithm. So, we instead use a different model, and pretend integers are arbitrarily long and their length is O(logn) bits. This is now a better model for physical computers.

Re:Magic: The Gathering Is Turing Complete (2012) by schoen on Thursday November 16, 2017 @02:25PM (#15715682)
True, no Turing machine in the strict sense is physically realizable!
Re:Magic: The Gathering Is Turing Complete (2012) by Retra on Friday November 17, 2017 @12:26AM (#15719198)
Sure. But anything a turing machine could calculate in finite time can be calculated using finite memory, so this doesn't matter unless you're trying to compute things that don't end.