5 ms·

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

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?

deepnotderp 9y ago
Tokens or an infinite blink (exiled and returns) mechanism I think. I haven't seen the thing in a while :)
- staticautomatic 9y ago
  You can also go infinite with time warp and a means of fetching it from your graveyard.
valbaca 9y ago
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)
- dragontamer 9y ago
  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.
deleted 9y ago
[deleted]
xaedes 9y ago
huh? - so we can never build turing machines? because we can never build infinite memory?
- schoen 9y ago
  True, no Turing machine in the strict sense is physically realizable!
- gnulinux 9y ago
  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.
- Retra 9y ago
  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.

deepnotderp 9y ago

Tokens or an infinite blink (exiled and returns) mechanism I think. I haven't seen the thing in a while :)

staticautomatic 9y ago
You can also go infinite with time warp and a means of fetching it from your graveyard.

valbaca 9y ago

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)

dragontamer 9y ago
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.

deleted 9y ago

[deleted]

xaedes 9y ago

huh? - so we can never build turing machines? because we can never build infinite memory?

schoen 9y ago
True, no Turing machine in the strict sense is physically realizable!
gnulinux 9y ago
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.
Retra 9y ago
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.